클릭(Clique)

클릭(Clique)

정의

  무방향성 그래프(undirected graph) G에서 clique의 성질을 갖는것은 서로다른 두 점(vertices)을 연결하는 선(edge)이 있는 점들의 집합들로 이루어진다.  다시 말해서 clique는 각각의 모든 점들이 자신을 제외한 다른 점들에 바로 연결 될수 있는 그래프를 말한다. ^[1]

  즉, complete graph의 부분 그래프를 clique이라고 한다. ^[2]

 

그래프 G 에서 가장 큰 clique는 이론적으로 중요하므로 ω(G) 로 표현한다.^[1]

 

n개의 노드로 이루어진 그래프에서 크기가 3인 clique의 개수는 0, 0, 1, 4, 12, 31, 67, ...개가 된다(Sloane's A005289). A complete k-partite graph has maximum clique size . The largest order graph which does not contain the complete graph K_p as a subgraph is called the Turán's graph T_{n, p} (Skiena 1990, p. 218). ^[3]

 

 

↑ 6개의 점(vertices)와 7개의 선(edges) 로 이루어진 그래프. vertex 1, 2, 5는 clique 크기가 3인 clique이다.^[1]
반면, 2,3,5로 이루어진 그래프는 3,5가 서로 연결되지 않아 clique가 되지 못한다.^[2]

 

 

↑ Clique의 예^[3]

 

용어의 유래^[1]

Clique라는 용어의 유래는 점(vertices)을 사람으로 나타내고, 선(edge)를 '알려져 있다'는 의미로 사용해서, 모든 사람이 다른 모든 사람을 알고 있다는 의미의 clique에서 유래됐다고 생각된다.

 

Clique의 크기^[1]

clique의 크기(the size of a clique)는 vertices의 개수이다.

 

↑ K₅ 인 complete 그래프. 이 그래프의 clique의 크기(a clique of size)는 5이다.^[1]

 

Clique Problem

그래프에서 주어진 크기의 clique를 찾는 문제를 clique problem이라고 하며 NP-complete 문제이다.^[1]

 

반대 개념

clique의 반대되는 개념은 independent set으로, 말하자면 모든 clique는 complement graph 그래프에의 independent set에 대응된다고 할 수 있다.^[1]

 

See also

• Solving the Maximum common subgraph isomorphism problem ^[1]
• Maximal clique ^[1]
• Clique Graph, Clique Number, Complete Graph, Induced Subgraph, Party Problem, Perfect Graph, Ramsey Number, Turán's Theorem ^[3]

 

참고자료

(1) http://en.wikipedia.org/wiki/Clique_(graph_theory)

(2) http://ko.wikipedia.org/wiki/%ED%81%B4%EB%A6%AD_%EB%AC%B8%EC%A0%9C

(3) http://mathworld.wolfram.com/Clique.html

 

 

이 글은 스프링노트에서 작성되었습니다.