그래프 색칠 (Graph Coloring)

규칙은 딱 하나 — 선으로 이어진 두 점은 서로 다른 색이어야 한다. 이 단순한 퍼즐이 지도 색칠, 시험 시간표 짜기, 컴파일러의 레지스터 배정, 스도쿠, 무선 주파수 할당까지 전부 같은 문제다. 최소 몇 가지 색이면 될까? 이것을 색칠수(chromatic number) χ(G) 라고 부른다.

1. 직접 칠해 보기

정점을 클릭하면 색이 바뀐다(색 없음 → 1번 색 → 2번 색 → … → 다시 색 없음). 이어진 두 정점이 같은 색이면 그 간선이 빨갛게 경고한다. 목표: 충돌 0 을 유지하면서 모든 정점을 칠하되, 되도록 적은 색으로.

2. 색이 몇 개나 필요할까?

3. 순서가 결과를 바꾼다 — Welsh–Powell

탐욕법은 정점을 훑는 순서에 민감하다. 나쁜 순서는 이분 그래프에도 여러 색을 쓰게 만든다(왕관 그래프가 대표적). Welsh–Powell 휴리스틱은 차수가 큰 정점부터 칠한다 — 까다로운 정점을 먼저 처리해서 색 수를 줄이는 경향이 있다. 위 데모의 「탐욕적 색칠」도 차수 내림차순을 쓴다.

# 탐욕적 그래프 색칠 (Welsh–Powell 순서)
def greedy_coloring(adj):            # adj: {정점: set(이웃)}
    order = sorted(adj, key=lambda v: -len(adj[v]))   # 차수 큰 순
    color = {}
    for v in order:
        used = {color[u] for u in adj[v] if u in color}
        c = 0
        while c in used:        # 이웃이 안 쓴 가장 작은 색
            c += 1
        color[v] = c
    return color            # max(color.values())+1 = 쓴 색 개수

4. 같은 문제, 다른 옷