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

Posted by Bitssam
2015.11.04 18:30 전공수학/Discrete Math

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


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


완전그래프 (complete graph)

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


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


C: 클릭 (clique)

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

VR complex


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

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


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


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



'전공수학 > Discrete Math' 카테고리의 다른 글

[그래프 이론] 클릭(clique)이란 무엇인가?  (0) 2015.11.04
이 댓글을 비밀 댓글로