그래프에 겹치지 않게 색을 칠해본 경험 다들 있을 것이다. 이번 챕터에서는 이러한 색칠하기의 새로운 쓸모를 알아볼 수 있다. 스케줄링, 컴파일러 최적화, 공항 게이트 배정까지 — 생각보다 쓸모가 많다.1. 동기: 스케줄링 문제 6명의 과학자가 5개의 장비를 공유해야 한다. 같은 장비가 필요한 과학자들은 동시에 일할 수 없다. 최소 몇 개의 시간 블록이 필요할까? 이걸 그래프로 모델링하면:Vertex = 과학자Edge = 충돌 (같은 장비 필요)Color = 시간 블록 인접한 두 vertex(= 충돌하는 두 과학자)는 반드시 다른 색(= 다른 시간대)이어야 한다. 최소 몇 가지 색으로 칠할 수 있는지 구하면 답이 나온다.2. 핵심 정의Coloring: 함수 c: V → CC는 색의 집합인접한 두 vert..
