그래프 이론에서 완벽 그래프는 모든 유도 부분 그래프(induced subgraph) $H$에 대해 색칠수 $\chi(H)$와 클릭수 $\omega(H)$가 같아지는 그래프를 말한다. 여기서 색칠수는 그래프의 꼭짓점을 인접한 꼭짓점이 다른 색을 갖도록 색칠하는 데 필요한 최소 색의 수이며, 클릭수는 그래프 내에서 모든 꼭짓점이 서로 연결된 완전 부분 그래프(clique) 중 가장 큰 것의 꼭짓점 수이다.
완벽 그래프는 조합 최적화 문제에서 중요한 역할을 하는데, 이는 이러한 그래프의 색칠 문제나 클릭 문제 등 NP-완전으로 알려진 많은 문제가 다항 시간 안에 해결될 수 있기 때문이다.
주요 정리
-
약한 완벽 그래프 정리 (Weak Perfect Graph Theorem): 그래프 $G$가 완벽 그래프이면 그 보수 그래프(complement graph) $G^c$도 완벽 그래프이다. 이 정리는 1972년 라슬로 로바스(László Lovász)에 의해 증명되었다. 이는 완벽 그래프의 정의에서 대칭성이 존재함을 보여준다.
-
강한 완벽 그래프 정리 (Strong Perfect Graph Theorem): 그래프 $G$가 완벽 그래프인 것은, $G$가 홀수 구멍(odd hole)이나 홀수 반구멍(odd antihole)을 유도 부분 그래프로 포함하지 않는 것과 동치이다. 여기서 '홀수 구멍'은 홀수 길이의 유도 순환(induced cycle)을 의미하며, '홀수 반구멍'은 홀수 길이의 유도 순환의 보수 그래프를 의미한다. 이 정리는 오랫동안 강한 완벽 그래프 추측(Strong Perfect Graph Conjecture)으로 알려져 있었으며, 2006년 마리아 추바탈(Maria Chudnovsky), 닐 로버트슨(Neil Robertson), 폴 시모어(Paul Seymour), 로빈 토마스(Robin Thomas) 등에 의해 증명되었다. 이 정리는 완벽 그래프의 특성을 완전히 분류하는 데 중요한 기여를 했다.
완벽 그래프의 종류
여러 중요한 그래프 클래스들이 완벽 그래프에 속한다. 이분 그래프(bipartite graph), 현 그래프(chordal graph), 비교 가능 그래프(comparability graph), 간격 그래프(interval graph) 등이 그 예시이다. 이들은 각각 고유한 구조적 특성을 가지고 있으며, 그 특성으로 인해 완벽 그래프의 조건을 만족한다.
활용
완벽 그래프 이론은 그래프 알고리즘, 조합 최적화, 전산학 등 다양한 분야에서 활용된다. 특히, 완벽 그래프의 성질은 그래프 색칠 문제의 해를 찾는 데 효율적인 알고리즘을 설계하는 데 기반을 제공한다. 예를 들어, 자원 할당, 스케줄링, 통신 네트워크 설계와 같은 실제 문제들은 그래프 색칠 문제로 모델링될 수 있으며, 해당 그래프가 완벽 그래프라면 효율적인 해결책을 찾을 수 있다.