완벽 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Paley9-perfect.svg|섬네일|완벽 그래프의 예. 만약 그래프에서 왼쪽 세 꼭짓점을 제외한 모든 꼭짓점을 지웠을 때 얻어지는 그래프(굵은 색)는 [[색칠수]]와 최대 [[클릭 (그래프 이론)|클릭]]의 크기가 같다. 다른 꼭짓점을 지웠을 때에도 마찬가지 결과가 얻어진다.]]
[[그래프 이론]]에서 '''완벽 그래프'''({{llang|en|perfect graph}})는 그 [[색칠수]]가 [[클릭 (그래프 이론)|클릭]]과 특별한 관계를 만족시키는 [[그래프]]이다.

== 정의 ==
'''완벽 그래프'''는 다음 성질을 만족시키는 (무향) 그래프 <math>\Gamma</math>이다.
* 모든 [[유도 부분 그래프]] <math>\tilde\Gamma\subset\Gamma</math>에 대하여, <math>\tilde\Gamma</math>에 속한 최대 [[클릭 (그래프 이론)|클릭]]의 크기는 <math>\tilde\Gamma</math>의 [[색칠수]]와 같다.

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

그래프 <math>\Gamma</math>에 대하여, 다음 세 조건들이 서로 [[동치]]이다.
* <math>\Gamma</math>는 완벽 그래프이다.
* <math>\Gamma</math>의 [[여 그래프]]는 완벽 그래프이다.
* <math>\Gamma</math>는 5 이상의 홀수 길이의 회로를 갖지 않는다. 또한, 모든 [[유도 부분 그래프]] <math>\tilde\Gamma</math>에 대하여, <math>\tilde\Gamma</math>의 [[여 그래프]]는 길이 5 이상의 홀수 길이의 회로가 아니다.
처음 두 조건의 동치는 '''약한 완벽 그래프 정리'''({{llang|en|weak perfect graph theorem}})이라고 하며, 세 번째 조건의 동치는 '''강한 완벽 그래프 정리'''({{llang|en|strong perfect graph theorem}})라고 한다. 세 번째 조건은 [[여 그래프]]에 대하여 불변이므로, 약한 완벽 그래프 정리는 강한 완벽 그래프 정리의 따름정리다.

세 번째 조건은 다항식 시간 [[알고리즘]]으로 구현할 수 있다.<ref>{{저널 인용
  | 이름 = Maria | 성= Chudnovsky|공저자=Gérard Cornuéjols, Xinming Liu, Paul Seymour, Kristina Vušković
  | 날짜 = 2005
  | title = Recognizing Berge graphs
  | 저널 = Combinatorica
  | volume = 25
  | issue = 2
  | pages = 143–186
  | doi = 10.1007/s00493-005-0012-8
  | 언어=en}}</ref> 즉, 완벽 그래프는 다항식 시간으로 식별할 수 있다.

양끝이 같은 변({{llang|en|self-loop}})이 없고, 두 꼭짓점 사이의 변의 수가 1개 이하인, 꼭짓점의 수가 <math>n=1,2,3,\dots</math>인 완벽 그래프의 수는 다음과 같다.
:1, 2, 4, 11, 33, 148, … {{OEIS|A052431}}
양끝이 같은 변({{llang|en|self-loop}})이 없고, 두 꼭짓점 사이의 변의 수가 1개 이하인, 꼭짓점의 수가 <math>n=1,2,3,\dots</math>인 연결 완벽 그래프의 수는 다음과 같다.
:1, 1, 2, 6, 20, 105, … {{OEIS|A052433}}

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

== 역사 ==
완벽 그래프의 개념의 시초는 걸러이 티보르({{llang|hu|Gallai Tibor}})의 1958년 논문이다. 이 논문에서 걸러이는 [[이분 그래프]]의 [[여 그래프]]가 완벽 그래프임을 증명하였다.

"완벽 그래프"라는 용어는 1963년에 클로드 베르주({{llang|fr|Claude Berge}})가 최초로 사용하였다. 이 논문에서 베르주는 강한 완벽 그래프 정리를 추측하였다. 약한 완벽 그래프 정리는 1972년에 [[로바스 라슬로]]가 증명하였다.<ref>{{저널 인용
 | last = Lovász | first = László | authorlink = 로바스 라슬로
 | 날짜 = 1972
 | title = Normal hypergraphs and the perfect graph conjecture
 | journal = Discrete Mathematics
 | volume = 2
 | issue = 3
 | pages = 253–267
 | doi = 10.1016/0012-365X(72)90006-4  | 언어= en}}</ref><ref>{{저널 인용
 | last = Lovász | first = László | authorlink = 로바스 라슬로
 | doi = 10.1016/0095-8956(72)90045-7
 | issue = 2
 | journal = Journal of Combinatorial Theory (Series B)
 | pages = 95–98
 | title = A characterization of perfect graphs
 | volume = 13
 | 날짜 = 1972 | 언어= en}}</ref>

강한 완벽 그래프 정리는 오랫동안 미해결 난제로 남아 있었다. 2002년에 마리아 추드노프스키({{llang|en|Maria Chudnovsky}}, {{llang|he|מריה צ'ודנובסקי}})와 닐 로버트슨({{llang|en|Neil Robertson}}, 폴 시모어({{llang|en|Paul Seymour}}), 로빈 토머스({{llang|en|Robin Thomas}})가 강한 완벽 그래프 정리의 증명을 발표하였고, 2006년에 출판하였다.<ref>{{저널 인용
  | 이름=Maria|성= Chudnovsky|공저자=Neil Robertson, Paul Seymour, Robin Thomas
  | 날짜 = 2006
  | title = The strong perfect graph theorem
  | journal = Annals of Mathematics
  | volume = 164 | issue = 1
  | pages = 51–229
  | doi = 10.4007/annals.2006.164.51 | mr = 2233847 | zbl=1112.05042
  | 언어=en}}</ref>

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|id=PerfectGraph|title=Perfect graph}}
* {{매스월드|id=PerfectGraphTheorem|title=Perfect graph theorem}}
* {{매스월드|id=StrongPerfectGraphTheorem|title=Strong perfect graph theorem}}

{{전거 통제}}
{{토막글|조합론}}

[[분류:완벽 그래프| ]]
[[분류:그래프 이론]]