그래프 색칠하기 — 색수와 활용

그래프 색칠하기는 보통 정점 색칠하기를 뜻합니다. 인접한 정점끼리는 같은 색을 쓰지 않도록 각 정점에 색을 배정하는 것입니다. 이때 가능한 가장 적은 색의 개수를 색수라고 하며, $\chi(G)$로 씁니다.

빠르게 직관만 잡고 싶다면, 색은 충돌이 없는 라벨이라고 생각하면 됩니다. 두 정점 사이에 간선이 없을 때에만 같은 색을 다시 사용할 수 있습니다.

1분 만에 보는 그래프 색칠하기의 정의

올바른 색칠에서는 모든 간선이 서로 다른 색의 두 정점을 연결합니다. 규칙은 이것이 전부입니다.

따라서 $\chi(G)=3$이라면, 다음 두 사실이 동시에 참입니다.

• $3$가지 색으로 하는 올바른 색칠이 존재한다
• $2$가지 색만으로는 올바른 색칠이 존재하지 않는다

그래서 색수는 어떤 그림에서 우연히 사용한 색의 개수가 아니라, 가능한 최소값입니다.

따로 말이 없으면, 입문 과정에서 그래프 색칠하기는 단순 무방향 그래프의 정점을 색칠하는 것을 뜻합니다. 간선 색칠하기는 규칙이 다른 별개의 문제입니다.

색수가 실제로 측정하는 것

색의 이름 자체는 중요하지 않습니다. 빨강, 파랑, 초록을 써도 되고, $1$, $2$, $3$이라는 라벨을 써도 됩니다.

중요한 것은 묶음입니다. 같은 색을 가진 정점들은 그 안에 간선이 없는 집합을 이루므로, 그 그룹 안에는 충돌이 없습니다.

이 관점 때문에 그래프 색칠하기는 일정 배정이나 자원 할당 문제에서 유용합니다. 하나의 색은 종종 "이 항목들은 같은 시간대나 슬롯을 함께 쓸 수 있다"는 뜻이 됩니다.

예제로 보기: 왜 5-사이클에는 3가지 색이 필요한가

간선이 $AB, BC, CD, DE,$ 그리고 $EA$인 사이클 그래프 $C_5$를 생각해 봅시다.

먼저 $2$가지 색을 시도해 봅시다. $A$에 색 $1$, $B$에 색 $2$를 주면, 사이클을 따라가며 색이 강제로 정해집니다.

$$A=1,\quad B=2,\quad C=1,\quad D=2$$

이제 $E$를 봅시다. $E$는 $D$와도 인접하고 $A$와도 인접합니다. 따라서 $D$ 때문에 색 $2$를 쓸 수 없고, $A$ 때문에 색 $1$도 쓸 수 없습니다.

즉, $2$가지 색으로는 실패합니다.

하지만 $3$가지 색으로는 가능합니다. 한 가지 올바른 색칠은 다음과 같습니다.

$$A=1,\quad B=2,\quad C=1,\quad D=2,\quad E=3$$

따라서

$$\chi(C_5)=3$$

이 예제는 꼭 기억할 만합니다. 중요한 패턴을 보여 주기 때문입니다. 사이클 그래프에서는 짝수 사이클은 $2$가지 색으로 색칠할 수 있지만, 홀수 사이클은 $3$가지 색이 필요합니다.

작은 그래프에서 그래프 색칠하기를 추론하는 방법

빠르게 확인할 수 있는 방법이 두 가지 있습니다.

첫째, 피할 수 없는 충돌을 찾으세요. 위의 예에서는 홀수 사이클을 따라 두 색을 번갈아 칠하면 마지막 정점이 가능한 두 선택 모두와 충돌하게 됩니다.

둘째, 하한을 찾으세요. 그래프에 삼각형이 들어 있으면 그 세 정점은 서로 쌍으로 인접하므로 이미 $3$가지 서로 다른 색이 필요합니다. 이것이 항상 정확한 답을 주는 것은 아니지만, 색수가 적어도 $3$이라는 것은 증명해 줍니다.

그래프 색칠하기 문제에서 흔한 실수

흔한 실수 하나는 정점들이 그림에서 가까이 그려졌다는 이유만으로 인접하다고 생각하는 것입니다. 색칠 제약을 만드는 것은 실제 간선뿐입니다.

또 다른 실수는 모든 정점이 각자 다른 색을 가져야 한다고 가정하는 것입니다. 인접하지 않은 정점들은 같은 색을 다시 사용할 수 있고, 효율적인 색칠은 보통 색을 최대한 재사용합니다.

학생들은 정점 색칠하기와 간선 색칠하기를 헷갈리기도 합니다. 이 페이지에서의 규칙은 인접한 간선이 아니라 인접한 정점에 대한 것입니다.

마지막 실수는 필요한 최소 색 수가 아니라, 우연히 사용한 색의 개수를 답으로 쓰는 것입니다. 어떤 그래프에 $4$가지 색을 썼다고 해서 색수가 $4$라는 뜻은 아닙니다.

그래프 색칠하기는 어디에 쓰일까

대표적인 활용은 일정표 작성입니다. 각 정점이 시험 하나를 나타내고, 간선이 두 시험이 같은 학생들을 공유해서 같은 시간에 배치될 수 없다는 뜻이라고 해 봅시다. 그러면 하나의 색은 하나의 시험 시간대를 나타낼 수 있습니다.

이 모델에서 색수는 가능한 최소 시간대 수를 알려 줍니다. $\chi(G)=4$라면, $3$개 시간대만으로는 올바른 일정을 만들 수 없습니다.

같은 아이디어는 서로 이웃한 지역이 달라야 하는 지도 색칠 문제에도 나타나고, 동시에 필요한 변수들이 같은 레지스터를 공유할 수 없는 컴파일러 설계에도 쓰입니다.

비슷한 그래프 색칠하기 문제를 풀어 보세요

정점이 $P,Q,R,S,T$이고 간선이 $PQ, QR, RS, ST, TP,$ 그리고 $PR$인 그래프를 그려 보세요.

먼저 삼각형을 찾아 하한을 구해 보세요. 그다음 가능한 한 적은 색으로 그래프를 색칠해 보고, 인접한 정점끼리 같은 색이 있는지 확인하세요. 다음 단계로 나아가고 싶다면, 더 큰 그래프에서 직접 비슷한 문제를 만들어 보고, 당신의 색칠이 단지 올바를 뿐 아니라 정말 최소인지도 증명해 보세요.