[그래프 이론] 클릭(clique)이란 무엇인가?

클릭이라는 것은 완전그래프인 부분그래프를 의미한다.

그러면 먼저 완전그래프가 무엇인지 알아보자.

완전그래프 (complete graph)

⇔ 임의의 서로 다른 두 꼭지점이 인접하고 위수가 n인 단순그래프

클릭이란 그래프에서 완전그래프를 만족하는 부분그래프를 뜻한다.

C: 클릭 (clique)

⇔ C: 부분그래프이면서 완전그래프

예를 들어 위 그래프에서 크기가 4인 클릭은 보다시피 진한 파란색으로 표시되어 있다. (4개의 꼭지점이 빠짐없이 인접)

크기가 3인 클릭은 하늘색으로 표시되어있다. (3개의 꼭지점이 빠짐없이 인접)

클릭수(clique number)란 그래프에서 최대 클릭의 크기를 이야기한다. $\omega (G)$라고 표시한다.

예를 들어 위 그래프에서 클릭수는 4가 된다.