그래프 색칠 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:3-coloringEx.svg|섬네일|250px|그래프의 3개의 색으로의 색칠. 이 그래프는 2개의 색으로 색칠할 수 없으며, 따라서 이 그래프의 색칠수는 3이다.]]
[[그래프 이론]]에서 '''그래프 색칠'''(graph色漆, {{llang|en|graph colo(u)ring}})은 [[그래프]]의 꼭지점들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다. 이를 사용하여 그래프의 불변량을 정의할 수 있다.

== 정의 ==
(단순) 그래프 <math>G</math>의 '''색칠''' <math>(C,c)</math>은 집합 <math>C</math> 및 함수 <math>c\colon V(G)\to C</math>의 순서쌍이다. 이 경우, 임의의 변 <math>v_1v_2\in E(G)</math>에 대하여 <math>c(v_1)\ne c(v_2)</math>이어야만 한다. 색칠 <math>(C,c)</math>에서, <math>C</math>의 원소를 '''색'''(色, {{llang|en|colo(u)r}})이라고 한다.

그래프 <math>G</math>의 두 색칠 <math>(C,c)</math>, <math>(C',c')</math>이 주어졌을 때, 만약 [[전단사 함수]] <math>f\colon C\to C'</math>가 존재하여 <math>c'=f\circ c</math>인 경우, 두 색칠이 서로 [[동형]]이라고 한다.

그래프 <math>G</math>의 '''[[변 색칠]]'''(邊色漆, {{llang|en|edge colo(u)ring}})은 <math>G</math>의 [[선 그래프]] <math>L(G)</math>의 색칠이다. [[평면 그래프]] <math>G</math>의 '''면 색칠'''(面色漆, {{llang|en|face colo(u)ring}})은 그 [[쌍대 그래프]]({{llang|en|dual graph}}) <math>G'</math>의 색칠이다.

=== 색칠 다항식과 색칠수 ===
[[파일:Graph with all three-colourings 2.svg|섬네일|오른쪽|이 그래프 <math>G</math>의 경우 <math>P_Ga(3)=12</math>이다.]]
그래프 <math>G</math>에서, 색 <math>C=\{1,2,\dots,t\}</math>을 공역으로 하는 색칠의 수를 <math>P_G(t)</math>라고 쓰자. (이 경우, 서로 동형인 색칠들도 중복하여 센다.) 만약 <math>G</math>가 유한 그래프일 경우, 이는 <math>t</math>에 대하여 [[다항식]]을 이루며, 이를 <math>G</math>의 '''색칠 다항식'''({{llang|en|chromatic polynomial}})이라고 한다. 그래프 <math>G</math>의 '''색칠수'''(色漆數, {{llang|en|chromatic number}}) <math>\chi(G)</math>는 색칠이 존재하는 최소의 정수이다.
:<math>\chi(G)=\min\{t\in\mathbb N\colon P_G(t)>0\}</math>
마찬가지로, '''변 색칠 다항식''' · '''변 색칠수''' 따위를 정의할 수 있다. 변 색칠수는 '''색칠 지표'''({{llang|en|chromatic index}})라고도 하며, <math>\chi'(G)</math>로 쓴다.

== 성질 ==
(단순) 유한 그래프 <math>G</math>에 대하여, 다음 세 조건이 서로 [[동치]]다.
* <math>\chi(G)=1</math>
* <math>P_G(t)=t^n</math> (<math>n\in\mathbb Z^+</math>)
* <math>|E(G)|=0</math>이며 <math>|V(G)|\ge1</math>
(단순) 그래프 <math>G</math>에 대하여, 다음 두 조건이 서로 [[동치]]다.
* <math>\chi(G)=2</math>
* <math>G</math>는 [[이분 그래프]]이다.

모든 (단순) 유한 그래프 <math>G</math>에 대하여, 다음이 성립한다.
* <math>1\le\chi(G)\le|V(G)|</math>
* <math>\chi(G)\left(\chi(G)-1\right)\le2|E(G)|</math>
* <math>\omega(G)\le\chi(G)\le\Delta(G)+1</math>
여기서 <math>\omega(G)</math>는 <math>G</math>의 최대 [[클릭 (그래프 이론)|클릭]]의 크기이며, <math>\Delta(G)=\max_{v\in V(G)}\deg v</math>는 <math>G</math>의 꼭짓점들의 차수들의 최댓값이다.
'''브룩스의 정리'''({{llang|en|Brooks’ theorem}})에 따르면, 임의의 연결 유한 그래프 <math>G</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* <math>\chi(G)=\Delta(G)+1</math>이다.
* <math>G</math>는 [[완벽 그래프]]이거나 홀수 크기의 [[순환 그래프]]이다.

'''[[4색정리]]'''에 따르면, 모든 유한 [[평면 그래프]] <math>G</math>에 대하여
:<math>\chi(G)\le 4</math>
이다. '''그뢰치의 정리'''({{llang|en|Grötzsch’s theorem}})에 따르면, 크기가 3인 [[순환 (그래프 이론)|순환]]을 갖지 않는 유한 [[평면 그래프]] <math>G</math>에 대하여
:<math>\chi(G)\le3</math>
이다.

=== 색칠 다항식의 성질 ===
<math>n</math>개의 꼭짓점을 갖는 그래프의 색칠 다항식은 <math>n</math>차 다항식이다.

(단순) 유한 그래프 <math>G</math>에 대하여, 다음 두 조건이 동치다.
* <math>\chi_G(t)=t(t-1)^{n-1}</math>
* <math>G</math>는 <math>n</math>개의 꼭짓점을 갖는 [[나무 (그래프 이론)|나무]]이다.

(단순) 유한 그래프 <math>G</math>에 대하여, 다음 두 조건이 동치다.
* <math>\chi_G(t)=(t-1)^n+(-1)^n(t-1)</math>
* <math>G</math>는 크기 <math>n</math>의 [[순환 그래프]] <math>C_n</math>이다.

[[파일:Chromatically equivalent graphs.svg|섬네일|오른쪽|색칠 다항식이 <math>t(t-1)^3(t-2)</math>인 그래프]]
두 그래프의 색칠 다항식이 같을 경우, 이들이 '''색칠 동치'''({{llang|en|chromatically equivalent}})라고 한다. 서로 동형이 아닌 두 그래프가 색칠 동치일 수 있다. 예를 들어, 꼭짓점의 수가 같지만 서로 동형이 아닌 두 [[나무 (그래프 이론)|나무]]는 색칠 동치이다. 또한, 색칠 다항식이 <math>t(t-1)^3(t-2)</math>인 그래프는 총 3개가 있다.

연결 성분 <math>G_1,\dots,G_n</math>으로 구성된 그래프의 색칠 다항식은 다음과 같다.
:<math>P_G(t)=\prod_{i=1}^nP_{G_i}(t)</math>

(단순) 그래프 <math>G</math> 및 <math>uv\in E(G)</math>에 대하여, <math>G-uv</math>를 <math>G</math>에서 변 <math>uv</math>를 제거한 그래프, <math>G/uv</math>를 <math>G</math>에서 변 <math>uv</math>를 제거하고 <math>u</math>와 <math>v</math>를 합친 그래프라고 하자. 그렇다면 다음이 성립한다.
:<math>P_G=P_{G-uv}-P_{G/uv}</math>
즉, 이를 사용하여 색칠 다항식을 재귀적으로 계산할 수 있다.

=== 알고리즘 ===
임의의 그래프에 대하여 <math>k</math>-색칠이 존재하는지 여부는 [[NP-완전]] [[결정 문제]]다. 이는 [[리처드 카프]]가 [[1972년]]에 보인 21개의 [[NP-완전]] 문제 중의 하나이다.

임의의 그래프 <math>G</math>에 대하여, <math>\Delta(G)+1</math>-색칠은 항상 존재하며, [[탐욕 알고리즘]]으로 쉽게 찾을 수 있다.

== 예 ==
일부 그래프의 색칠 다항식 및 색칠수는 다음과 같다.
{| class="wikitable"
! 다항식 || 색칠 다항식 || 색칠수
|-
| 변이 없는 그래프 <math>\bar K_n</math> || <math>t^n</math> || 1
|-
| [[완전 그래프]] <math>K_n</math> || <math>t(t-1)(t-2)...(t-(n-1))</math> || <math>n</math>
|-
| <math>n</math>개의 꼭짓점을 갖는 [[나무 (그래프 이론)|나무]] || <math>t(t-1)^{n-1}</math>   || 2
|-
| [[순환 그래프]] <math>C_n</math>|| <math>(t-1)^n+(-1)^n(t-1)</math> || 2 (<math>n</math> 짝수), 3 (<math>n</math> 홀수)
|-
| [[페테르센 그래프]] || <math>t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)</math> || 3
|}

== 응용 ==
그래프 색칠 문제는 [[컴파일러]]에서 [[프로세서 레지스터]]를 할당하는 문제, [[무선 기지국]] 사이에서 간섭을 없애기 위한 [[주파수]] 할당 문제 등에 응용된다.

[[스도쿠]] 역시 일종의 그래프 색칠 문제이다. 이 경우, 9×9 격자의 각 행·각 열·각 3×3 부분격자는 [[클릭 (그래프 이론)|클릭]]을 이루며, 스도쿠는 주어진 부분적 9-색칠을 완성시키는 문제이다.

== 외부 링크 ==
* {{eom|title=Graph colouring}}

== 같이 보기 ==
* [[텃 다항식]]
* [[램지의 정리]]

{{전거 통제}}

[[분류:그래프 색칠| ]]
[[분류:그래프 이론의 계산 문제]]
[[분류:NP-완전 문제]]
[[분류:NP-난해 문제]]