채색수와 채색다항식

기말고사에 과목 네 개 국어, 수학, 영어, 과학이 있다. 같은 학생이 함께 듣는 두 과목은 같은 교시에 치를 수 없다. 국어와 수학, 수학과 영어, 영어와 과학, 과학과 국어를 함께 듣는 학생이 있고, 국어와 영어, 수학과 과학은 함께 듣는 학생이 없다. 교시는 최소 몇 개 필요할까? 교시를 세 개 쓸 수 있다면, 과목에 교시를 배정하는 방법은 모두 몇 가지일까? 과목을 꼭짓점, 함께 듣는 관계를 변으로 그리고, 교시를 색으로 바꾸면 그래프를 칠하는 문제가 된다.

4.7.1이웃은 다른 색

그래프의 각 꼭짓점에 색을 하나씩 칠하되, 변으로 이어진 두 꼭짓점은 서로 다른 색이 되게 하는 것을 그래프의 채색이라 한다. 그렇게 칠하는 데 필요한 색의 최소 개수를 채색수라 한다. 시간표 문제에서는 함께 듣는 학생이 있는 두 과목이 이어져 있으므로, 같은 색, 곧 같은 교시에 놓을 수 없다. 그래서 필요한 최소 교시 수는 채색수이다. 삼각형이 있으면 세 꼭짓점이 서로 모두 이웃이어서 적어도 세 색이 필요하고, 홀수 개의 꼭짓점으로 된 고리도 두 색으로는 칠할 수 없다.

수형도는 한 꼭짓점에 \(k\)가지 색을 고르고, 거기서 가지를 따라가며 각 꼭짓점에 바로 앞 꼭짓점과 다른 \(k - 1\)가지 색을 고르면 되므로 곱의 법칙으로 \(k(k - 1)^{n-1}\)이다. 고리는 한 변을 끊으면 수형도가 되는데, 끊은 변의 두 끝이 같은 색인 경우를 빼야 한다. 그 경우는 두 끝을 한 점으로 합친 더 작은 고리를 칠하는 것과 같아, 이를 되풀이하면 고리의 식을 얻는다. 채색다항식에 \(k = 1, 2, 3, \ldots\)을 차례로 넣어 처음 양수가 되는 \(k\)가 채색수이다.¹

4.7.2지도를 칠하는 색

지도에서 국경을 맞댄 나라끼리 다른 색이 되도록 칠하는 문제는, 나라를 꼭짓점, 국경을 맞댄 관계를 변으로 하는 평면그래프의 채색이다. 1852년 영국의 거스리는 어떤 지도든 네 가지 색이면 충분하다고 추측했고, 이 추측은 120년 넘게 풀리지 않다가 1976년 컴퓨터로 수천 가지 경우를 확인해 증명되었다. 이것이 4색 정리이다. 반면 다섯 색이면 충분하다는 것은 오일러 공식에서 차수 5 이하인 꼭짓점이 늘 있다는 사실로 손으로 증명할 수 있다.

4.7.3예제 풀이

고리의 채색다항식은 \(P = (k - 1)^4 + (k - 1)\)이다. \(k = 1\)이면 \(0 + 0 = 0\)이고, \(k = 2\)이면 \(1 + 1 = 2\)이므로 채색수는 2이다. 교시 2개로는 국어와 영어를 1교시, 수학과 과학을 2교시로 하거나 그 반대로 하는 2가지이다. 교시 3개로는 \(2^4 + 2 = 18\)가지이다.

국어와 영어를 함께 듣는 학생이 생기면 국어, 수학, 영어가 서로 모두 이어진 삼각형이 생기므로, 적어도 세 교시가 필요하다. 실제로 국어 1교시, 수학과 과학 2교시, 영어 3교시로 배정하면 세 교시로 충분하므로 최소 교시 수는 3이 된다. 즉 이웃한 꼭짓점을 다른 색으로 칠하는 그래프의 채색은 충돌을 피하는 배정 문제를 나타내며, 채색다항식으로 칠하는 방법의 수와 필요한 최소 색의 수인 채색수를 구한다.

아래 탐구 카드에서 지도를 칠하는 데 색이 최소 몇 가지 필요한지 찾아보고, 색이 \(k\)가지일 때 칠하는 방법의 수를 채색다항식으로 세어 보자.

1. 채색다항식은 1912년 미국의 버코프가 4색 문제를 풀려는 시도에서 처음 도입했다. 그 시도는 성공하지 못했지만, 채색다항식은 그래프 이론의 중요한 도구로 남았다.