완벽 그래프

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

정의 편집

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

모든 유도 부분 그래프 ${\tilde {\Gamma }}\subset \Gamma$ 에 대하여, ${\tilde {\Gamma }}$ 에 속한 최대 클릭의 크기는 ${\tilde {\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]

참고 문헌 편집

↑ 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.

[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. MR 2233847. Zbl 1112.05042.

[1]

[2]

[3]

[4]