완벽 그래프

3. 역사

완벽 그래프 개념은 헝가리의 수학자 걸러이 티보르(Gallai Tibor^hu)가 1958년에 발표한 논문에서 처음 나타났다. 이 논문에서 걸러이는 이분 그래프의 여 그래프가 완벽 그래프임을 증명하였다.

"완벽 그래프"라는 용어는 1963년 프랑스의 수학자 클로드 베르주(Claude Berge^프랑스어)가 처음으로 사용하였다. 베르주는 이 논문에서 강한 완벽 그래프 정리를 추측하였다. 약한 완벽 그래프 정리는 1972년에 헝가리의 수학자 로바스 라슬로가 증명하였다.^[3][4]

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

4. 종류

이분 그래프, 현 그래프 등 여러 종류의 그래프가 완벽 그래프에 속한다. 이러한 그래프들은 조합 구조에 대한 최소-최대 정리와 관련이 있는 경우가 많다. 예를 들어, 이분 그래프와 그 선 그래프의 완벽성은 쾨니그의 정리와 관련이 있고, 비교 가능 그래프의 완벽성은 딜워스의 정리 및 미르스키의 정리와 관련이 있다.

구간 그래프는 실수선상의 구간 집합에 의해 정의된 순서인 구간 순서의 비교 불가능성 그래프이다. $x\backslash le\; y$는 구간 $x$가 구간 $y$의 왼쪽에 완전히 있을 때 성립한다. 해당 구간 그래프에서 두 구간이 공통점을 가질 때마다 $x$에서 $y$로 변이 있다. 이러한 그래프의 채색은 각 작업의 예약된 시간을 설명하는 구간을 사용하여 (교실을 수업에 할당하는 것과 같은) 작업에 자원을 할당하는 문제를 모델링하는 데 사용될 수 있다. 구간 그래프와 순열 그래프는 모두 사다리꼴 그래프에 의해 일반화된다. 두 구간이 중첩되지 않는 구간 시스템은 무관심 그래프를 생성하며, 이는 반순서의 비교 불가능성 그래프이다. 이는 항목이 서로 매우 유사한 효용성을 가질 때 비교 불가능할 것이라는 가정 하에 인간의 선호를 모델링하는 데 사용되었다. 모든 쌍이 중첩되거나 분리된 구간은 자명하게 완전한 그래프를 생성하며, 정렬된 트리의 비교 가능성 그래프이다. 이 그래프에서 독립 수는 최대 클릭의 수와 같다.

거리-유전 그래프는 단일 정점 그래프에서 시작하여 차수 1 정점("매달린 정점") 또는 기존 정점의 복사본(동일한 이웃을 가짐)을 반복적으로 추가하여 형성된다. 각 정점과 해당 복사본은 인접할 수도 있고('진짜 쌍둥이'), 인접하지 않을 수도 있다('가짜 쌍둥이'). 이러한 그래프의 모든 연결된 유도된 부분 그래프에서 정점 간의 거리는 전체 그래프와 동일하다. 쌍둥이 연산만 사용하면 코그래프가 된다. 코그래프는 직렬-병렬 부분 순서의 비교 가능 그래프이며, 보수 및 그래프의 분리 합집합을 결합하는 다른 구성 과정을 통해 형성될 수도 있다.

현 그래프와 거리-유전 그래프를 모두 갖는 그래프는 프톨레마이오스 그래프라고 불리며, 그 거리는 프톨레마이오스 부등식을 따른다. 여기에는 제한된 형태의 거리-유전 구성 시퀀스가 있는데, 가짜 쌍둥이는 해당 이웃이 클릭을 형성할 때만 추가할 수 있다. 여기에는 단일 정점에서 연결된 클릭으로 구성된 풍차 그래프와 각 양방향 연결된 구성 요소가 클릭인 블록 그래프가 특별한 경우로 포함된다.

임계 그래프는 빈 그래프에서 반복적으로 고립 정점(다른 정점과 연결되지 않음) 또는 보편 정점(다른 모든 정점과 연결됨)을 추가하여 형성된다. 이는 분할 그래프와 자명하게 완전한 그래프의 특수한 경우이다. 이들은 정확히 자명하게 완전하고 자명하게 완전한 그래프의 보수이고, 코그래프이자 분할 그래프이기도 하다.

거리-유전 그래프의 정점이 점진적 구성 시퀀스의 순서로 채색되면 결과 채색은 최적이 된다. 비교 가능 그래프의 정점이 기본 부분 순서의 선형 확장 순서로 채색되면 결과 채색은 최적이 된다. 이 속성은 완전하게 순서화 가능한 그래프로 일반화되는데, 이는 유도된 부분 그래프로 제한될 때 탐욕적 채색이 최적이 되도록 하는 순서가 존재하는 그래프이다. 코그래프는 모든 정점 순서가 이 속성을 갖는 그래프이다. 완전하게 순서화 가능한 그래프의 또 다른 하위 클래스는 구간 그래프의 일반화인 허용 오차 그래프의 보수이다.

라인 완전 그래프 $L(G)$의 기본 그래프 $G$는 이중 연결된 구성 요소가 이분 그래프, 완전 그래프 $K\_4$, 삼각 책인 그래프이다. 이 구성 요소는 완전하며, 이들의 조합은 완전성을 유지하므로 모든 라인 완전 그래프는 완전하다.^[4]

분할 그래프는 클릭과 독립 집합으로 분할할 수 있는 그래프이다. 최대 클릭의 각 정점에 서로 다른 색상을 할당한 다음, 나머지 각 정점을 인접하지 않은 클릭 정점과 같은 색상으로 칠하여 색칠할 수 있다. 따라서 이러한 그래프는 클릭 수와 채색수가 같으며, 완전 그래프이다. 더 넓은 범위의 그래프인 ''단극 그래프''는 클릭과 클리크의 분리된 합집합인 클러스터 그래프로 분할될 수 있다. 여기에는 클러스터 그래프가 단일 클릭인 이분 그래프도 포함된다. 단극 그래프와 그 여집합은 함께 ''일반화된 분할 그래프''의 클래스를 형성한다. 대부분의 완전 그래프는 일반화된 분할 그래프이다. 즉, 완전한 $n$ 정점 그래프 중에서 일반화된 분할 그래프인 그래프의 비율은 $n$이 임의로 커짐에 따라 극한에서 1로 수렴한다.

대부분의 완전 그래프의 다른 극한적 특성은 일반화된 분할 그래프를 연구하여 결정할 수 있다. 이러한 방식으로, 거의 모든 완전 그래프가 해밀턴 사이클을 포함한다는 것이 밝혀졌다. $H$가 임의의 그래프인 경우, $H$가 큰 무작위 완전 그래프의 유도된 부분 그래프로 나타날 극한 확률은 $H$가 일반화된 분할 그래프가 아닌 경우, 단극 또는 공동 단극이지만 둘 다 아닌 경우, 또는 둘 다 단극 및 공동 단극인 경우 각각 0, 1/2 또는 1이다.

강하게 완벽한 그래프는 모든 유도 부분 그래프에서 모든 극대 클릭과 교차하는 독립 집합이 존재하는 그래프이다. Meyniel 그래프 또는 ''매우 강하게 완벽한 그래프''에서는 모든 정점이 그러한 독립 집합에 속한다. Meyniel 그래프는 길이가 5 이상인 모든 홀수 사이클에 최소 두 개의 현이 있는 그래프로도 특징지을 수 있다.

패리티 그래프는 모든 두 정점 사이에서 모든 유도 경로가 동일한 패리티를 갖는다는 속성으로 정의된다. 즉, 길이가 모두 짝수이거나 모두 홀수이다. 여기에는 두 정점 사이의 모든 유도 경로가 동일한 길이를 갖는 거리-유전 그래프와 두 정점 사이의 모든 경로(유도 경로뿐 아니라)가 동일한 패리티를 갖는 이분 그래프가 포함된다. 패리티 그래프는 Meyniel 그래프이므로 완벽하다. 긴 홀수 사이클에 현이 하나만 있다면 현의 끝점 사이의 사이클의 두 부분은 서로 다른 패리티의 유도 경로가 될 것이다. 모든 패리티 그래프의 프리즘(단일 에지와의 데카르트 곱)은 또 다른 패리티 그래프이며, 패리티 그래프는 프리즘이 완벽한 유일한 그래프이다.

4. 1. 이분 그래프

이분 그래프 (가장자리 하나 이상)에서 채색수와 클릭수는 모두 2와 같다. 유도된 부분 그래프는 이분 그래프로 유지되므로 이분 그래프는 완벽 그래프이다.^[1] 이분 그래프는 완전 그래프이며, 트리와 중앙 그래프가 그 예이다.^[2] 완전 그래프 정리에 따르면 이분 그래프에서 최대 독립 집합의 크기는 최소 클릭 커버의 크기와 같다. 최대 독립 집합은 모든 가장자리를 포함하는 정점 집합인 최소 정점 커버의 여집합이다. 최소 클릭 커버는 최대 매칭 (가능한 한 많은 분리된 가장자리)과 나머지 모든 정점에 대한 단일 정점 클릭으로 구성되며, 크기는 정점 수에서 매칭 가장자리 수를 뺀 것이다. 따라서 이 등식은 이분 그래프에서 최대 매칭의 크기와 최소 정점 커버의 크기 사이의 등식, 즉 쾨니그의 정리의 일반적인 공식으로 표현할 수 있다.^[3]

어떤 그래프 $G$에서 매칭은 라인 그래프 $L(G)$에서 독립 집합과 같다. $L(G)$는 $G$의 각 가장자리에 대해 정점을 갖고, $G$에서 공통 끝점을 공유하는 각 가장자리의 쌍에 대해 $L(G)$에서 두 정점 사이에 가장자리를 갖는 그래프이다. 라인 그래프는 두 종류의 클릭을 갖는데, 공통 끝점을 갖는 $G$의 가장자리 집합과 $G$의 삼각형이다. 이분 그래프에는 삼각형이 없으므로 $L(G)$의 클릭 커버는 $G$의 정점 커버에 해당한다. 따라서 이분 그래프의 라인 그래프에서 독립수와 클릭 커버 수는 같다. 이분 그래프의 라인 그래프의 유도된 부분 그래프는 부분 그래프의 라인 그래프이므로 이분 그래프의 라인 그래프는 완전 그래프이다.^[4] 룩의 그래프와 완전 이분 그래프의 라인 그래프가 그 예시이다. 모든 이분 그래프의 라인 그래프는 룩의 그래프의 유도된 부분 그래프이다.^[5]

이분 그래프의 라인 그래프는 완전 그래프이므로 클릭 수는 채색수와 같다. 이분 그래프의 라인 그래프의 클릭 수는 기본 이분 그래프의 모든 정점의 최대 차수이다. 이분 그래프의 라인 그래프의 채색수는 기본 이분 그래프의 채색 지수이며, 인접한 가장자리가 서로 다른 색상을 갖도록 가장자리를 색칠하는 데 필요한 최소 색상 수이다. 각 색상 클래스는 매칭을 형성하며, 채색 지수는 모든 가장자리를 덮는 데 필요한 최소 매칭 수이다. 이분 그래프에서 최대 차수와 채색 지수의 등식은 데네스 쾨니그의 또 다른 정리이다. 임의의 단순 그래프에서는 이 둘의 값이 1만큼 다를 수 있는데, 이것은 비징의 정리이다.^[4]

4. 2. 현 그래프

현 그래프는 정점이 추가될 때 그 이웃이 클릭을 형성하는 방식으로 점진적으로 구성되는 그래프이다. 현 그래프는 짝수 또는 홀수의 구멍(유도 순환)이 없는 그래프로도 특징지을 수 있다. 숲, 구간 그래프, 최대 외평면 그래프 등은 현 그래프의 특수한 예시이다. 분할 그래프는 현 그래프이면서 동시에 현 그래프의 보 그래프인 그래프이다. -트리는 트리 너비를 정의할 때 핵심적인 요소로 사용되며, k+1개의 정점으로 구성된 클릭에서 시작하여 동일한 크기의 클릭을 형성하는 정점을 반복적으로 추가하는 방식으로 형성된 현 그래프이다.

현 그래프의 정점에 탐욕적 채색 알고리즘을 적용하여 점진적 구성 시퀀스의 순서대로 채색하면 최적의 채색 결과를 얻는다. 이 구성 과정에서 사용된 정점 순서의 역순은 '제거 순서'라고 불린다.

4. 3. 비교가능 그래프

부분 순서 집합은 원소 집합과 비교 관계 $\backslash le$로 정의되며, 이 관계는 반사적(모든 원소 $x$에 대해, $x\backslash le\; x$), 반대칭적(만약 $x\backslash le\; y$이고 $y\backslash le\; x$이면, $x=y$), 추이적(만약 $x\backslash le\; y$이고 $y\backslash le\; z$이면, $x\backslash le\; z$)이다. 원소 $x$와 $y$가 $x\backslash le\; y$ 또는 $y\backslash le\; x$이면 "비교 가능"하고, 그렇지 않으면 "비교 불가능"하다. 예를 들어, 집합 포함 ($\backslash subseteq$)은 모든 집합족을 부분적으로 순서화한다. 부분 순서 집합의 비교 가능성 그래프는 부분 순서 집합의 원소를 꼭짓점으로 가지며, 비교 가능한 임의의 두 원소를 연결하는 변을 갖는다. 그 여집합은 "비교 불가능성 그래프"라고 한다. 서로 다른 부분 순서는 동일한 비교 가능성 그래프를 가질 수 있다. 예를 들어, 모든 비교를 반전시키면 순서는 변경되지만 그래프는 변경되지 않는다.

유한한 비교 가능성 그래프 (및 그 여집합인 비교 불가능성 그래프)는 항상 완전 그래프이다.^[1] 비교 가능성 그래프에서 클릭은 쌍으로 비교 가능한 원소의 부분 집합에서 발생하며, 이러한 부분 집합을 사슬이라고 하며, 주어진 부분 순서에 의해 선형적으로 정렬된다. 독립 집합은 비교 불가능한 원소의 부분 집합에서 발생하며, 이러한 부분 집합을 반사슬이라고 한다. 예를 들어, 예시된 부분 순서 및 비교 가능성 그래프에서 $\backslash \{A,B,C\backslash \}$는 순서에서 사슬이고 그래프에서 클릭인 반면, $\backslash \{C,D\backslash \}$는 순서에서 반사슬이고 그래프에서 독립 집합이다. 따라서, 비교 가능성 그래프의 채색은 원소를 반사슬로 분할하는 것이고, 클릭 커버는 원소를 사슬로 분할하는 것이다. 부분 순서 이론의 딜워스 정리는 모든 유한 부분 순서에 대해 가장 큰 반사슬의 크기가 원소를 분할할 수 있는 최소 사슬 수와 같다고 명시한다. 그래프 언어로 표현하면 다음과 같다. 모든 유한 비교 가능성 그래프는 완전 그래프이다. 마찬가지로 미르스키의 정리는 모든 유한 부분 순서에 대해 가장 큰 사슬의 크기가 원소를 분할할 수 있는 최소 반사슬 수와 같다고 명시하며, 즉 모든 유한 비교 불가능성 그래프는 완전 그래프이다. 이 두 정리는 완전 그래프 정리를 통해 동등하지만, 미르스키의 정리가 딜워스 정리보다 직접 증명하기 더 쉽다. 각 원소에 대해 해당 원소가 최대인 가장 큰 사슬의 크기로 레이블을 지정하면, 동일한 레이블을 가진 부분 집합은 반사슬로 분할되며, 반사슬의 수는 전체적으로 가장 큰 사슬의 크기와 같다.^[2] 모든 이분 그래프는 비교 가능성 그래프이다. 따라서, 쾨니그의 정리는 완전 그래프 이론을 통해 연결된 딜워스 정리의 특수한 경우로 볼 수 있다.^[3]

4. 4. 기타 완벽 그래프

• 이분 그래프
• (쾨니그의 정리) 이분 그래프의 선 그래프
• 현 그래프

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

분할 그래프는 클리크와 독립 집합으로 분할할 수 있는 그래프이다. 최대 클리크의 각 정점에 서로 다른 색상을 할당한 다음, 나머지 각 정점을 인접하지 않은 클리크 정점과 같은 색상으로 칠하여 색칠할 수 있다. 따라서 이러한 그래프는 클리크 수와 채색수가 같으며, 완전 그래프이다. 더 넓은 범위의 그래프인 ''단극 그래프''는 클리크와 클리크의 분리된 합집합인 클러스터 그래프로 분할될 수 있다. 여기에는 클러스터 그래프가 단일 클리크인 이분 그래프도 포함된다. 단극 그래프와 그 여집합은 함께 ''일반화된 분할 그래프''의 클래스를 형성한다. 대부분의 완전 그래프는 일반화된 분할 그래프이다. 즉, 완전한 $n$ 정점 그래프 중에서 일반화된 분할 그래프인 그래프의 비율은 $n$이 임의로 커짐에 따라 극한에서 1로 수렴한다.

대부분의 완전 그래프의 다른 극한적 특성은 일반화된 분할 그래프를 연구하여 결정할 수 있다. 이러한 방식으로, 거의 모든 완전 그래프가 해밀턴 사이클을 포함한다는 것이 밝혀졌다. $H$가 임의의 그래프인 경우, $H$가 큰 무작위 완전 그래프의 유도된 부분 그래프로 나타날 극한 확률은 $H$가 일반화된 분할 그래프가 아닌 경우, 단극 또는 공동 단극이지만 둘 다 아닌 경우, 또는 둘 다 단극 및 공동 단극인 경우 각각 0, 1/2 또는 1이다.

강하게 완벽한 그래프는 모든 유도 부분 그래프에서 모든 극대 클릭과 교차하는 독립 집합이 존재하는 그래프이다. Meyniel 그래프 또는 ''매우 강하게 완벽한 그래프''에서는 모든 정점이 그러한 독립 집합에 속한다. Meyniel 그래프는 길이가 5 이상인 모든 홀수 사이클에 최소 두 개의 현이 있는 그래프로도 특징지을 수 있다.

패리티 그래프는 모든 두 정점 사이에서 모든 유도 경로가 동일한 패리티를 갖는다는 속성으로 정의된다. 즉, 길이가 모두 짝수이거나 모두 홀수이다. 여기에는 두 정점 사이의 모든 유도 경로가 동일한 길이를 갖는 거리-유전 그래프와 두 정점 사이의 모든 경로(유도 경로뿐 아니라)가 동일한 패리티를 갖는 이분 그래프가 포함된다. 패리티 그래프는 Meyniel 그래프이므로 완벽하다. 긴 홀수 사이클에 현이 하나만 있다면 현의 끝점 사이의 사이클의 두 부분은 서로 다른 패리티의 유도 경로가 될 것이다. 모든 패리티 그래프의 프리즘(단일 에지와의 데카르트 곱)은 또 다른 패리티 그래프이며, 패리티 그래프는 프리즘이 완벽한 유일한 그래프이다.

5. 알고리즘

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

그래프 $\backslash Gamma$가 완벽 그래프이기 위한 세 가지 조건은 다음과 같으며, 이들은 서로 동치이다.^[2]

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

참조

_[1] Harvtxt
_[2] 저널 Recognizing Berge graphs 2005
_[3] 저널 Normal hypergraphs and the perfect graph conjecture 1972
_[4] 저널 A characterization of perfect graphs 1972
_[5] 저널 The strong perfect graph theorem 2006