퍼펙트 그래프

순서 9의 Paley 그래프는 세 가지 색으로 색칠되고 세 가지 꼭지점의 집단을 보여준다. 이 그래프와 각각의 유도 하위 그래프에서 색소수는 클릭 수와 같기 때문에 완벽한 그래프다.

그래프 이론에서, 완벽한 그래프는 모든 유도 서브그래프의 색도수가 그 서브그래프의 가장 큰 클라이크(클라이크 수)의 순서와 같은 그래프다. Equivalently stated in symbolic terms an arbitrary graph $G=(V,E)$ is perfect if and only if for all $S\subseteq V$ we have $\chi (G[S])=\omega (G[S])$ .

완벽한 그래프는 많은 중요한 그래프 패밀리를 포함하며, 그러한 패밀리의 색상 및 패밀리와 관련된 결과를 통합하는 역할을 한다. 예를 들어, 모든 완벽한 그래프에서 그래프 색칠 문제, 최대 클라이크 문제, 최대 독립 집합 문제는 다항 시간 내에 모두 해결될 수 있다. 또한 딜워스의 정리처럼 조합학에서 몇 가지 중요한 최소-최대 이론은 특정 관련 그래프의 완성도 측면에서 표현될 수 있다.

그래프 $G$ ${\$ $displaystyle$ $G}$ 은 $\chi (G)=\omega (G)$ ( G $\chi (G)=\omega (G)$ ) $\chi (G)=\omega (G)$ = $\chi (G)=\omega (G)$ ( $\chi (G)=\omega (G)$ ) $\chi (G)=\omega (G)$ 인 경우에만 1-완벽하다 $G$ $\chi (G)=\omega (G)$ 그러면 $G$ ${\$ $displaystyle$ $G}$ 의 모든 하위 그래프가 1-완벽한 경우에만 $G$ 완벽하다 $G$ .

특성.

완벽한 그래프 정리에 의해 $그래프$ G{\ $displaystyle G$ }은(는) ${\bar {G}}$ 인 G ${\$ 이(가) 완벽할 ${\bar {G}}$ 경우에만 완벽하다 $G$ .
강력하고 완벽한 그래프 정리를 통해 완벽한 그래프는 Berge 그래프와 동일하며, $G$ ${\displaystyle G$ ${\bar {G}}$ 과 $G$ (와) ${\bar {G}}$ ${\$ 이(가) 모두 홀수 길이 5 이상의 유도 사이클을 포함하지 ${\bar {G}}$ 않는 그래프 $G$ $G$ $G$ 이다.

자세한 내용은 아래 절을 참조하십시오.

역사

현대 언어로 된 Tibor Gallai의 1958년 결과로부터 개발된 완벽한 그래프 이론은 초당적 그래프의 보완이 완벽하다고 해석할 수 있다; 이 결과는 또한 Kignig의 정리와 간단한 등가로서, 초당적 그래프의 일치점과 정점 커버와 관련된 훨씬 이전의 결과로 볼 수 있다. "완벽한 그래프"라는 문구를 처음 사용한 것은 1963년 클로드 버지의 논문이며, 그 뒤에 버지 그래프의 이름이 붙는다. 이 논문에서 그는 완벽한 그래프를 정의함으로써 갈라이의 결과를 몇 가지 유사한 결과로 통일시켰고, 그는 완벽한 그래프와 버지 그래프 정의의 등가성을 추측했다; 그의 추측은 2002년에 강력한 완벽한 그래프 정리로서 증명되었다.

완벽한 그래프 패밀리

더 잘 알려진 완벽한 그래프 중 일부는 다음과 같다.^[2]

초당적 그래프: 포리스트(주기가 없는 그래프)를 포함하여 두 가지 색상으로 색칠할 수 있는 그래프.
초당적 그래프의 선 그래프(Kőnig의 정리 참조). Rook의 그래프(완전한 초당적 그래프의 선 그래프)는 특별한 경우다.
코드 그래프, 4개 이상의 정점 사이의 모든 주기에 연속되지 않은 두 정점 사이의 가장자리인 화음을 갖는 그래프. 여기에는 다음이 포함된다.
- 포리스트, k-through(특정 트리 너비가 있는 수직 그래프)
- 분할 그래프(클릭 및 독립 집합으로 분할할 수 있는 그래프)
- 블록 그래프(모든 이코넥트 구성요소가 클라이크인 경우),
- Ptolemaic 그래프(Ptolemy의 불평등을 거리가 따르는 그래프)
- 구간 그래프(각 꼭지점이 선의 구간을 나타내고 각 가장자리가 두 구간 사이의 비어 있지 않은 교차점을 나타내는 값)
- 단순하게 완벽한 그래프(내포된 구간에 대한 그래프), 분계점 그래프(총 중량이 숫자 임계값을 초과할 때 두 정점이 인접하는 그래프)
- 풍차 그래프(공통 꼭지점에서 동일한 패밀리를 결합하여 형성됨),
- 및 강한 화음 그래프(길이가 6 이상일 때마다 고른 화음을 갖는 화음 그래프).
비교가능성 그래프는 요소 쌍이 부분 순서로 연관될 때마다 엣지로 연결함으로써 부분 순서 집합에서 형성된다. 여기에는 다음이 포함된다.
- 초당적 그래프, 간격 그래프의 보완, 약간 완벽한 그래프, 분계점 그래프, 풍차 그래프,
- 순열 그래프(가장자리가 순열에 의해 역행되는 요소 쌍을 나타내는 표시)
- 및 cographs(분리된 결합과 보완의 재귀적 운영에 의해 형성됨)
완벽하게 정렬 가능한 그래프, 즉 모든 유도 서브그래프에서 탐욕스러운 컬러링 알고리즘이 최적의 방식으로 정렬할 수 있는 그래프. 여기에는 초당적 그래프, 화음 그래프, 비교가능성 그래프,
- 거리 측정 그래프(연결된 유도 하위 그래프의 최단 경로 거리가 전체 그래프의 최단 경로 거리와 동일함)
- 정점 수가 홀수인 휠 그래프.
사다리꼴 그래프 - 가장자리의 평행 쌍이 두 개의 평행선에 놓여 있는 사다리꼴의 교차 그래프. 여기에는 구간 그래프, 사소한 것으로 완벽한 그래프, 분계점 그래프, 풍차 그래프, 순열 그래프가 포함된다. 이들의 보완은 비교가능성 그래프의 하위 집합이다.

최소-최대 정리와의 관계

모든 그래프에서, clique 번호는 clique의 모든 정점이 적절한 색상에서 구별되는 색상을 할당해야 하기 때문에 색채 수에 대한 하한을 제공한다. 완벽한 그래프는 그래프 자체에서뿐만 아니라 모든 유도 하위 그래프에서 이 하한이 타이트한 그래프들이다. 완벽하지 않은 그래프의 경우 색수와 클릭 수가 다를 수 있다. 예를 들어, 길이 5의 사이클은 적절한 색상에 세 가지 색상이 필요하지만 가장 큰 클릭은 크기가 2이다.

한 등급의 그래프가 완벽하다는 증거는 최소-최대 정리라고 볼 수 있다: 이러한 그래프에 필요한 최소 색 수는 한 집단의 최대 크기와 같다. 조합학에서 많은 중요한 최소-최대 이론들은 이 용어로 표현될 수 있다. 예를 들어, 딜워스의 정리에서는 부분적으로 순서가 정해진 체인에 있는 칸막이의 최소 체인 수는 반창고의 최대 크기와 같으며, 비교가능성 그래프의 보완이 완벽하다고 진술하는 것으로 바꾸어 말할 수 있다. 미르스키의 정리에서는 한 칸막이로 분할된 반동물의 최소 수는 체인의 최대 크기와 같으며, 비교가능성 그래프의 완성도와 같은 방식으로 대응한다고 명시하고 있다.

순열 그래프의 완전성은 정렬된 원소의 모든 시퀀스에서 가장 긴 감소 부분들의 길이가 파티션의 최소 시퀀스 수와 같다는 문구와 동일하다. Erdős-Szekeres 정리는 이 진술의 쉬운 결과물이다.

Kőnig의 그래프 이론의 정리는 초당적 그래프의 최소 꼭지점 표지가 최대 일치에 해당하며, 그 반대의 경우도 최대 일치에 해당한다고 기술하고 있다; 그것은 초당적 그래프의 보완의 완벽함으로 해석할 수 있다. 초당적 그래프에 대한 또 다른 정리는 색도 지수가 최대 정도와 같다는 것으로, 초당적 그래프의 선 그래프의 완성도와 같다.

특성화 및 완벽한 그래프 구성

완벽한 그래프에 대한 그의 초기 연구에서, 버지는 나중에야 증명된 그들의 구조에 대해 두 가지 중요한 추측을 했다.

이 두 가지 정리 중 첫 번째는 로바스(1972년)의 완벽한 그래프 정리였는데, 그래프의 보완이 완벽해야 완벽하다고 명시했다. 따라서 완벽성(유도된 모든 하위 그래프에서 최대 클라이크 크기와 색수의 동일성으로 정의됨)은 최대 독립 집합 크기 및 클라이크 커버 숫자의 동일성과 동일하다.

7-Vertex 사이클과 그 보완재로서, 각각의 경우에서 최적의 색상과 최대 클라이크(가장자리가 무겁다)를 보여준다. 어느 그래프도 그것의 클라이크 크기와 동일한 수의 색상을 사용하므로, 어느 그래프도 완벽하지 않다.

버지에 의해 추측된 두 번째 정리는 완벽한 그래프의 금지된 그래프 특성을 제공했다. 최소 5 $이상$ 의 홀수 길이의 유도 주기를 홀수 구멍이라고 한다. 홀수 구멍의 보완물인 유도 서브그래프를 홀수 안티홀이라고 한다. 길이가 $3$ 보다 큰 홀수 주기는 완벽할 수 없다. 왜냐하면 색수는 3이고 클릭 수는 2이기 때문이다. 마찬가지로 길이 $2k$ + $1$ 의 홀수 사이클의 보완은 완벽할 수 없는데, 그 색수는 k + $1$ 이고 그 클릭 수는 $k$ 이기 때문이다(대안적으로 이 그래프의 불완전성은 완벽한 그래프 정리 및 보완적인 홀수 사이클의 불완전함에서 따온 것이다). 이 그래프들이 완벽하지 않기 때문에 모든 완벽한 그래프는 버지 그래프여야 한다. 홀수 구멍도 없고 홀수 안티홀도 없는 그래프. 버지는 모든 버지의 그래프가 완벽하다고 추측했다. 이것은 마침내 추드노브스키, 로버트슨, 세이모어, 토마스(2006)의 강력한 완벽한 그래프 정리로서 증명되었다. 그것은 사소한 것으로 완벽한 그래프 정리를 암시하고 있으며, 따라서 명칭을 의미한다.

완벽한 그래프 정리는 짧은 증거를 가지고 있지만, 강력한 완벽한 그래프 정리의 증거는 베르헤 그래프의 깊은 구조적 분해를 바탕으로 길고 기술적이다. 관련 분해 기법도 다른 그래프 등급, 특히 발톱이 없는 그래프의 연구에서 결실을 맺었다.

원래 하지날에서 제안했던 로바스스로 인해 다시 세 번째 정리가 있다. 가장 큰 클라이크와 가장 큰 독립 집합의 크기가 함께 곱할 때 그래프의 정점 수와 같거나 초과하면 그래프가 완벽하다고 명시하고 있으며, 유도 하위 그래프도 마찬가지다. 그것은 강력한 완벽한 그래프 정리의 쉬운 결과인 반면, 완벽한 그래프 정리는 쉬운 결과인 것이다.

하지날 특성화는 홀수 n 사이클 또는 $n$ > $3$ 에 대한 보완으로 충족되지 않는다: n > $3$ 정점의 홀수 사이클은 $2번$ 과 독립 번호 $(n$ - 1 $)/2$ 를 갖는다. 그 반대는 보완에 해당하므로 두 경우 모두 제품이 n - $1$ 이다.

완벽한 그래프의 알고리즘

모든 완벽한 그래프에서 그래프 컬러링 문제, 최대 클라이크 문제, 최대 독립 세트 문제는 다항 시간(Grötschel, Lovass & Schrijver 1988)에 모두 해결될 수 있다. 일반 사례에 대한 알고리즘은 이러한 그래프의 Lovász 번호를 포함하며, (주어진 그래프를 보완하기 위해) 색수와 클릭 번호 사이에 끼어 있다. Lovassz 숫자를 계산하는 것은 세미데마인파 프로그램으로 공식화될 수 있고 선형 프로그래밍을 위한 타원체 방법을 사용하여 다항 시간에서 대략적으로 수치로 계산된다. 완벽한 그래프의 경우, 이 근사치를 정수로 반올림하면 다항 시간 내에 색수와 클릭 수를 얻을 수 있다. 최대 독립 집합은 그래프의 보완에 동일한 접근법을 적용함으로써 찾을 수 있다. 그러나 이 방법은 복잡하고 다항식 지수가 높다. 더 효율적인 조합 알고리즘은 많은 특별한 경우에 알려져 있다.

여러 해 동안 Berge 그래프와 완벽한 그래프를 인식하는 복잡성은 여전히 열려 있었다. Berge 그래프의 정의에 따르면, 즉시 그 그래프의 인식이 co-NP(Lovász 1983)에 있다는 것을 알 수 있다. 마침내, 강력한 완벽한 그래프 정리의 증명 이후, 추드노프스키, 코르누에졸스, 류, 세이모어, 부슈코비치 등에 의해 다항 시간 알고리즘이 발견되었다.

참조

^ Coudert, Olivier (1997). Exact Coloring of Real-Life Graphs is Easy. DAC '97: Proceedings of the 34th annual Design Automation Conference. pp. 121–12. doi:10.1145/266021.266047.
^ West, Douglas Brent, author. (2017-02-14). Introduction to graph theory. ISBN 9780131437371. OCLC 966410137. {{cite book}}: last= 일반 이름 포함(도움말)CS1 maint: 여러 이름: 작성자 목록(링크)

Berge, Claude (1961). "Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind". Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. 10: 114.
Berge, Claude (1963). "Perfect graphs". Six Papers on Graph Theory. Calcutta: Indian Statistical Institute. pp. 1–21.
Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina (2005). "Recognizing Berge graphs". Combinatorica. 25 (2): 143–186. doi:10.1007/s00493-005-0012-8. S2CID 2229369.
Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics. 164 (1): 51–229. arXiv:math/0212070. doi:10.4007/annals.2006.164.51. S2CID 119151552.
Gallai, Tibor (1958). "Maximum-minimum Sätze über Graphen". Acta Mathematica Academiae Scientiarum Hungaricae. 9 (3–4): 395–434. doi:10.1007/BF02020271. S2CID 123953062.
Golumbic, Martin Charles (1980). Algorithmic Graph Theory and Perfect Graphs. Academic Press. ISBN 0-444-51530-5. Archived from the original on 2010-05-22. Retrieved 2007-11-21. 제2판, 이산 수학 연보 57, 엘스비에, 2004.
Grötschel, Martin; Lovász, László; Schrijver, Alexander (1988). Geometric Algorithms and Combinatorial Optimization. Springer-Verlag. 특히 9장 "그래프의 안정적 집합", 페이지 273–303을 참조하십시오.
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.
Lovász, László (1983). "Perfect graphs". In Beineke, Lowell W.; Wilson, Robin J. (eds.). Selected Topics in Graph Theory, Vol. 2. Academic Press. pp. 55–87. ISBN 0-12-086202-6.

외부 링크

[1] Coudert, Olivier (1997). Exact Coloring of Real-Life Graphs is Easy. DAC '97: Proceedings of the 34th annual Design Automation Conference. pp. 121–12. doi:10.1145/266021.266047.

[2] West, Douglas Brent, author. (2017-02-14). Introduction to graph theory. ISBN 9780131437371. OCLC 966410137. {{cite book}}: last= 일반 이름 포함(도움말)CS1 maint: 여러 이름: 작성자 목록(링크)

[2]

Search