그래프 색칠

그래프의 3개의 색으로의 색칠. 이 그래프는 2개의 색으로 색칠할 수 없으며, 따라서 이 그래프의 색칠수는 3이다.

그래프 이론에서 그래프 색칠(graph色漆, 영어: graph colo(u)ring)은 그래프의 꼭지점들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다. 이를 사용하여 그래프의 불변량을 정의할 수 있다.

정의

(단순) 그래프 $G$ 의 색칠 $(C, c)$ 은 집합 $C$ 및 함수 $c : V (G) \to C$ 의 순서쌍이다. 이 경우, 임의의 변 $v_{1} v_{2} \in E (G)$ 에 대하여 $c (v_{1}) \neq c (v_{2})$ 이어야만 한다. 색칠 $(C, c)$ 에서, $C$ 의 원소를 색(色, 영어: colo(u)r)이라고 한다.

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

그래프 $G$ 의 변 색칠(邊色漆, 영어: edge colo(u)ring)은 $G$ 의 선 그래프 $L (G)$ 의 색칠이다. 평면 그래프 $G$ 의 면 색칠(面色漆, 영어: face colo(u)ring)은 그 쌍대 그래프(영어: dual graph) $G^{'}$ 의 색칠이다.

색칠 다항식과 색칠수

파일:Graph with all three-colourings 2.svg

이 그래프

G

의 경우

P_{G} a (3) = 12

이다.

그래프 $G$ 에서, 색 $C = {1, 2, \dots, t}$ 을 공역으로 하는 색칠의 수를 $P_{G} (t)$ 라고 쓰자. (이 경우, 서로 동형인 색칠들도 중복하여 센다.) 만약 $G$ 가 유한 그래프일 경우, 이는 $t$ 에 대하여 다항식을 이루며, 이를 $G$ 의 색칠 다항식(영어: chromatic polynomial)이라고 한다. 그래프 $G$ 의 색칠수(色漆數, 영어: chromatic number) $χ (G)$ 는 색칠이 존재하는 최소의 정수이다.

χ (G) = \min {t \in ℕ : P_{G} (t) > 0}

마찬가지로, 변 색칠 다항식 · 변 색칠수 따위를 정의할 수 있다. 변 색칠수는 색칠 지표(영어: chromatic index)라고도 하며, $χ^{'} (G)$ 로 쓴다.

성질

(단순) 유한 그래프 $G$ 에 대하여, 다음 세 조건이 서로 동치다.

$χ (G) = 1$
$P_{G} (t) = t^{n}$ ( $n \in ℤ^{+}$ )
$| E (G) | = 0$ 이며 $| V (G) | \geq 1$

(단순) 그래프 $G$ 에 대하여, 다음 두 조건이 서로 동치다.

$χ (G) = 2$
$G$ 는 이분 그래프이다.

모든 (단순) 유한 그래프 $G$ 에 대하여, 다음이 성립한다.

$1 \leq χ (G) \leq | V (G) |$
$χ (G) (χ (G) - 1) \leq 2 | E (G) |$
$ω (G) \leq χ (G) \leq Δ (G) + 1$

여기서 $ω (G)$ 는 $G$ 의 최대 클릭의 크기이며, $Δ (G) = \max_{v \in V (G)} \deg v$ 는 $G$ 의 꼭짓점들의 차수들의 최댓값이다. 브룩스의 정리(영어: Brooks’ theorem)에 따르면, 임의의 연결 유한 그래프 $G$ 에 대하여, 다음 두 조건이 서로 동치이다.

$χ (G) = Δ (G) + 1$ 이다.
$G$ 는 완벽 그래프이거나 홀수 크기의 순환 그래프이다.

4색정리에 따르면, 모든 유한 평면 그래프 $G$ 에 대하여

χ (G) \leq 4

이다. 그뢰치의 정리(영어: Grötzsch’s theorem)에 따르면, 크기가 3인 순환을 갖지 않는 유한 평면 그래프 $G$ 에 대하여

χ (G) \leq 3

이다.

색칠 다항식의 성질

$n$ 개의 꼭짓점을 갖는 그래프의 색칠 다항식은 $n$ 차 다항식이다.

(단순) 유한 그래프 $G$ 에 대하여, 다음 두 조건이 동치다.

$χ_{G} (t) = t (t - 1)^{n - 1}$
$G$ 는 $n$ 개의 꼭짓점을 갖는 나무이다.

(단순) 유한 그래프 $G$ 에 대하여, 다음 두 조건이 동치다.

$χ_{G} (t) = (t - 1)^{n} + (- 1)^{n} (t - 1)$
$G$ 는 크기 $n$ 의 순환 그래프 $C_{n}$ 이다.

파일:Chromatically equivalent graphs.svg

색칠 다항식이

t (t - 1)^{3} (t - 2)

인 그래프

두 그래프의 색칠 다항식이 같을 경우, 이들이 색칠 동치(영어: chromatically equivalent)라고 한다. 서로 동형이 아닌 두 그래프가 색칠 동치일 수 있다. 예를 들어, 꼭짓점의 수가 같지만 서로 동형이 아닌 두 나무는 색칠 동치이다. 또한, 색칠 다항식이 $t (t - 1)^{3} (t - 2)$ 인 그래프는 총 3개가 있다.

연결 성분 $G_{1}, \dots, G_{n}$ 으로 구성된 그래프의 색칠 다항식은 다음과 같다.

P_{G} (t) = \prod_{i = 1}^{n} P_{G_{i}} (t)

(단순) 그래프 $G$ 및 $u v \in E (G)$ 에 대하여, $G - u v$ 를 $G$ 에서 변 $u v$ 를 제거한 그래프, $G / u v$ 를 $G$ 에서 변 $u v$ 를 제거하고 $u$ 와 $v$ 를 합친 그래프라고 하자. 그렇다면 다음이 성립한다.

P_{G} = P_{G - u v} - P_{G / u v}

즉, 이를 사용하여 색칠 다항식을 재귀적으로 계산할 수 있다.

알고리즘

임의의 그래프에 대하여 $k$ -색칠이 존재하는지 여부는 NP-완전 결정 문제다. 이는 리처드 카프가 1972년에 보인 21개의 NP-완전 문제 중의 하나이다.

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

예

일부 그래프의 색칠 다항식 및 색칠수는 다음과 같다.

다항식	색칠 다항식	색칠수
변이 없는 그래프 ${\bar{K}}_{n}$	$t^{n}$	1
완전 그래프 $K_{n}$	$t (t - 1) (t - 2) ... (t - (n - 1))$	$n$
$n$ 개의 꼭짓점을 갖는 나무	$t (t - 1)^{n - 1}$	2
순환 그래프 $C_{n}$	$(t - 1)^{n} + (- 1)^{n} (t - 1)$	2 ( $n$ 짝수), 3 ( $n$ 홀수)
페테르센 그래프	$t (t - 1) (t - 2) (t^{7} - 12 t^{6} + 67 t^{5} - 230 t^{4} + 529 t^{3} - 814 t^{2} + 775 t - 352)$	3

응용

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

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

외부 링크

“Graph colouring” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4.

같이 보기

모듈:Authority_control 159번째 줄에서 Lua 오류: attempt to index field 'wikibase' (a nil value).