그래프 색칠: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Osteologia (토론 | 기여) 잔글 →성질 |
Osteologia (토론 | 기여) 편집 요약 없음 |
||
20번째 줄:
* <math>P_\Gamma(t)=t^n</math>
* <math>|E(\Gamma)|=0</math>
(단순 무향) 그래프 <math>\Gamma</math>에 대하여, 다음 두 조건이 서로 [[동치]]다.
* <math>\chi(\Gamma)=2</math>
* <math>\Gamma</math>는 [[이분 그래프]]이다.
모든 (단순 무향) 그래프 <math>\Gamma</math>에 대하여, 다음이 성립한다.
줄 30 ⟶ 33:
* <math>\Gamma</math>는 [[완벽 그래프]]이거나 홀수 크기의 [[순환 그래프]]이다.
'''[[4색정리]]'''에 따르면, 모든 [[평면 그래프]] <math>\Gamma</math>에 대하여
임의의 그래프에 대하여 <math>k</math>-색칠이 존재하는지 여부는 [[NP-완전]] [[결정 문제]]다. 이는 [[리처드 카프]]가 [[1972년]]에 보인 21개의 [[NP-완전]] 문제 중의 하나이다.▼
:<math>\chi(\Gamma)\le 4</math>
이다. '''그뢰치의 정리'''({{llang|en|Grötzsch’s theorem}})에 따르면,또한, 크기가 3인 [[순환 (그래프 이론)|순환]]
:<math>\chi(\Gamma)\le3</math>
이다.
=== 색칠 다항식의 성질 ===
줄 49 ⟶ 48:
연결 성분 <math>\Gamma_1,\dots,\Gamma_n</math>으로 구성된 그래프의 색칠 다항식은 다음과 같다.
:<math>P_\Gamma(t)=\prod_{i=1}^nP_{\Gamma_i}(t)</math>
=== 알고리즘 ===
▲임의의 그래프에 대하여 <math>k</math>-색칠이 존재하는지 여부는 [[NP-완전]] [[결정 문제]]다. 이는 [[리처드 카프]]가 [[1972년]]에 보인 21개의 [[NP-완전]] 문제 중의 하나이다.
임의의 그래프 <math>\Gamma</math>에 대하여, <math>\Delta(\Gamma)+1</math>-색칠은 항상 존재하며, [[탐욕 알고리즘]]으로 쉽게 찾을 수 있다.
== 예 ==
| |||