그래프 색칠 문제
위키백과 ― 우리 모두의 백과사전.
그래프 이론에서 그래프 색칠이란 꼭지점이나 변과 같은 그래프의 일부분에 빨강 파랑과 같은 색을 칠하는 것을 말한다. 그래프의 일부분이라고 하면, 꼭지점이나 변도 될 수 있지만, 평면에 그렸을 때 면이 될 수도 있다. 색깔은 1, 2, 3, 4와 같은 정수로 생각할 수 있다.
그 중에 꼭지점에 색을 칠하는 경우가 가장 중요하게 다뤄지는데, 그 이유는 4색정리를 풀기위해 노력하다가 그래프 이론 분야가 만들어졌을 정도의 역사적인 배경이 있기도 하거니와, 많은 경우 그래프 색칠 문제를 꼭지점에 색칠하는 경우로 바꿀 수 있기 때문이다. 예를 들어 변에 색을 칠하는 경우는 사실 라인 그래프의 꼭지점 색칠 문제로 바꿔서 생각할 수 있다. 게다가 평면 그래프에서 면에 색칠하는 문제의 경우도 듀얼 그래프에서 꼭지점 색칠 문제와 같다.
[편집] 꼭지점 색칠
보통 그래프 색칠이라고 하면 꼭지점에 색을 칠하는 것을 의미한다. 보통 아무런 말이 없으면 색칠할 때 이웃한 꼭지점은 다른 색으로 칠해야 한다. k개 이하의 색으로 색칠할 수 있다는 말은 그래프의 꼭지점 집합을 k개 이하의 변이 없는 부분집합으로 분할할 수 있다는 것과 동일하다. 그래프를 색칠하는 문제는 많은 분야에 응용이 되고 있다. 예를 들어 컴파일러에서 프로세서 레지스터 할당 문제라던지, 무선 기지국 사이에서 간섭을 없애기 위한 주파수 할당 문제같은 것들에 쓰인다.
[편집] 색칠수
어떤 그래프 G의 색칠수(혹은 채색수, chromatic number)가 k라고 함은, k-1개 이하의 색으로는 그 그래프를 칠할 수 없지만 k개로는 칠할 수 있음을 뜻한다. 보통 그래프 G의 색칠수는 χ(G)로 나타낸다. 예를 들어 n개 꼭지점을 가진 완전 그래프를 색칠하기 위해서는 n개의 색이 필요하고, n개로는 당연히 색칠이 가능하므로, χ(Kn) = n이다.
그래프의 색칠수를 찾는 것은 NP-난해 문제이다. 이 문제의 결정문제판(이 그래프가 k개 색으로 색칠될 수 있나?)은 NP-완전 문제이며, 리차드 카프가 1972년에 보인 21개의 NP-완전 문제 중의 하나이다. 그래프를 평면 그래프로 제한하고, 각 꼭지점에 연결된 변의 개수를 4개로 제한하더라도 이 문제는 여전히 NP-완전일 정도로 어렵다.
