그래프 채색 계산기

그래프 채색 계산기 정보

그래프 채색 계산기는 모든 무방향 그래프에 대한 채색수 χ(G)와 유효한 정점 채색 결과를 계산합니다. 그래프를 간선 리스트나 인접 리스트 형식으로 입력하면 인접한 두 정점이 같은 색을 공유하지 않도록 하는 데 필요한 최소 색상 수와 함께 대화형 SVG 시각화, 애니메이션 DSATUR 추적 및 각 정점에 할당된 색상 상세 내역을 제공합니다.

그래프 채색이란 무엇인가요?

그래프 G = (V, E)의 적절한 정점 채색은 모든 간선의 양 끝점이 서로 다른 색을 갖도록 각 정점에 색을 할당하는 것입니다. 채색수(chi(G)로 표기)는 이러한 채색이 가능한 최소 색상 수를 의미합니다. χ(G)를 계산하는 것은 일반적인 경우 NP-하드(NP-hard) 문제이지만, 수학적으로 매우 흥미로운 이론이며 시험 일정 짜기, 무선 주파수 할당, 컴파일러의 레지스터 할당, 평면 지도의 4색 정리 등 다양한 실무적 응용 분야를 가지고 있습니다.

주요 정리 및 한계값

• 자명한 한계: 모든 그래프에 대해 1 ≤ χ(G) ≤ |V|입니다.
• 클릭 하한선: χ(G) ≥ ω(G)이며, 여기서 ω(G)는 최대 클릭의 크기입니다.
• 이분 그래프 특성: G에 홀수 사이클이 없는 경우에만 χ(G) ≤ 2입니다 (쾨니그의 정리).
• 브룩스의 정리: G가 완전 그래프나 홀수 사이클이 아닌 한 χ(G) ≤ Δ(G)입니다. 여기서 Δ(G)는 최대 차수입니다.
• 4색 정리: 모든 평면 그래프는 4-채색이 가능합니다.
• 탐욕적 상한선: 모든 탐욕 알고리즘은 최대 Δ(G) + 1개의 색상을 사용합니다.

이 계산기에서 사용하는 알고리즘

DSATUR (포화 차수 알고리즘)

1979년 다니엘 브렐라즈(Daniel Brélaz)가 제안한 DSATUR는 그래프 채색을 위한 가장 강력한 실용적 휴리스틱 중 하나입니다. 이 알고리즘은 이웃 정점들이 이미 가장 다양한 색상을 사용하고 있는(포화도가 높은) 미채색 정점을 반복적으로 선택하여 채색하며, 동률일 경우 정점 차수로 결정합니다. 선택된 정점에는 이웃이 사용하지 않는 가장 작은 번호의 색상을 할당합니다. DSATUR는 이분 그래프 및 많은 구조화된 그래프 패밀리에서 최적임을 증명할 수 있으며, 수백 개의 정점이 있는 그래프에서도 밀리초 단위로 고품질 채색을 생성합니다.

Welsh-Powell

Welsh-Powell 알고리즘은 정점들을 차수의 내림차순으로 정렬한 다음 탐욕적으로 채색합니다. O(|V|²) 시간 복잡도를 가지며 최대 Δ(G) + 1개의 색상을 보장합니다. 매우 빠르며 종종 좋은 1차 근사치를 제공하지만, 국소 구조가 다양한 그래프에서는 DSATUR에 뒤처질 수 있습니다.

탐욕 알고리즘 (입력 순서)

가장 단순한 알고리즘입니다. 입력된 순서대로 정점을 훑으며 이미 채색된 이웃이 사용하지 않는 가장 작은 번호의 색상을 할당합니다. 결과는 입력 순서에 민감하지만, 무작위 순서는 더 스마트한 휴리스틱과 비교할 수 있는 기준점을 제공합니다.

정확한 백트래킹

작은 그래프(최대 약 18개 정점)의 경우 계산기는 k = 2, 3, 4, ...를 시도하며 깊이 우선 백트래킹으로 k-채색을 시도하여 실제 채색수를 찾을 수 있습니다. 검색은 차수 내림차순으로 정점을 정렬하며 사용 가능한 색상이 없을 때 가지치기를 수행합니다. 정확한 알고리즘이 성공하면 결과에 "정확함" 레이블이 표시됩니다.

입력 형식

간선 리스트

각 간선을 하이픈(-), 공백 또는 화살표로 구분된 두 개의 정점 레이블로 작성하세요. 간선 사이는 쉼표나 줄바꿈으로 구분합니다. 정점 레이블에는 문자, 숫자 또는 언더바를 사용할 수 있습니다. 예시:

인접 리스트

각 정점, 콜론(:), 그리고 쉼표로 구분된 이웃 목록을 작성하세요. 예시:

정점은 자기 자신과 다른 색으로 칠해져야 하므로 셀프 루프는 거부됩니다. 중복된 간선은 자동으로 하나로 처리되며, 그래프는 무방향 그래프로 간주됩니다.

이 계산기 사용 방법

1. 형식 선택: 라디오 버튼으로 간선 리스트와 인접 리스트 중 하나를 선택합니다.
2. 그래프 입력: 데이터를 붙여넣거나 퀵 예제(삼각형, 완전 그래프 K₅, 피터슨 유사 휠, 이분 그래프 K₃,₃, 시험 일정) 중 하나를 클릭합니다.
3. 알고리즘 선택: 최상의 기본값인 '자동'을 유지하거나 Welsh-Powell, 탐욕, DSATUR 또는 정확한 백트래킹을 강제로 선택합니다.
4. "그래프 채색하기" 클릭: 채색수, 색상별 목록, 드래그 가능한 노드가 있는 대화형 SVG, 단계별 애니메이션 추적이 아래에 나타납니다.
5. 탐색: 재생 버튼을 눌러 알고리즘이 정점을 하나씩 채색하는 것을 확인하고, 노드를 드래그하여 레이아웃을 조정하거나 이전/다음 버튼을 사용하여 수동으로 단계를 넘겨보세요.

그래프 채색의 실제 응용

시험 일정 계획

각 시험을 정점으로 하고, 최소 한 명의 학생을 공유하는 시험 사이에 간선을 그립니다. k개의 색상을 사용한 적절한 채색은 어떤 학생도 일정이 겹치지 않는 k개의 시간대를 제공합니다. 채색수는 필요한 최소 시간대 수입니다.

무선 주파수 할당

서로 간섭 범위 내에 있는 송신기들은 서로 다른 주파수로 방송해야 합니다. 간섭 그래프의 채색수는 필요한 최소 주파수 개수가 됩니다.

레지스터 할당

컴파일러에서 변수의 활성 범위는 정점입니다. 두 활성 범위가 시간적으로 겹치면 그 사이에 간선이 생깁니다. k-채색은 충돌 없이 변수들을 k개의 CPU 레지스터에 할당합니다.

지도 채색

국경을 접하고 있는 국가들은 서로 다른 색으로 칠해져야 합니다. 4색 정리(Appel-Haken, 1976)는 모든 평면 지도에 대해 4가지 색이면 항상 충분함을 증명합니다.

스도쿠 및 제약 퍼즐

완성된 스도쿠는 81개의 셀을 정점으로 하고 같은 행, 열 또는 3×3 박스에 있는 셀들을 간선으로 연결한 그래프의 9-채색 결과입니다. 그래프 채색은 많은 제약 충족 퍼즐의 수학적 핵심입니다.

흥미로운 특수 사례

• 완전 그래프 K_n: χ(K_n) = n입니다. 모든 정점 쌍이 인접해 있으므로 모든 색상이 달라야 합니다.
• 사이클 C_n: n이 짝수이면 χ(C_n) = 2, 홀수이면 3입니다.
• 트리: 정점이 2개 이상인 모든 트리는 χ = 2입니다 (트리는 이분 그래프입니다).
• 이분 그래프: 간선이 하나라도 있으면 χ = 2입니다.
• 피터슨 그래프: χ = 3인 유명한 3-정규 그래프입니다.
• 휠 그래프 W_n: n-사이클에 중심 정점이 연결된 형태입니다. n이 짝수이면 χ = 3, 홀수이면 4입니다.

자주 묻는 질문

그래프의 채색수란 무엇인가요?

채색수 χ(G)는 인접한 두 정점이 같은 색을 공유하지 않도록 그래프의 정점을 칠하는 데 필요한 최소 색상 수입니다. 이분 그래프는 채색수가 최대 2이며, 삼각형을 포함하는 그래프는 최소 3입니다. 브룩스의 정리에 따르면 완전 그래프와 홀수 사이클을 제외하고는 채색수가 최대 차수를 넘지 않습니다.

이 계산기는 어떤 알고리즘을 사용하나요?

작은 그래프의 경우 계산기는 정확한 채색수를 찾기 위해 정확한 백트래킹 검색을 실행합니다. 더 큰 그래프의 경우 이미 채색된 이웃이 가장 많은 정점을 우선적으로 채색하는 DSATUR 휴리스틱을 사용합니다. 알고리즘 드롭다운에서 Welsh-Powell이나 단순 탐욕 알고리즘을 선택할 수도 있습니다.

그래프를 어떻게 입력해야 하나요?

간선 리스트 모드에서는 한 줄에 A-B와 같이 간선 하나를 입력하거나, A-B, B-C와 같이 쉼표로 구분하여 입력합니다. 인접 리스트 모드에서는 정점 뒤에 콜론과 그 이웃들을 씁니다(예: A: B, C). 셀프 루프는 허용되지 않습니다.

DSATUR가 항상 실제 채색수를 찾지 못하는 이유는 무엇인가요?

그래프 채색은 NP-하드 문제이므로 항상 최적의 답을 내는 빠른 알고리즘은 존재하지 않습니다. DSATUR는 매우 강력한 휴리스틱이지만 특수한 경우에는 필요한 것보다 더 많은 색을 사용할 수 있습니다. 계산기는 사용된 색상 수와 함께 하한선(최대 클릭)을 제공하여 결과의 신뢰도를 판단할 수 있게 돕습니다.

그래프 채색의 실생활 예는 무엇인가요?

시험 시간표 작성, 무선 주파수 할당, 컴파일러 최적화, 지도 제작, 스도쿠 풀이, 충돌 제약이 있는 작업 할당 등이 있습니다.

채색수는 항상 최대 클릭 크기와 같나요?

아니요. 클릭 수 ω(G)는 항상 하한선일 뿐입니다. 이분 그래프나 트리 같은 완벽 그래프에서는 서로 같지만, 일반적인 그래프에서는 채색수가 클릭 수보다 훨씬 클 수 있습니다.

이 계산기가 처리할 수 있는 최대 그래프 크기는 얼마인가요?

최대 60개의 정점과 600개의 간선을 지원합니다. 정확한 알고리즘의 경우 정점이 약 18개를 넘어가면 백트래킹 속도 문제로 DSATUR로 전환될 수 있습니다. 이는 대부분의 교육용 예제나 소규모 실무 문제를 처리하기에 충분한 수치입니다.

더 읽어보기

• 그래프 채색 — 위키백과
• DSATUR 알고리즘 — Wikipedia
• 채색 다항식 — 위키백과
• 4색 정리 — 위키백과
• 브룩스의 정리 — Wikipedia