그래프 색칠

수치해석 소프트웨어 마지막 수정: 2026-08-23 04:12:40

1. 개요[편집]

그래프 색칠 Graph Coloring
대상	정점 채색(vertex coloring)
핵심량	채색수 $\chi(G)$
판정 복잡도	$k \ge 3$ 이면 NP-완전
기본 상계	$\chi \le \Delta + 1$ (브룩스: 예외 빼면 $\Delta$)
대표 휴리스틱	탐욕 · Welsh-Powell · DSATUR
수치해석 응용	희소 야코비안 압축(CPR) · 적흑 스무더

지도에 색칠하는 초등학교 숙제인 줄 알았는데, 알고 보니 컴파일러와 GPU 솔버가 매일 돌리는 것이었다.

그래프 색칠(graph coloring)은 그래프의 정점마다 색을 하나씩 배정하되 간선으로 이어진 두 정점이 같은 색을 갖지 않게 하는 문제이며, 그렇게 칠하는 데 필요한 최소 색 수를 채색수(chromatic number) $\chi(G)$ 라 한다. “이어진 것끼리는 동시에 하면 안 된다”는 제약을 그래프로 옮기면 무엇이든 색칠 문제가 되기 때문에, 시간표·주파수 배정·레지스터 할당 같은 서로 무관해 보이는 문제들이 전부 같은 껍데기를 쓴다.

시뮬레이션 하는 사람이 이 문서를 봐야 하는 이유는 따로 있다. 희소 자코비안 행렬을 유한차분으로 만드는 비용이 채색수만큼으로 줄어들고, 격자 위 반복법 스무더를 병렬화하는 순서도 결국 색칠이기 때문이다. 즉 색칠은 이 바닥에서 조합론 놀이가 아니라 “한 번에 동시에 처리해도 되는 것들의 묶음”을 찾는 도구다.

2. 채색수와 기본 상계[편집]

정의부터 정리하자. $k$ -채색이 존재하면 $G$ 는 $k$ -채색 가능이고, $\chi(G)$ 는 그런 $k$ 의 최솟값이다. 바로 따라오는 사실 몇 가지.

완전그래프: $\chi(K_n) = n$ . 일반적으로 $G$ 안에 크기 $\omega$ 의 클리크가 있으면 $\chi(G) \ge \omega(G)$ 다. 이 하계는 흔히 느슨하다(무삼각형인데 채색수가 큰 그래프가 얼마든지 있다).
이분그래프: 간선이 있는 그래프에서 $\chi = 2$ 인 것과 홀수 길이 사이클이 없는 것이 동치다. 격자를 체스판처럼 칠할 수 있다는 사실이 여기서 나온다.
탐욕 상계: 어떤 순서로 칠하든 정점 하나를 칠할 때 금지된 색은 최대 $\Delta$ 개(이웃 수)이므로 $\chi(G) \le \Delta(G) + 1$ 이다.

마지막 상계를 한 칸 조여 주는 것이 브룩스 정리(Brooks, 1941)다. 연결 그래프 $G$ 가 완전그래프도 아니고 홀수 사이클도 아니면 $\chi(G) \le \Delta(G)$ . 예외 두 종류가 정확히 등호가 필요한 경우다 — $K_n$ 은 $\Delta+1 = n$ 색이 필요하고, 홀수 사이클은 $\Delta = 2$ 인데 3색이 필요하다. 실무적으로 이 정리는 “탐욕이 뽑는 $\Delta+1$ 은 거의 항상 한 칸 낭비”라는 힌트로 읽힌다. 다만 브룩스 정리의 증명이 주는 채색은 구성적이긴 해도 최적과는 거리가 멀다.

3. 탐욕 채색 — 순서가 전부다[편집]

가장 단순한 알고리즘은 탐욕 채색이다. 정점을 어떤 순서로 훑으면서, 각 정점에 이웃이 아직 안 쓴 색 중 번호가 가장 작은 것을 준다. $O(V + E)$ 에 끝나고 구현은 열 줄이다.

문제는 결과가 순서에 전적으로 좌우된다는 것이다. 좋은 소식은 어떤 그래프든 $\chi(G)$ 색으로 칠하게 만드는 완벽한 순서가 존재한다는 것(최적해에서 색깔별로 정점을 모아 나열하면 된다). 나쁜 소식은 그 순서를 찾는 것이 원 문제만큼 어렵다는 것이고, 더 나쁜 소식은 최악의 순서가 임의로 나쁘다는 것이다.

교과서 반례는 왕관 그래프(crown graph)다. 정점 $a_1,\dots,a_n$ 과 $b_1,\dots,b_n$ 을 두고 $i \ne j$ 일 때만 $a_i$ 와 $b_j$ 를 잇는다. 이건 명백히 이분그래프라 $\chi = 2$ 인데, 순서를 $a_1, b_1, a_2, b_2, \dots$ 로 주면 탐욕이 $n$ 개의 색을 쓴다. 색 수 비율이 $n/2$ 로 벌어지는 것이다. 그래서 실무 휴리스틱은 전부 순서를 어떻게 정할 것인가에 대한 제안이다.

Welsh-Powell(1967)은 정점을 차수 내림차순으로 정렬한 뒤 탐욕을 돌린다. 차수를 $d_1 \ge d_2 \ge \dots \ge d_n$ 으로 정렬해 두면 $i$ 번째 정점을 칠할 때 이미 칠해진 이웃이 $\min(d_i, i-1)$ 개 이하이므로

\chi(G) \le \max_{1 \le i \le n} \min\big(d_i + 1,\ i\big)

이라는 상계가 딸려 나온다. “빡빡한 놈부터 먼저 칠한다”는 직관 그대로다. 정렬 한 번이 전부라 여전히 거의 선형이고, 밀도가 고르지 않은 그래프에서 순수 탐욕보다 눈에 띄게 낫다.

DSATUR(Brélaz, 1979)는 순서를 미리 정하지 않고 매 단계 다시 고른다. 각 정점의 포화도(saturation degree)를 “이웃이 이미 쓰고 있는 서로 다른 색의 개수”로 정의하고, 포화도가 가장 큰 정점을 다음에 칠한다(동점이면 미채색 이웃 수가 큰 쪽). 즉 “선택지가 가장 좁아진 놈부터 처리한다”는 제약 충족 문제의 고전적인 최소잔여값 원리다. 왕관 그래프에서 DSATUR은 2색을 찾아내며, 더 일반적으로 이분그래프에서는 항상 최적임이 증명돼 있다. 사이클·휠 같은 몇몇 부류에서도 최적이다.

같은 기하 랜덤 그래프에 세 정점 순서(무작위·차수 내림차순·DSATUR)를 동시에 걸고 한 정점씩 first-fit 으로 칠한다. 정점 70개·반경 0.22(간선 약 302개) 그래프 200개의 실측 평균 색 수는 9.70 / 8.98 / 8.71 이고, 같은 그래프 하나에 무작위 순열만 2000번 바꿔 걸면 색 수가 8에서 12까지 흔들린다. 매 프레임 인접 동색을 전수검사해 충돌 0을 확인하며, 탐욕 클리크 하한과 색 수가 같아지면 그 채색이 최적임이 확정된다.

대가는 비용이다. 매 단계 포화도 최대 정점을 뽑아야 하므로 소박하게 짜면 $O(V^2)$ , 우선순위 큐에 (포화도, 차수) 키를 얹고 이웃의 포화도가 바뀔 때마다 키를 갱신하면 $O((V+E)\log V)$ 로 떨어진다.¹ 색칠 휴리스틱의 성능표가 사실상 힙 성능표라는 점에서, 이 문서는 우선순위 큐 문서와 한 몸이다.

더 좋은 답이 필요하면 DSATUR 을 분기한정의 뼈대로 쓰거나(Brélaz 원논문이 이미 그렇게 했다), 탐욕해에서 출발해 담금질 모사·타부 탐색으로 색 수를 하나씩 깎아 내려간다. 산업 규모 인스턴스에서는 여전히 “DSATUR 로 초기해, 국소탐색으로 개선”이 국룰이다.

4. 왜 어려운가 — NP-난해성과 4색정리[편집]

채색수를 구하는 문제는 카프의 21개 NP-완전 문제 목록(1972)에 처음부터 들어 있었다. $k$ -채색 가능성 판정은 $k \le 2$ 면 너비 우선 탐색 한 번으로 끝나지만 $k \ge 3$ 이면 NP-완전이다. 심지어 평면그래프의 3-채색 판정도 NP-완전이다.

근사도 안 된다. 채색수를 $n^{1-\varepsilon}$ 배 이내로 근사하는 것조차 (표준 가정 하에서) NP-난해임이 알려져 있다. 그러니까 “적당히 좋은 색칠”에 대한 보장은 사실상 포기하고, 위에서 본 휴리스틱으로 실전 인스턴스를 두들기는 것이 현실이다.

평면그래프로 한정하면 이야기가 달라진다. 4색정리 — 모든 평면그래프는 4색으로 칠할 수 있다 — 는 1976년 아펠과 하켄이 컴퓨터로 수천 개의 불가피 집합을 검사해 증명했고, 인류 최초의 대규모 컴퓨터 보조 증명으로 기록됐다.² 1997년 로버트슨·샌더스·시모어·토머스가 훨씬 짧은 증명을 냈고, 2005년 곤티에가 Coq 로 완전 형식화했다. 5색정리는 종이 한 장으로 증명되고 실제로 선형 시간 알고리즘도 있지만, 4색은 여전히 손으로 안 된다. 참고로 4색정리가 참이어도 평면그래프가 3색으로 되는지 아닌지는 여전히 NP-완전이라는 점이 재미있다 — 존재는 보장되는데 최소값은 모른다.

5. 희소 야코비안의 컬럼 압축[편집]

여기서부터가 심위키다운 각도다. 뉴턴-랩슨법으로 $\mathbf{F}(\mathbf{x}) = \mathbf{0}$ 을 풀려면 매 반복 $m \times n$ 야코비안 $J$ 가 필요하다. 자동 미분을 못 쓰는 레거시 코드에서는 유한차분으로 만드는데, 열 하나마다 함수 평가가 한 번씩 필요하니 $n$ 번의 잔차 평가가 든다. $n$ 이 100만이면 그냥 죽는다.

그런데 희소행렬이면 사정이 다르다. 두 열 $j, k$ 가 구조적으로 직교하면(같은 행에서 동시에 0이 아닌 성분을 갖지 않으면) 두 방향을 한꺼번에 흔들어도 결과가 섞이지 않는다. 그런 열들을 한 묶음 $S$ 로 모아 방향벡터 $\mathbf{d} = \sum_{j \in S} \mathbf{e}_j$ 를 만들고 한 번만 평가하면

\frac{\mathbf{F}(\mathbf{x} + h\,\mathbf{d}) - \mathbf{F}(\mathbf{x})}{h} \approx J\mathbf{d}

의 $i$ 번째 성분이 곧 $\partial F_i/\partial x_j$ 다 — $S$ 안에서 $i$ 행에 성분을 갖는 열 $j$ 는 정의상 하나뿐이므로 모호함이 없다. 결국 필요한 함수 평가 횟수 = 묶음의 개수다.

이제 열을 정점으로, “같은 행을 공유함”을 간선으로 하는 열 교차 그래프(column intersection graph)를 그리면, 유효한 묶음 나누기가 정확히 그 그래프의 정점 채색이 된다. 즉

(\text{최소 함수 평가 횟수}) = \chi\big(G(A)\big)

이것이 커티스-파월-리드(Curtis, Powell, Reid, 1974) 압축이고, 채색 문제와의 동치를 명시적으로 정리한 것은 콜먼과 모레(1983)다.³ 하계는 눈으로도 보인다 — 한 행에 0이 아닌 성분이 $\rho$ 개 있으면 그 열들은 서로 전부 인접하므로 클리크를 이루고, 따라서 색 수는 최소 $\rho_{\max}$ = 행별 최대 비영 개수다. 5점 스텐실 격자 야코비안이면 $\rho_{\max} = 5$ 이고, 실제로 탐욕 채색이 5~7색 언저리를 뽑는다. 100만 번 평가할 것을 예닐곱 번으로 줄이는 것이니, 이 정도면 조합론이 밥값을 한 셈이다.

변주도 많다. 헤시안처럼 대칭이면 대칭성을 이용해 색 수를 더 줄일 수 있고(스타 채색·비순환 채색), 압축된 값에서 원소를 곧바로 읽지 않고 역대입으로 풀어내는 방식(substitution)을 쓰면 색이 더 줄어든다. 이 계열을 총정리한 것이 게브레메딘·마네·포텐의 리뷰이며, 제목이 아예 “What color is your Jacobian?”이다. ColPack 같은 라이브러리가 자동 미분 도구 뒤에 붙어 이 채색을 대신 해 준다.

6. 병렬 격자 스무더와 적흑 순서[편집]

두 번째 각도는 병렬화다. 가우스-자이델 반복법은 정의상 순차적이다 — $x_i$ 를 갱신할 때 이미 갱신된 $x_j (j<i)$ 를 써야 하므로, 순서대로 훑는 한 스레드를 못 나눈다.

탈출구가 색칠이다. 같은 색의 미지수끼리는 서로 인접하지 않으므로 서로의 갱신에 영향을 주지 않는다. 따라서 색 하나를 통째로 병렬 갱신하고 색 사이에만 동기화 장벽을 두면 된다. 5점 라플라시안의 격자 그래프는 이분그래프이므로 색이 두 개면 충분하고, 이것이 그 유명한 적흑 순서(red-black ordering)다. 체스판의 검은 칸을 전부 갱신하고, 그다음 흰 칸을 전부 갱신한다.

여기서 놀라운 것은 적흑이 병렬성만 얻고 수렴은 안 잃는다는 점이다. 오히려 다중격자법의 스무더로 쓰면 2차원 모델 문제에서 국소 푸리에 해석상의 평활화 인자가 사전순 가우스-자이델의 $0.5$ 에서 적흑의 $0.25$ 로 좋아진다. 고주파 오차를 한 스윕에 더 많이 지워 주기 때문이다.⁴ 영(D. M. Young)의 고전적인 SOR 이론에서 말하는 “성질 A”(property A)와 일관 순서(consistently ordered) 조건도 사실 행렬 그래프가 2-채색 가능하다는 말의 다른 표현이다.

비정형 격자로 가면 2색으로는 안 되고 $\Delta+1$ 색 이하의 다색 순서(multicoloring)를 탐욕이나 DSATUR 로 뽑는다. 여기서 실무적 균형이 하나 있다 — 색이 많아지면 동기화 장벽이 늘고 색당 작업량이 줄어 병렬 효율이 떨어지지만, 색이 적으면 한 색 안의 정점이 많아 캐시 지역성이 나빠진다. 게다가 다색 순서는 사전순 순서에 비해 수렴이 다소 느려지는 경우도 있어서, GPU 컴퓨팅에서는 “색은 적당히, 대신 색 내부를 잘 뭉쳐서” 정도가 관행이다. 병렬 색칠 자체도 순차로 하면 병목이므로 존스-플래스먼이나 루비의 무작위 알고리즘으로 병렬로 칠한다.

같은 발상이 유한요소법 조립에서도 쓰인다. 요소별 강성행렬을 전역 행렬에 흩뿌려 더할 때 절점을 공유하는 두 요소가 동시에 쓰면 경쟁 상태가 되는데, 요소를 정점으로 절점 공유를 간선으로 하는 그래프를 칠해 같은 색 요소만 동시에 조립하면 원자 연산 없이 안전하다. 이산요소법의 접촉쌍 처리, 분자동역학의 결합 제약(SHAKE/RATTLE) 병렬화도 같은 트릭이다.

7. 그 밖의 응용[편집]

레지스터 할당: 컴파일러가 변수를 물리 레지스터에 배정하는 문제. 생존구간이 겹치는 두 변수를 간선으로 잇는 간섭 그래프를 $K$ (레지스터 개수) 색으로 칠하면 된다. 차이틴(1981)의 고전적 방법은 차수가 $K$ 미만인 정점을 계속 떼어내다가 막히면 변수 하나를 메모리로 내보낸다(spill). ” $\chi > K$ 면 코드가 느려진다”가 문자 그대로 성립하는 드문 현장.
시간표·주파수 배정: 동시에 열 수 없는 두 과목을 잇고 칠하면 교시 수가 채색수다. 무선 기지국 채널 배정은 간섭 반경이 여러 겹이라 “거리 2 이내는 다른 색” 같은 변종(L(2,1) 라벨링)을 쓴다.
스도쿠: 81개 칸을 정점으로, 같은 행·열·박스를 간선으로 하면 9-채색 문제 그 자체다. 좋은 예제이자, 사람이 손으로 푸는 방식이 왜 제약 전파를 닮았는지에 대한 설명이기도 하다.
그래프 분할과의 차이: 분할은 “덩어리를 균등하게 나누되 자르는 간선을 줄인다”, 색칠은 “인접한 것끼리 갈라놓는다”. 목적이 정반대라서 도메인 분해 병렬화에는 분할을, 스레드 내부 순서 잡기에는 색칠을 쓴다. 대형 코드는 보통 둘 다 쓴다.

8. 관련 문서[편집]

힙에 (포화도, 차수) 를 사전식 키로 넣고, 정점 하나를 칠할 때마다 그 이웃들의 키를 올려 주면 된다. 갱신 횟수가 간선 수만큼이므로 $O((V+E)\log V)$ . 다만 실측에서는 포화도 값이 작은 정수라 버킷 배열이 힙보다 빠른 경우가 흔하다 — 우선순위 큐 문서에서 되풀이되는 그 이야기다. ↩
당시 수학계 반응은 “증명인가 계산인가”로 갈렸다. 사람이 전부 검토할 수 없는 1200시간짜리 케이스 분석을 증명으로 인정할 것인가 하는 논쟁이 수십 년 이어졌고, 2005년 형식화로 사실상 종결됐다. 그 사이 아펠-하켄 증명에서 실제로 오류가 몇 건 발견되긴 했는데, 전부 수정 가능한 종류였다는 점이 오히려 방법론의 신뢰를 올렸다. ↩
Curtis, Powell, Reid (1974), J. Inst. Math. Appl. 13, 117–119 / Coleman, Moré (1983), SIAM J. Numer. Anal. 20, 187–209. CPR 원논문은 채색이라는 말을 쓰지 않고 “그룹 나누기”로 서술했는데, 9년 뒤 그것이 정확히 채색수 문제였음이 밝혀진 셈이다. 수치해석과 조합최적화가 서로 모르고 같은 문제를 풀던 시절의 유물. ↩
평활화 인자는 조대격자가 못 잡는 고주파 성분에 대한 감쇠율이라, 전체 수렴률이 아니라 다중격자 사이클 안에서의 성능 지표다. 적흑이 0.25 인 것은 표준 2배 조대화 기준이며 스텐실·조대화 방식이 바뀌면 숫자도 바뀐다. “적흑이 무조건 좋다”가 아니라 “모델 문제에서 병렬성을 공짜로 얻는다”가 정확한 요약이다. ↩