채색수(Chromatic Number)

주어진 문제를 수학으로 해결하기 위해선 문제 상황을 반영한 표나 그래프, 수식, 다이어그램 등을 써서 정리하고 분석해야 한다.

수학적 모델링

수학적 모델링은 수학 기호, 식, 그래프, 표, 그림 등으로 문제 상황에 들어맞는 수학적 모델을 만들어 해를 찾아 나가는 일련 된 과정이다. 쾨니히스베르그 다리 문제를 해결하기 위해 오일러가 고안한 그래프 이론이 대표적인 예이다. 쾨니히스베르그에 있는 다리 7개를 모두 한 번씩만 지나서 되돌아 출발점으로 되돌아오는 경로를 찾는 문제를 해결하기 위해 오일러는 아래와 같은 모델을 만들었다.

지도에 나오는 나라를 구분하기 위해 4색이면 충분하다. 다시 정리하면 유한 개 부분으로 나누어진 평면이 있다. 경계선을 공유하는 이웃한 부분은 서로 다른 색으로 구분할 때 필요한 색은 4개이면 충분하다고 할 수 있다. 4색 정리로 불리는 이 정리는 처음에 컴퓨터를 써서 증명하였으나 인정받지 못하다 1976년에 이르러  Kenneth Appel와 Wolfgang Haken 이 증명하였다.

4색 정리를 증명하기 위해서도 그래프 이론이 필요하다. 그래프 이론에 나오는 채색수에 대해 알아보자.

채색수

그래프에서 같은 변을 공유하는 꼭짓점은 서로 다른 색으로 칠하는 것을 '그래프를 채색한다.'라고 한다. 채색수(Chromatic Number)는 주어진 그래프를 채색하는데 필요한 서로 다른 색의 최소 가짓수이다.

채색수는 아래 그림과 같이 그래프 유형에 따라 정해진다. 위에 있는 지도 채색 문제는 채색수로 모델링하여 해결할 수 있다.

더 자세한 것은 아래 링크를 참고하자.

mathworld.wolfram.com/ChromaticNumber.html

Chromatic Number -- from Wolfram MathWorld

지도에 색칠을 하는 문제는 아래 그림과 같이 그래프 문제로 바꿔서 해결할 수 있다. 도시를 꼭짓점으로 생각하고 서로 경계를 공유하고 있다면 변으로 이으면 된다.

채색다항식

채색수가 $n$인 그래프 $G$가 있다. $n$보다 크거나 같은 자연수 $k$에 대하여, 채색다항식은 그래프 $g$를 서로 다른 $k$가지 색으로 채색하는 방법의 수 $f(k)$이다.

아래 그래프는 채색수가 3이다. 이 그래프를 $k(k \geq3)$가지 색으로 채색하는 방법의 수를 생각해 보자.

꼭짓점 $D$를 색칠하는 방법은 $k$가지, 먼저 꼭짓점 $A$는 $D$와 다른 색을 칠해야 하므로 $k-1$가지이다. 꼭짓점 $C$는 꼭짓점 $D$, $A$와 달라야 하므로 $k-2$가지, 마지막으로 꼭짓점 $B$는 꼭짓점 $A$, $C$와 달라야 하므로 $k-2$가지다.

곱의 법칙에 따라 이 그래프의 채색다항식은

$$f(k)=k(k-1)(k-2)^2$$

이다.