그래프 색칠(탐욕) 계산기
같은 색을 쓸 수 없는 짝 목록을 넣으면 탐욕 알고리즘으로 색을 칠하고 몇 가지 색이 드는지 계산합니다. 칠하는 순서를 바꿔 가며 결과가 달라지는 것과, 최소 색깔 수의 상한·하한을 함께 보여 줍니다.
같은 색을 쓸 수 없는 짝 (한 줄에 하나)
«수학 물리»는 두 과목을 같은 시간에 둘 수 없다는 뜻입니다. 주파수 배정이나 레지스터 할당도 같은 문제입니다.
비워도 됩니다. 순서에 따라 색 수가 어떻게 달라지는지 볼 때 씁니다.
가장 적게 쓴 색
3가지
입력에 나온 순서로 칠했을 때 · 하한 3 ~ 상한 4
| 칠하는 순서 | 쓴 색 | 순서 |
|---|---|---|
| 입력에 나온 순서 | 3 | 수학 → 물리 → 화학 → 생물 → 지구 |
| 차수 내림차순 (웰시-파월) | 3 | 화학 → 물리 → 생물 → 수학 → 지구 |
| 이름 오름차순 | 3 | 물리 → 생물 → 수학 → 지구 → 화학 |
계산 방법
- 1같은 색을 쓸 수 없는 짝을 한 줄에 하나씩 넣습니다.
- 2세 가지 순서(입력순·차수 내림차순·이름순)의 결과를 견줍니다.
- 3칠하는 순서를 직접 넣어 색 수가 어떻게 달라지는지 봅니다.
- 4하한(가장 큰 클리크)과 상한(최대 차수+1) 사이에 답이 있는지 확인합니다.
자주 묻는 질문
정점을 하나씩 보며 이웃이 쓰지 않은 가장 작은 번호의 색을 주는 탐욕 알고리즘을 씁니다. 빠르고 언제나 유효한 색칠을 주지만, 최소 색깔 수를 보장하지는 않습니다. 최적 채색은 NP-난해라 정점이 조금만 늘어도 모두 훑을 수 없습니다.
크게 바꿉니다. 왕관 그래프는 두 색이면 충분한데 a1·b1·a2·b2… 순서로 탐욕을 돌리면 세 색을 씁니다. 정점 수를 늘리면 이 차이가 얼마든지 벌어집니다. 그래서 차수가 큰 정점부터 칠하는 웰시-파월 같은 요령을 쓰지만, 그것도 최적을 보장하지는 않습니다.
위아래로 범위를 좁힙니다. 서로 다 이어진 k개 무리(클리크)가 있으면 최소 k가지는 필요하므로 그것이 하한이고, 탐욕은 언제나 최대 차수 + 1 안에서 끝나므로 그것이 상한입니다. 답이 하한과 같으면 그 답이 최적임이 확실합니다.
홀수 길이 사이클이 없으면(이분 그래프이면) 두 색으로 됩니다. 너비 우선으로 번갈아 칠해 보다가 어긋나는 곳이 나오면 홀수 사이클이 있는 것입니다. 두 색인지는 이렇게 쉽게 판정되지만, 세 색부터는 갑자기 어려운 문제가 됩니다.
시험 시간표(같은 학생이 듣는 두 과목은 같은 시간에 둘 수 없다), 주파수 배정(가까운 기지국끼리 같은 주파수를 쓸 수 없다), 컴파일러의 레지스터 할당(동시에 살아 있는 변수는 같은 레지스터에 둘 수 없다)이 모두 이 문제입니다. 색이 곧 시간대·주파수·레지스터입니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 탐욕 알고리즘의 결과는 «유효한 색칠»이지 «최소 색칠»이 아닙니다. 하한과 답이 같을 때만 최적임이 확실합니다.
- 하한으로 쓰는 클리크 크기는 정점이 적을 때 실제로 찾아 구한 값입니다. 클리크가 없어도 색이 더 필요한 그래프가 있어(예: 홀수 사이클) 하한이 언제나 촘촘하지는 않습니다.
- 상한 «최대 차수 + 1»은 탐욕이 보장하는 값입니다. 완전그래프와 홀수 사이클을 빼면 최대 차수만으로도 칠할 수 있다는 브룩스 정리가 있지만 여기서는 다루지 않습니다.
- 자기 자신을 가리키는 선은 무시합니다. 자기와 다른 색을 쓸 수는 없어 애초에 색칠이 불가능해지기 때문입니다.
- 정점은 26개까지 봅니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.