그래프 색칠에서 Greedy와 Welsh-Powell을 선택하는 기준

인접 관계를 색으로 분리하는 문제

그래프 색칠은 무향 그래프 G=(V,E)에서 모든 간선 (u,v)에 대해 color(u) ≠ color(v)가 되도록 정점에 색을 배정하는 문제다. 색은 실제 색상일 필요가 없으며, 서로 충돌해서는 안 되는 자원이나 시간을 구분하는 식별자로 쓰인다.

이때 색수(Chromatic Number) χ(G)는 유효한 색칠에 필요한 최소 색의 개수다. 정확한 색수를 구하는 일은 NP-난해 문제에 속한다. 따라서 규모가 큰 그래프에서는 최적해보다 빠르게 얻을 수 있는 상한이 운영 계획에 더 실용적인 경우가 많다.

Greedy Coloring은 주어진 정점 순서대로 가능한 가장 작은 색을 배정하는 탐욕적 휴리스틱이다. Welsh-Powell은 정점 차수를 내림차순으로 정렬한 뒤 같은 규칙을 적용한다. 후자는 자연 순서나 무작위 순서보다 색 수를 줄이는 경향이 있다.

정점 순서가 결과를 바꾸는 이유

색칠 과정에서는 이미 색이 정해진 인접 정점의 색 집합을 모은 뒤, 그 집합에 없는 가장 작은 색 인덱스를 선택한다. 구현은 단순하지만 어떤 정점을 먼저 처리하는지가 결과에 직접 영향을 준다.

Greedy Coloring은 입력 순서에 강하게 좌우된다. Welsh-Powell은 차수가 큰 정점을 먼저 처리해 충돌 가능성이 큰 정점의 색을 먼저 정함으로써 이 영향을 일부 완화한다. 다만 동률인 정점의 처리 순서에 따라 결과가 달라질 수 있으므로, 재현성이 필요한 환경에서는 보조 타이브레이커를 고정해야 한다.

Greedy와 Welsh-Powell은 색 수의 상한을 제공하며 최적성을 보장하지 않는다. 기본 구현의 시간 복잡도는 O(V^2 + E)이고, 인접 리스트를 최적화하면 O(E log V) 수준까지 가능하다. Welsh-Powell은 정렬을 포함해 O(V log V + E)다. 대규모 그래프에서도 선형~준선형 시간으로 확장할 수 있는 이유다.

색 배정이 진행되는 흐름

⤢✕

자기 루프가 있는 그래프는 유효하게 색칠할 수 없으므로 오류로 처리해야 한다. 비연결 그래프는 같은 절차를 적용할 수 있고, 각 연결 성분을 독립적으로 처리할 수 있다.

상한 해법과 정확 해법의 차이

항목	Greedy	Welsh-Powell	정확 색수(백트래킹/ILP)
성능(시간 복잡도)	O(V^2+E)	O(V log V + E)	지수적, 소규모에 한해 실용
확장성	대규모 실무 적용 용이	대규모 실무 적용 용이	제한적
최적성/일관성	최적 미보장, 순서 민감	상한 개선 경향, 동률 민감	최적 보장
안정성(결과 변동성)	높음	중간	낮음(결정적 탐색 시)
운영 편의	구현 단순, 유지보수 용이	단순, 차수 계산 필요	모델링/튜닝 부담 존재

정확 색수 계산은 최적해가 반드시 필요한 작은 문제에 맞는다. 반면 빠른 계획 수립이 목적이라면 Greedy나 Welsh-Powell로 상한을 먼저 구하고, 병목 구간에만 정확 해법이나 로컬 개선을 적용할 수 있다.

충돌 관계를 운영 자원에 매핑하는 방식

작업 스케줄링에서는 상호 배타적인 작업을 정점으로, 자원 충돌을 간선으로 표현한다. 색은 시간 슬롯이 되며 Welsh-Powell 기반 상한은 슬롯 수를 줄이는 데 활용할 수 있다.

컴파일러의 레지스터 할당에서는 변수 간 간섭 그래프의 색을 레지스터에 대응시킨다. Greedy와 우선순위 순서를 조합해 스필을 최소화하려고 한다.

무선 주파수 할당에서는 기지국 간 간섭 관계를 간선으로 만들고, 색을 주파수 채널로 사용한다. 차수가 높은 노드를 먼저 배정하는 방식은 혼신을 줄이는 데 쓰인다.

시험 편성이나 좌석 배치도 같은 구조를 갖는다. 충돌 관계를 간선으로 정의한 뒤 색을 시험 회차나 구역으로 매핑하면, 색수 상한을 바탕으로 최소 회차 계획을 세울 수 있다.

Welsh-Powell은 무작위 Greedy 순서 대비 색 수가 10~30% 감소할 수 있으며, 이 효과는 그래프 구조에 의존한다. 대규모 그래프에서는 준선형 시간으로 해법을 도출할 수 있어 계획 수립 리드타임을 줄일 수 있다.

Python으로 구현한 색칠과 정확 탐색

전제조건은 Python 3.10+와 인접 리스트 딕셔너리 형태의 무향 단순 그래프다.

# -*- coding: utf-8 -*-
from collections import defaultdict
from typing import Dict, Set, List, Tuple

Graph = Dict[str, Set[str]]

def validate_graph(G: Graph) -> None:
    for v, nbrs in G.items():
        if v in nbrs:
            raise ValueError(f"Self-loop detected at {v}")
        for u in nbrs:
            if v not in G.get(u, set()):
                raise ValueError(f"Asymmetry on edge {v}-{u}")

def greedy_coloring(G: Graph, order: List[str] | None = None) -> Dict[str, int]:
    validate_graph(G)
    if order is None:
        order = list(G.keys())
    color: Dict[str, int] = {}
    for v in order:
        used = {color[u] for u in G[v] if u in color}
        c = 0
        while c in used:
            c += 1
        color[v] = c
    return color

def welsh_powell_coloring(G: Graph) -> Dict[str, int]:
    # Degree descending, tie-break by vertex name for determinism
    order = sorted(G.keys(), key=lambda v: (-len(G[v]), v))
    return greedy_coloring(G, order)

def chromatic_number_backtracking(G: Graph) -> Tuple[int, Dict[str, int]]:
    """
    소규모 그래프 전용 정확 색수 계산
    전략: Welsh-Powell 상한으로 초기화, 백트래킹으로 최적 탐색
    """
    validate_graph(G)
    vertices = sorted(G.keys(), key=lambda v: (-len(G[v]), v))
    upper_coloring = welsh_powell_coloring(G)
    best_k = 1 + max(upper_coloring.values())  # color indices start at 0
    best = upper_coloring.copy()

    color: Dict[str, int] = {}
    def can_color(v: str, c: int) -> bool:
        return all(color.get(u) != c for u in G[v])

    def backtrack(i: int, used_k: int) -> None:
        nonlocal best_k, best
        if used_k >= best_k:
            return
        if i == len(vertices):
            best_k = used_k
            best = color.copy()
            return
        v = vertices[i]
        for c in range(used_k):
            if can_color(v, c):
                color[v] = c
                backtrack(i + 1, used_k)
                del color[v]
        # Try a new color
        color[v] = used_k
        backtrack(i + 1, used_k + 1)
        del color[v]

    backtrack(0, 0)
    return best_k, best

if __name__ == "__main__":
    G: Graph = {
        "A": {"B", "C"},
        "B": {"A", "C", "D"},
        "C": {"A", "B", "D"},
        "D": {"B", "C", "E"},
        "E": {"D"},
    }
    print("Greedy:", greedy_coloring(G))
    print("Welsh-Powell:", welsh_powell_coloring(G))
    k, coloring = chromatic_number_backtracking(G)
    print("Chromatic Number:", k, "Coloring:", coloring)

Greedy의 결과는 입력 정점 순서에 따라 사용하는 색 수가 달라질 수 있다. Welsh-Powell은 차수 우선 순서를 적용해 더 나은 상한을 기대한다. chromatic_number_backtracking은 소규모 그래프에서 χ(G)와 최적 색 배정을 반환한다.

휴리스틱의 품질과 탐색 비용

차수뿐 아니라 포화도(DSATUR), 중심성을 반영한 혼합 순서는 색 수 상한을 개선할 수 있지만 계산 비용이 늘어난다. 희소 그래프에서는 인접 리스트와 비트셋으로 색 집합 검사를 가속할 수 있으며, 이때 메모리와 속도의 균형을 고려해야 한다.

백트래킹, ILP, SAT 기반 탐색은 V≤40 등 소규모이거나 그래프 밀도가 높아 상한과 최적해의 차이가 클 때 적용할 수 있다. 선택 기준은 시간 제한과 필요한 해의 품질이다.

운영 환경에서는 정점 ID나 해시처럼 동률을 해소하는 규칙을 고정해야 결과를 재현할 수 있다. 빠른 상한 산출에는 Welsh-Powell과 국소 개선의 조합이 기본 전략이 될 수 있고, 정확 탐색은 필요한 구간으로 제한하는 편이 적합하다.