클릭 (그래프 이론) 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Complete graph K5.svg|right|섬네일|200px|[[완전 그래프]] K<sub>5</sub>. 이러한 부분 그래프가 있으면, 그 부분 그래프에 속하는 꼭짓점들은 크기 5인 클릭을 이룬다.]]

[[그래프 이론]]에서 '''클릭'''({{llang|en|clique}})은 모든 가능한 변이 존재하는 꼭짓점들의 부분집합이다.

== 정의 ==
[[그래프]] <math>G</math>의 '''클릭''' <math>C\subset G</math>은 [[완전 그래프]]인 [[부분 그래프]]이다. 즉, [[꼭짓점]]으로 이루어진 집합 중 모든 두 꼭짓점이 변으로 연결되어 있는 집합을 말한다.

'''극대 클릭'''({{llang|en|maximal clique}})은 포함 관계에 따라 극대인 클릭이다. 즉, 더 이상 꼭짓점을 추가할 수 없는 클릭이다. '''최대 클릭'''({{llang|en|maximum clique}})은 크기가 가장 큰 클릭이다. [[그래프]] <math>G</math>의 최대 클릭의 크기는 '''클릭 수'''({{llang|en|clique number}})라고 하며, <math>\omega(G)</math>로 쓴다.

== 성질 ==
클릭은 항상 [[유도 부분 그래프]]이다.

그래프 <math>G</math>의 클릭은 그 [[여 그래프]] <math>\bar G</math>의 [[독립 집합]]이며, 반대로 그래프 <math>G</math>의 독립 집합은 [[여 그래프]] <math>\bar G</math>의 클릭이다.

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

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

== 같이 보기 ==
* [[완벽 그래프]]
* [[클릭 문제]]
* [[독립 집합]]

== 외부 링크 ==
* {{매스월드|id=Clique|title=Clique}}
* {{매스월드|id=CliqueNumber|title=Clique number}}
* {{매스월드|id=MaximalClique|title=Maximal clique}}
* {{매스월드|id=MaximumClique|title=Maximum clique}}

[[분류:그래프 이론]]