완벽 그래프

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

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

정의[편집]

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

성질[편집]

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

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

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

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

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

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

1, 2, 4, 11, 33, 148, … (OEIS의 수열 A052431)

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

1, 1, 2, 6, 20, 105, … (OEIS의 수열 A052433)

[편집]

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

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

역사[편집]

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

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

강한 완벽 그래프 정리는 오랫동안 미해결 난제로 남아 있었다. 2002년에 마리아 추드노프스키(영어: Maria Chudnovsky, 히브리어: מריה צ'ודנובסקי)와 닐 로버트슨(영어: Neil Robertson, 폴 시모어(영어: Paul Seymour), 로빈 토머스(영어: Robin Thomas)가 강한 완벽 그래프 정리의 증명을 발표하였고, 2006년에 출판하였다.[4]

참고 문헌[편집]

  1. (영어) 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.
  2. (영어) 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.
  3. (영어) 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.
  4. (영어) 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. MR2233847. Zbl 1112.05042.

바깥 고리[편집]