그래프 색칠 문제

그래프 색칠 문제(Graph coloring problem)는 인접한 정점들이 같은 색을 가지지 않도록 하면서 그래프의 정점에 색을 칠하는 조합 최적화 문제이다.

정의

그래프 색칠 문제는 정점 색칠(vertex coloring), 모서리 색칠(edge coloring), 면 색칠(face coloring) 등 여러 변형이 있으며, 가장 일반적인 형태는 정점 색칠 문제이다. 주어진 무방향 그래프에서 인접한 정점들이 같은 색을 갖지 않도록 최소한의 색을 사용하여 모든 정점을 색칠하는 것이 목적이다. 이때 필요한 최소 색의 수를 그래프의 색수(chromatic number)라고 한다.

문제 유형

• 정점 색칠(Vertex coloring): 각 정점에 색을 할당하되, 인접한 정점이 서로 다른 색을 가지도록 한다.
• 모서리 색칠(Edge coloring): 각 모서리에 색을 할당하되, 같은 정점을 공유하는 모서리가 서로 다른 색을 가지도록 한다.
• 면 색칠(Face coloring): 평면 그래프에서 면에 색을 할당하며, 인접한 면이 같은 색을 가지지 않도록 한다.

계산 복잡도

그래프 색칠 문제는 일반적으로 NP-완전 문제로 분류된다. 특히, 주어진 정점 색칠 문제에서 k개의 색으로 색칠할 수 있는지 여부를 판단하는 것은 k≥3일 때 NP-완전이다. 따라서 큰 그래프에 대해 최적의 색칠을 구하는 것은 매우 어렵다.

평면 그래프의 경우, 4색 정리에 의해 최대 4가지 색으로 색칠이 가능하지만, 이러한 색칠을 실제로 구하는 문제 또한 복잡할 수 있다. 3색으로 색칠이 가능한 평면 그래프인지 여부를 판별하는 문제는 여전히 NP-완전이다.

알고리즘

• 탐욕적 색칠(Greedy coloring): 정점을 특정 순서로 순회하며 가능한 최소의 색을 할당한다. 최적해를 보장하지는 않지만 계산이 빠르다.
• 백트래킹: 가능한 모든 색칠 조합을 탐색하며 해를 찾는다. 느리지만 정확하다.
• DSatur 알고리즘: 동적으로 포화 차수(saturation degree)를 고려하여 색을 할당한다.
• 몬테카를로 알고리즘(Monte Carlo algorithm): 확률적으로 색을 할당하고 실패 확률을 허용하여 근사 해를 찾는다. 일반적으로 빠르지만 항상 정답을 보장하지 않는다.
• 라스베가스 알고리즘(Las Vegas algorithm): 정답이 나올 때까지 무작위 방식으로 탐색을 반복하되, 정답이 보장된다. 실행 시간이 변동적일 수 있다.
• 메타휴리스틱: 유전 알고리즘, 시뮬레이티드 어닐링 등도 색칠 문제 해결에 활용된다.

응용

• 시간표 편성: 과목 간 충돌이 없도록 시간대(색)를 배정하는 문제.
• 주파수 할당: 인접 지역에서 간섭이 없도록 서로 다른 주파수를 배정.
• 지도 색칠: 국가 혹은 지역 단위로 인접한 영역이 같은 색을 사용하지 않도록 색상 배정.

같이 보기

• NP-완전 문제
• 그래프 이론
• 평면 그래프
• 4색 정리
• 탐욕 알고리즘
• 조합 최적화

참고 문헌

• Jensen, T. R., & Toft, B. (1995). *Graph Coloring Problems*. Wiley-Interscience.
• Garey, M. R., & Johnson, D. S. (1979). *Computers and Intractability: A Guide to the Theory of NP-Completeness*. W. H. Freeman.