완벽 그래프

그래프 이론에서 완벽 그래프()는 그 색칠수가 클릭과 특별한 관계를 만족시키는 그래프이다.

 정의 
완벽 그래프는 다음 성질을 만족시키는 (무향) 그래프 이다.
 모든 유도 부분 그래프 에 대하여, 에 속한 최대 클릭의 크기는 의 색칠수와 같다.

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

그래프 에 대하여, 다음 세 조건들이 서로 동치이다.
 는 완벽 그래프이다.
 의 여 그래프는 완벽 그래프이다.
 는 5 이상의 홀수 길이의 회로를 갖지 않는다. 또한, 모든 유도 부분 그래프 에 대하여, 의 여 그래프는 길이 5 이상의 홀수 길이의 회로가 아니다.
처음 두 조건의 동치는 약한 완벽 그래프 정리()이라고 하며, 세 번째 조건의 동치는 강한 완벽 그래프 정리()라고 한다. 세 번째 조건은 여 그래프에 대하여 불변이므로, 약한 완벽 그래프 정리는 강한 완벽 그래프 정리의 따름정리다.

세 번째 조건은 다항식 시간 알고리즘으로 구현할 수 있다. 즉, 완벽 그래프는 다항식 시간으로 식별할 수 있다.

양끝이 같은 변()이 없고, 두 꼭짓점 사이의 변의 수가 1개 이하인, 꼭짓점의 수가 인 완벽 그래프의 수는 다음과 같다.
1, 2, 4, 11, 33, 148, … 
양끝이 같은 변()이 없고, 두 꼭짓점 사이의 변의 수가 1개 이하인, 꼭짓점의 수가 인 연결 완벽 그래프의 수는 다음과 같다.
1, 1, 2, 6, 20, 105, … 

 예 
아래의 그래프들은 완벽 그래프의 예이다.
 이분 그래프
 (쾨니그의 정리) 이분 그래프의 선 그래프
 현 그래프
위 그래프들의 여 그래프 역시 완벽 그래프 정리에 의하여 완벽 그래프이다.

 역사 
완벽 그래프의 개념의 시초는 걸러이 티보르()의 1958년 논문이다. 이 논문에서 걸러이는 이분 그래프의 여 그래프가 완벽 그래프임을 증명하였다.

"완벽 그래프"라는 용어는 1963년에 클로드 베르주()가 최초로 사용하였다. 이 논문에서 베르주는 강한 완벽 그래프 정리를 추측하였다. 약한 완벽 그래프 정리는 1972년에 로바스 라슬로가 증명하였다.

강한 완벽 그래프 정리는 오랫동안 미해결 난제로 남아 있었다. 2002년에 마리아 추드노프스키(, )와 닐 로버트슨(, 폴 시모어(), 로빈 토머스()가 강한 완벽 그래프 정리의 증명을 발표하였고, 2006년에 출판하였다.

 각주 

 외부 링크 





분류:그래프 이론