클릭 (그래프 이론)

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

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

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

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

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

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

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

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

 외부 링크 





분류:그래프 이론