그래프 채색

이 계산기에 대하여

그래프 색칠 계산기는 채색수 χ(G) — 같은 색의 두 꼭짓점을 잇는 변이 없도록 그래프의 꼭짓점을 칠하는 데 필요한 최소 색 수 — 를 구하고 최적 색칠 하나를 보여 줍니다. 꼭짓점 수와 변 목록을 입력하면 분기 한정 탐색으로 χ를 정확히 계산하고, 최대 차수 Δ와 최대 클리크 ω(χ의 하한)를 알려 주며, 이분 그래프와 완전 그래프를 표시하고, 색칠된 그래프를 그립니다. 일정 편성, 레지스터 할당, 지도 색칠, 채색수 학습에 유용합니다.

그래프를 색칠하는 방법

1. 꼭짓점 수를 입력하세요. 꼭짓점에는 1부터 n까지 번호가 매겨집니다.
2. 변을 1-2, 2-3 같은 쌍으로 나열하세요 — 연결 하나에 쌍 하나입니다.
3. 채색수 χ(G)와 각 꼭짓점에 배정된 색을 확인하세요.
4. χ를 최대 클리크 ω와 비교해 왜 그만큼의 색이 필요한지 알아보거나, 프리셋을 불러와 살펴보세요.

대표적인 예

• 삼각형(K₃)은 3가지 색이 필요합니다 — 모든 꼭짓점 쌍이 인접하기 때문입니다.
• 짝수 순환 그래프는 이분 그래프이므로 2가지 색이면 충분하고, C₅ 같은 홀수 순환 그래프는 3가지 색이 필요합니다.
• 완전 그래프 Kₙ은 정확히 n가지 색이 필요합니다.
• 크기 ω인 최대 클리크는 최소 ω가지 색을 요구하므로 χ(G) ≥ ω입니다.
• 그뢰치 그래프는 삼각형이 없는데도 4가지 색이 필요하므로, χ는 클리크 수보다 클 수 있습니다.