완벽 그래프

완벽 그래프의 예. 만약 그래프에서 왼쪽 세 꼭짓점을 제외한 모든 꼭짓점을 지웠을 때 얻어지는 그래프(굵은 색)는 색칠수와 최대 클릭의 크기가 같다. 다른 꼭짓점을 지웠을 때에도 마찬가지 결과가 얻어진다.

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

정의

완벽 그래프는 다음 성질을 만족시키는 (무향) 그래프 $\mathrm{\Gamma }$이다.

• 모든 유도 부분 그래프 $\tilde{\mathrm{\Gamma }}\subset \mathrm{\Gamma }$에 대하여, $\tilde{\mathrm{\Gamma }}$에 속한 최대 클릭의 크기는 $\tilde{\mathrm{\Gamma }}$의 색칠수와 같다.

성질

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

그래프 $\mathrm{\Gamma }$에 대하여, 다음 세 조건들이 서로 동치이다.

• $\mathrm{\Gamma }$는 완벽 그래프이다.
• $\mathrm{\Gamma }$의 여 그래프는 완벽 그래프이다.
• $\mathrm{\Gamma }$는 5 이상의 홀수 길이의 회로를 갖지 않는다. 또한, 모든 유도 부분 그래프 $\tilde{\mathrm{\Gamma }}$에 대하여, $\tilde{\mathrm{\Gamma }}$의 여 그래프는 길이 5 이상의 홀수 길이의 회로가 아니다.

처음 두 조건의 동치는 약한 완벽 그래프 정리(틀:Llang)이라고 하며, 세 번째 조건의 동치는 강한 완벽 그래프 정리(틀:Llang)라고 한다. 세 번째 조건은 여 그래프에 대하여 불변이므로, 약한 완벽 그래프 정리는 강한 완벽 그래프 정리의 따름정리다.

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

양끝이 같은 변(틀:Llang)이 없고, 두 꼭짓점 사이의 변의 수가 1개 이하인, 꼭짓점의 수가 $n=1,2,3,\dots$인 완벽 그래프의 수는 다음과 같다.

1, 2, 4, 11, 33, 148, … 틀:OEIS

양끝이 같은 변(틀:Llang)이 없고, 두 꼭짓점 사이의 변의 수가 1개 이하인, 꼭짓점의 수가 $n=1,2,3,\dots$인 연결 완벽 그래프의 수는 다음과 같다.

1, 1, 2, 6, 20, 105, … 틀:OEIS

예

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

• 이분 그래프
• (쾨니그의 정리) 이분 그래프의 선 그래프
• 현 그래프

위 그래프들의 여 그래프 역시 완벽 그래프 정리에 의하여 완벽 그래프이다.

역사

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

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

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

외부 링크

• 틀:매스월드
• 틀:매스월드
• 틀:매스월드