그래프 색칠 (graph coloring)
쉽게 풀면
세계지도를 색칠할 때 국경을 맞대고 있는 두 나라는 반드시 다른 색으로 칠해야 헷갈리지 않습니다. 이때 "몇 가지 색만 있으면 지도 전체를 이렇게 칠할 수 있을까?"라는 질문이 바로 그래프 색칠 문제입니다. 각 나라를 꼭짓점으로, 국경을 맞댄 관계를 변으로 나타내면 지도가 하나의 그래프가 되고, 인접한 꼭짓점끼리 다른 색을 쓰면서 필요한 색의 최소 개수를 "채색수(chromatic number)"라고 부릅니다. 신기하게도 평면 위에 그릴 수 있는 어떤 지도든 4가지 색만 있으면 충분하다는 사실이 증명되어 있는데, 이를 4색 정리라고 합니다.
왜 중요한가
그래프 색칠은 "서로 충돌하는 자원을 어떻게 최소한의 종류로 분리해서 배정할 것인가"라는 문제로 일반화되기 때문에, 스케줄링·자원 할당·최적화를 다루는 다양한 분야의 논문에서 문제를 표현하는 틀로 자주 쓰입니다. 조합론적으로는 계산 복잡도 이론에서 NP-난해 문제의 대표적인 예로 다뤄지며, 근사 알고리즘이나 발견적(heuristic) 기법의 성능을 검증하는 벤치마크 문제로도 자주 활용됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 서로 동시에 실행하면 안 되는 작업들을 연결한 그래프를 만들고, 이 그래프를 색칠하는 방식으로 겹치지 않는 시간표를 짰다는 뜻입니다. 시험 시간표 배정, 무선 채널 할당, 레지스터 할당 등 자원 충돌을 다루는 컴퓨터공학·최적화 논문에서 자주 응용되는 기법입니다.
통신 네트워크 분야에서도 서로 가까운 기지국이 같은 주파수를 쓰지 않도록 그래프 색칠 개념을 이용해 채널을 배정했다는 뜻입니다.
조금 더 깊게 보면
실제 응용에서는 정확한 채색수를 구하기보다, 그리디 색칠 알고리즘이나 지역 탐색 기반의 발견적 기법으로 실용적인 시간 안에 "충분히 좋은" 색칠을 찾는 경우가 대부분입니다. 그래프의 특성에 따라 최대 차수(degree)에 기반한 이론적 상한(예: 최대 차수 더하기 1로 항상 색칠 가능하다는 정리)이 알려져 있어, 이런 이론적 경계를 이용해 근사 알고리즘의 성능을 평가하기도 합니다.
주의할 점
주어진 그래프의 채색수를 정확히 구하는 일반적인 문제는 계산 복잡도가 매우 높은 NP-난해 문제로 알려져 있어, 큰 그래프에서는 정확한 최솟값 대신 근사 알고리즘으로 "충분히 괜찮은" 색칠을 찾는 경우가 많습니다. 이는 경우의 수가 폭발적으로 늘어나는 조합 최적화 문제의 전형적인 예입니다.