개념
인접한 노드는 다른 색을 가져야 하는 문제. 지도, 일부 시간표·주파수·레지스터 할당처럼 충돌 관계를 그래프로 모델링할 수 있을 때 유용하다.
한 호흡으로 이해하기
"인접한 영역이 다른 색을 갖도록 지도를 칠하려면 몇 가지 색이 필요한가?" 1852년 한 학생의 단순한 질문은 124년 후 컴퓨터에 핵심 검증을 맡긴 첫 주요 정리 가운데 하나인 4색 정리로 이어졌다. 학교 시간표·주파수 할당·컴파일러 레지스터 할당도 그래프 색칠로 모델링할 수 있다.
한눈에 보기
그래프 종류 | χ(G) | 실제 응용 |
|---|---|---|
평면 지도 (4색 정리) | ≤ 4 | 국가 지도, GIS |
이분 그래프 (홀수 사이클 없음) | 2 | 학생-과목 매칭 |
n-clique (Kₙ) | n | 완전 그래프 |
홀수 길이 사이클 | 3 | 시간표 충돌 |
Petersen 그래프 | 3 | 교과서 단골 |
트리 | 2 | 계층 구조 |
χ(G) = G의 색칠 수. 인접 정점이 다른 색이어야 하는 최소 색 수. NP-완전 일반 문제.
핵심 식
χ(G) — 인접 정점이 다른 색을 갖는 데 필요한 최소 색 수
핵심 순간
AD 1852
4색 추측
거스리가 영국 군 지도에서 4색이면 충분함을 추측.
AD 1976
4색 정리 컴퓨터 증명
아펠·하켄이 유한한 경우 환원과 컴퓨터 검증을 결합했다. 컴퓨터 보조로 증명된 첫 주요 정리로 널리 평가된다.
AD 1979
카프 — NP-완전 문제
리처드 카프가 3색 결정 문제가 NP-완전임을 증명. 일반 그래프 색칠은 어려움.
오늘날의 응용
컴파일러의 레지스터 할당, 시간표 작성, 주파수 할당, GIS 지도, 그래픽 카드의 충돌 회피.
MathVoyage 너머로
불러오는 중…