-그래프
정점(vertex) 집합과 간선(edge) 집합으로 이루어진 수학적 구조
-채색
그래프에서 같은 간선을 공유하는 정점을 서로 다른 색으로 칠하는 것
-그래프 $G$의 채색다항식 $=C_k(G)$
$k$개의 서로 다른 색을 사용하여 인접하는 두 정점은 같은 색이 아니게끔 그래프 $G$의 정점에 색칠하는 경우의 수
-채색수(chromatic number) $=\chi ( G)$
$C_k(G)\neq 0$ 을 만족하는 최소의 자연수 $k$값 ($C_k(G)$를 0에 가장 가깝게 하는 $k$)
- 영그래프 : 간선이 없는 그래프
영그래프의 채색다항식 $C_k(G)=K^n$
(인접한 정점이 없으므로 각 정점마다 k가지의 채색이 가능하다.)
영그래프의 채색수 $\chi ( G)$ $ = 1 $ (1가지의 색 만으로도 채색이 가능하다.)
2. 완전그래프 : 서로 다른 두 개의 정점이 반드시 하나의 간선으로 연결된 그래프
완전그래프의 채색다항식 $C_k(G)=_{k}P_{n}$
(k개의 색에서 n개를 골라 각 정점에 하나씩 집어넣는 경우의 수)
완전그래프의 채색수 $\chi ( G)$ $ = n $ (채색다항식 ${}_{k}P_{n}$에서 $ k=n $일 때 최소가 된다.)
3.평면그래프 : 평면 상에 그래프를 그렸을 때, 간선끼리 정점에서만 만나도록 그릴 수 있는 그래프
왼쪽 그래프는 평면그래프이다.
왜냐하면 동형그래프를 오른쪽과 같이 그리면 간선끼리 정점에서만 만나도록 그릴 수 있기 때문이다.
4.트리그래프 : 순환을 갖지 않으며 임의의 두 정점 사이의 경로가 존재하는 연결그래프
트리그래프의 채색다항식 $C_k(G)=k(k-1)^{n-1}$
(트리그래프에서 임의의 정점을 $k$개의 색 중 하나로 채색한다면 이어진 정점 $(n-1)$개는 각각 $(k-1)$가지의 색들로 채색 가능하다.)
트리그래프의 채색수 $\chi ( G)$ = 2 (2가지 색을 번갈아서 칠할 때 가장 적은 색을 사용할 수 있다.)
5.순환그래프 : 정다각형의 그래프
순환그래프의 채색다항식 $C_k(G)= (k-1)^n+(-1)^n(k-1)$
(뒤에 나올 제거축약정리에서 점화식을 이용하여 증명 가능하다.)
순환그래프의 채색수 $\chi ( G)$
- 1 ($n=1$일 때)
- 2 ($n$이 짝수 일 때)
- 3 ($n$이 2 이상의 홀수 일 때)
제거 축약 정리(Deletion-contraction theorem)
$C_k(G)=C_k(G-e)-C_k(G/e)$
$G$의 채색다항식 = ($G$에서 $e$를 제거한 채색다항식)-($G$에서 $e$를 축약한 채색다항식)
간단한 증명)
식을 이항하면
$C_k(G-e)=C_k(G)+C_k(G/e)$
간선 $e$가 정점 $u, v$를 연결한다 가정했을 때
$C_k(G-e)$에서는 $e$가 제거되었으므로 두 정점 $u$와 $v$는 인접하지 않다.
따라서 색이 같을 수도 있고 다를 수도 있다.
1. 두 정점 $u$와 $v$를 다른 색으로 채색할 경우
이 경우 $u$와 $v$가 다른 색이므로 $e$를 제거하기 전 두 정점이 연결된 상태에서 채색하는 것과 일치한다.
즉, $u$와 $v$ 사이의 간선 $e$를 잇더라도 채색다항식에는 변함이 없다.
따라서 이 경우의 채색다항식은 $e$가 연결된 상태의 $G$를 채색하므로 $C_k(G)$이다.
2. 두 정점 $u$와 $v$를 같은 색으로 채색할 경우
이 경우 $u$와 $v$는 같은 색이므로 $u$와 $v$를 하나의 정점으로 보아도 무방하다.
즉, $u$와 $v$를 하나의 정점으로 축약하여도 채색다항식에는 변함이 없다.
따라서 이 경우의 채색다항식은 $e$가 축약된 상태의 $G$를 채색하므로 $C_k(G/e)$이다.
두 경우를 합하면
$C_k(G-e)=C_k(G)+C_k(G/e)$
$\Leftrightarrow C_k(G)=C_k(G-e)-C_k(G/e)$
순환그래프에서의 제거축약정리
순환그래프에서 제거축약정리를 사용하면 점화식을 유도해 낼 수 있다.
정점이 $n$개인 순환그래프에서
$e$를 제거하면 정점이 $n$개인 트리그래프가 만들어지고
$e$를 축약하면 정점이 $(n-1)$ 개인 순환그래프가 만들어진다.
따라서 정점이 $n$개인 순환그래프의 채색다항식을 $G_n$으로 정의한 후 제거축약정리 식에 대입해보면
$C_k(G)=C_k(G-e)-C_k(G/e)$
$\therefore C_k(G_n)=k(k-1)^{n-1}-C_k(G_{n-1})$
또한 이 점화식을 이용하여 순환그래프의 채색다항식이 $C_k(G)= (k-1)^n+(-1)^n(k-1)$라는 것을 증명할 수 있다.