완벽 그래프
그래프 이론에서 완벽 그래프(영어: perfect graph)는 그 색칠수가 클릭과 특별한 관계를 만족시키는 그래프이다.
정의
편집완벽 그래프는 다음 성질을 만족시키는 (무향) 그래프 이다.
성질
편집완벽 그래프에서는 그래프 색칠 문제, 최대 클릭 문제, 최대 서로 소 집합 문제(maximum independent set problem) 등의 여러 NP-완전 문제를 다항 시간 안에 해결할 수 있다.
그래프 에 대하여, 다음 세 조건들이 서로 동치이다.
- 는 완벽 그래프이다.
- 의 여 그래프는 완벽 그래프이다.
- 는 5 이상의 홀수 길이의 회로를 갖지 않는다. 또한, 모든 유도 부분 그래프 에 대하여, 의 여 그래프는 길이 5 이상의 홀수 길이의 회로가 아니다.
처음 두 조건의 동치는 약한 완벽 그래프 정리(영어: weak perfect graph theorem)이라고 하며, 세 번째 조건의 동치는 강한 완벽 그래프 정리(영어: strong perfect graph theorem)라고 한다. 세 번째 조건은 여 그래프에 대하여 불변이므로, 약한 완벽 그래프 정리는 강한 완벽 그래프 정리의 따름정리다.
세 번째 조건은 다항식 시간 알고리즘으로 구현할 수 있다.[1] 즉, 완벽 그래프는 다항식 시간으로 식별할 수 있다.
양끝이 같은 변(영어: self-loop)이 없고, 두 꼭짓점 사이의 변의 수가 1개 이하인, 꼭짓점의 수가 인 완벽 그래프의 수는 다음과 같다.
양끝이 같은 변(영어: self-loop)이 없고, 두 꼭짓점 사이의 변의 수가 1개 이하인, 꼭짓점의 수가 인 연결 완벽 그래프의 수는 다음과 같다.
예
편집아래의 그래프들은 완벽 그래프의 예이다.
위 그래프들의 여 그래프 역시 완벽 그래프 정리에 의하여 완벽 그래프이다.
역사
편집완벽 그래프의 개념의 시초는 걸러이 티보르(헝가리어: Gallai Tibor)의 1958년 논문이다. 이 논문에서 걸러이는 이분 그래프의 여 그래프가 완벽 그래프임을 증명하였다.
"완벽 그래프"라는 용어는 1963년에 클로드 베르주(프랑스어: Claude Berge)가 최초로 사용하였다. 이 논문에서 베르주는 강한 완벽 그래프 정리를 추측하였다. 약한 완벽 그래프 정리는 1972년에 로바스 라슬로가 증명하였다.[2][3]
강한 완벽 그래프 정리는 오랫동안 미해결 난제로 남아 있었다. 2002년에 마리아 추드노프스키(영어: Maria Chudnovsky, 히브리어: מריה צ'ודנובסקי)와 닐 로버트슨(영어: Neil Robertson, 폴 시모어(영어: Paul Seymour), 로빈 토머스(영어: Robin Thomas)가 강한 완벽 그래프 정리의 증명을 발표하였고, 2006년에 출판하였다.[4]
각주
편집- ↑ Chudnovsky, Maria; Gérard Cornuéjols, Xinming Liu, Paul Seymour, Kristina Vušković (2005). “Recognizing Berge graphs”. 《Combinatorica》 (영어) 25 (2): 143–186. doi:10.1007/s00493-005-0012-8.
- ↑ Lovász, László (1972). “Normal hypergraphs and the perfect graph conjecture”. 《Discrete Mathematics》 (영어) 2 (3): 253–267. doi:10.1016/0012-365X(72)90006-4.
- ↑ Lovász, László (1972). “A characterization of perfect graphs”. 《Journal of Combinatorial Theory (Series B)》 (영어) 13 (2): 95–98. doi:10.1016/0095-8956(72)90045-7.
- ↑ Chudnovsky, Maria; Neil Robertson, Paul Seymour, Robin Thomas (2006). “The strong perfect graph theorem”. 《Annals of Mathematics》 (영어) 164 (1): 51–229. doi:10.4007/annals.2006.164.51. MR 2233847. Zbl 1112.05042.
외부 링크
편집- Weisstein, Eric Wolfgang. “Perfect graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “Perfect graph theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “Strong perfect graph theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.