클릭 (그래프 이론)

위키백과 ― 우리 모두의 백과사전.

K₅, 완전 그래프. 이러한 부분 그래프가 있으면, 그 부분 그래프에 속하는 꼭지점들은 크기 5인 클릭을 이룬다.

그래프 이론에서 클릭(영어: clique)이란 무향 그래프 G의 꼭지점으로 이루어진 집합 중 모든 두 꼭지점이 변으로 연결되어 있는 집합을 말한다. 이는 V의 유도 부분 그래프가 완전 그래프라는 것과 동치이다. 클릭의 크기는 그 클릭에 있는 꼭지점 개수로 한다. 최대 클릭은 꼭지점을 더 추가할 수 없는 클릭이다.

그래프에서 주어진 크기의 클릭이 있는지를 찾는 문제는 NP-완전이다. (이것을 클릭 문제라고 한다.)

모든 클릭은 완전 그래프에서 대응하는 독립 집합이 있기 때문에, 클릭의 반대는 독립 집합이라고 볼 수 있다.

클릭이라는 용어는 꼭지점이 사람을 나타내고 변이 '아는 사람' 관계를 나타낸다면, 모든 사람이 서로를 안다는 것은 영어: clique 클릭(무리, 도당, 파벌)을 이룬 것과 같다는 생각에서 온 것이다.

[편집] 더 보기

클릭 문제
최대 공통 부분 그래프 동형 문제

분류: 그래프 이론

See also ebooksgratis.com: no banners, no cookies, totally FREE.

클릭 (그래프 이론)

위키백과 ― 우리 모두의 백과사전.

[편집] 더 보기

Views

둘러보기

찾기

다른 언어