클릭 (그래프 이론)

그래프 이론에서 클릭(영어: clique)은 모든 가능한 변이 존재하는 꼭짓점들의 부분집합이다.

완전 그래프 K₅. 이러한 부분 그래프가 있으면, 그 부분 그래프에 속하는 꼭짓점들은 크기 5인 클릭을 이룬다.

정의

그래프 ${\displaystyle G}$의 클릭 ${\displaystyle C\subset G}$은 완전 그래프인 부분 그래프이다. 즉, 꼭짓점으로 이루어진 집합 중 모든 두 꼭짓점이 변으로 연결되어 있는 집합을 말한다.

극대 클릭(영어: maximal clique)은 포함 관계에 따라 극대인 클릭이다. 즉, 더 이상 꼭짓점을 추가할 수 없는 클릭이다. 최대 클릭(영어: maximum clique)은 크기가 가장 큰 클릭이다. 그래프 ${\displaystyle G}$의 최대 클릭의 크기는 클릭 수(영어: clique number)라고 하며, ${\displaystyle \omega (G)}$로 쓴다.

성질

클릭은 항상 유도 부분 그래프이다.

그래프 ${\displaystyle G}$의 클릭은 그 여 그래프 ${\displaystyle {\bar {G}}}$의 독립 집합이며, 반대로 그래프 ${\displaystyle G}$의 독립 집합은 여 그래프 ${\displaystyle {\bar {G}}}$의 클릭이다.

그래프에서 주어진 크기의 클릭이 있는지를 찾는 문제는 클릭 문제라고 하며, 이는 NP-완전 결정 문제이다.

어원

영어 낱말 클릭(clique)은 무리 또는 파벌을 뜻한다. 이는 그래프의 클릭을 서로 친하게 지내는 사람들의 파벌에 빗댄 것이다.

같이 보기

• 완벽 그래프
• 클릭 문제
• 독립 집합

외부 링크

• Weisstein, Eric Wolfgang. “Clique” (영어). 《Wolfram MathWorld》. Wolfram Research.
• Weisstein, Eric Wolfgang. “Clique number” (영어). 《Wolfram MathWorld》. Wolfram Research.
• Weisstein, Eric Wolfgang. “Maximal clique” (영어). 《Wolfram MathWorld》. Wolfram Research.
• Weisstein, Eric Wolfgang. “Maximum clique” (영어). 《Wolfram MathWorld》. Wolfram Research.