완벽 그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
완벽 그래프의 예. 만약 그래프에서 왼쪽 세 꼭지점을 제외한 모든 꼭지점을 지웠을 때 얻어지는 그래프(굵은 색)는 색칠수완전모임수가 같다. 다른 꼭지점을 지웠을 때에도 마찬가지 결과가 얻어진다.

어떤 그래프에 대해서, 그 그래프의 모든 유도 부분 그래프(그래프에서 일부 꼭지점을 지워서 얻어지는 부분 그래프)에 대해, 그 유도 부분 그래프의 색칠수 \chi완전모임수 \omega(그 그래프가 가지고 있는 최대 클릭 크기)가 항상 서로 같을 경우, 그 그래프를 완벽 그래프(perfect graph)라고 정의한다.

완벽 그래프는 여러 중요한 성질을 가지고 있다. 예를 들어, 완벽 그래프에서는 그래프 색칠 문제, 최대 클릭 문제, 최대 서로 소 집합 문제(maximum independent set problem) 등의 여러 NP-완전 문제를 다항 시간 안에 해결할 수 있다.

완벽 그래프의 예[편집]

아래의 그래프들은 완벽 그래프의 예이다.

완벽 그래프의 특성[편집]

완벽 그래프가 어떤 그래프들인지 정확하게 파악하는 문제는 오랫동안 수학자들을 괴롭힌 어려운 문제였다.

완벽 그래프 정리 (1972, 로바스 (László Lovász))

어떤 그래프가 완벽 그래프일 필요충분조건은 그 그래프의 complement가 완벽 그래프라는 것이다.

강한 완벽 그래프 정리 (2002, 추드노프스키, 로버트슨, 씨이머, 토마스)

그래프가 완벽 그래프일 필요충분조건은 홀수 길이의 회로나 그 complement를 induced 부분 그래프로 가지지 않는다는 것이다.

강한 완벽 그래프 정리는 1960년에 클라우드 버지(Claude Berge)가 처음 제기한 것인데, 40년이상 미해결난제였다. 증명은 길고 복잡하다. 강한 완벽 그래프 정리가 제시하는 필요충분조건은 여원화(complementation)에 의해 보존되기 때문에, 강한 완벽 그래프 정리는 완벽 그래프 정리를 수반한다. 강한 완벽 그래프 정리가 증명된 이후 어떤 그래프가 완벽 그래프인지 확인하는 다항식 시간 알고리즘이 발견되었다.