클릭 (그래프 이론)

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

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

정의

편집

그래프  클릭  완전 그래프부분 그래프이다. 즉, 꼭짓점으로 이루어진 집합 중 모든 두 꼭짓점이 변으로 연결되어 있는 집합을 말한다.

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

성질

편집

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

그래프  의 클릭은 그 여 그래프  독립 집합이며, 반대로 그래프  의 독립 집합은 여 그래프  의 클릭이다.

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

어원

편집

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

같이 보기

편집

외부 링크

편집