클릭 (그래프 이론)

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
K5, 완전 그래프. 이러한 부분 그래프가 있으면, 그 부분 그래프에 속하는 꼭지점들은 크기 5인 클릭을 이룬다.

그래프 이론에서 클릭(clique)이란 무향 그래프 G의 꼭지점으로 이루어진 집합 중 모든 두 꼭지점이 으로 연결되어 있는 집합을 말한다. 이는 V의 유도 부분 그래프가 완전 그래프라는 것과 동치이다. 클릭의 크기는 그 클릭에 있는 꼭지점 개수로 한다. 최대 클릭은 꼭지점을 더 추가할 수 없는 클릭이다.

그래프에서 주어진 크기의 클릭이 있는지를 찾는 문제는 NP-완전이다. (이것을 클릭 문제라고 한다.)

모든 클릭은 완전 그래프에서 대응하는 독립 집합이 있기 때문에, 클릭의 반대는 독립 집합이라고 볼 수 있다.

클릭이라는 용어는 꼭지점이 사람을 나타내고 변이 '아는 사람' 관계를 나타낸다면, 모든 사람이 서로를 안다는 것은 clique 클릭[*](무리, 도당, 파벌)을 이룬 것과 같다는 생각에서 온 것이다.

그래프 G완전모임수 \omega(G)는 그 그래프에 존재하는 클릭 중에서 가장 큰 것의 크기를 의미한다.

더 보기[편집]