클릭 (그래프 이론)

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

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

정의[편집]

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

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

성질[편집]

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

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

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

어원[편집]

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

바깥 고리[편집]

같이 보기[편집]