K-Graph Coloring

K-Graph Coloring

---

Graph Coloring

정점, 간선, 면을 기준으로 인접한 구성 요소가 같은 색이 되지 않도록 칠하는 문제

간선, 면 채색이 정점 채색으로 변환 가능하기 때문에, 대개 정점 채색을 의미

• 간선 채색: 선 그래프에 대한 정점 채색 문제로 변환가능
• 면 채색: 이중(Dual) 그래프에 대한 정점 채색 문제로 변환가능
• 루프를 갖는 정점은 채색이 불가능하므로 루프가 없는 그래프를 대상

K-Graph Coloring

최대 k 개의 서로 다른 색을 가지고, 정점 채색이 가능한지 확인하는 결정 문제
가능 여부만을 확인

어떤 색인지는 중요하지 않기 때문에, 색을 정수로 표현 (1, 2, 3)

그래프의 채색수 (Chromatic Number)

그래프를 채색하기 위해 최소로 필요한 색깔의 수를 알아내는 문제

• n정점 완전 그래프(모든 정점이 연결된-인접한): n
• 트리: 2
• 단순한 지도: 3색이면 충분
  • 홀수개의 영역에 둘러싸인 영역이 있다면: 4
  • 지도를 그릴 때 나라 구분을 색으로 하는데, 과거 잉크가 비싸서 최소한의 색으로 표시하고자

응용

• 컴파일러에서의 레지스터 할당 문제를 모델링
  • 목적 코드의 실행 시간을 줄이기 위하여 코드최적화에서 사용하는 기술 중 하나는 컴파일된 프로그램내의 자주 쓰이는 값을 이왕이면 빠른 레지스터에 배정
  • 변수를 정점으로, 동시에 필요한 변수들 사이를 간선으로 나타내는 간섭 그래프를 구축하고 k 색으로 채색 가능하다면 어떤 경우라도 동시에 필요한 변수들을 최대 k 개의 레지스터에 저장 가능

스도쿠: 9-채색 문제를 81정점 그래프에 적용하는 것

• 다양한 스케줄링 문제
  • 각 작업들에 동일한 시간을 할당한다고 가정할 때, 각 작업을 정점으로 하고, 겹쳐서 진행할 수 없는 작업들을 간선으로 연결한 그래프를 생각해보자. 이 그래프를 대상으로 채색수를 구한다면 이로부터 최소 완료 시간을 구할 수 있음

Solve By BackTracking

---

i.e. 지도 채색 문제
면 채색 → 정점 채색, 각 영역(정점)에 1 ~ n까지 번호를 매김

상태 공간 트리

아무것도 칠하지 않은 비어있는 지도에서 출발
레벨 i의 노드들은 정점 1에서부터 차례대로 정점 i 까지 채색한 상태
단말 노드의 레벨은 당연히 n
유망하지 않은 노드를 판별: 인접한 정점은 같은 색으로 칠해서는 안 된다!!

@ KGC_0000, Start 노드로 시작해서 내려가는, 각 노드에는 (정점, 색)으로 마킹된 상태 공간 트리
@ KGC_0001, Start 노드로 시작해서 내려가는, 각 노드에는 (정점, 색)으로 마킹된, 유망하지 않은 노드는 x로 표시하고 패스한, 최종 상태 노드가 표시된, 상태 공간 트리

가능 여부만 찾으면 되기 때문에, 최종 상태 노드를 찾으면 끝

알고리듬

Back-Tracking, 실제로 트리를 만들지는 않고, 각 레벨에 해당하는 상태 정보를 배열에 저장한다.

• 배열을 이용하여 상태 공간 트리를 관리하는 방법
  • 기억해야 할 정보는 “걸어온 길”
  • 레벨 i 노드는 i 개의 정점의 색을 기억해야 함
    • 해당 노드가 유망하여 자식 노드로 내려간다면, 다음 단계에 i + 1개 정점의 색을 기억
    • 해당 노드가 유망하지 않아 부모 노드로 되돌아간다면, 다음 단계에 i - 1개 정점의 색을 기억

인덱스	1	2	3	4	5	6	7	8	9
색	1	2	2	3	1	2	1	1	3

@ KGC_0002

• 배열 인덱스: 정점
• 배열 값: 해당 정점을 칠한 색

∴ n 개의 색을 저장할 수 있는 1차원 배열이 필요

구현

ColoringBT(0) 을 호출함으로써 시작

void ColoringBT(int i) // 노드가 아니라 레벨, 레벨에 대한 처리
{
    if (!Promising(i)) // 유망하지 않으면 패스
        return;

    // 마지막 행이면 끝
    // 왜 바로 끝이냐면, 유망한 노드에 대해서만 검사를 하니까 (위에서 검사)
    // + 가능 여부만 찾으면 되니까
    if (i == n) 
    {
        OutputSolution(i);
        Exit(); // 대충 끝나는 함수
    }
    // 마지막 레벨이 아니면
    // 자식 노드들에 대해서 검사
    else
    {
        for (int c = 1; c <= k; c++)
        {
            color[i + 1] = c;
            ColoringBT(i + 1);
        }
    }
}

bool Promising(int i)
{
    // 유망하지 않은 경우
    // 1. 인접하고: graph[i][j]
    // 2. 색이같음: color[i] == color[j]
    for (int j = 0; j < i; j++)
    {
        if (graph[i][j] && color[i] == color[j])
            return false;
    }
    return true;
}

분석

상태 공간 트리의 노드 수

\[1 + k + k^2 + ... + k^n = {(k^{n+1} - 1) \over (n-1)}\]

결정 문제이고 효율적 가지치기가 이루어지므로, 시간 복잡도는 크더라도, 실제 방문 노드 수는 훨씬 적음
아시아 46개국만을 대상 -> 약 1.3 × 10^22

@ KGC_0001 예시는 총 29,524개의 노드 가운데 17개 노드만 방문
@ 같은 노드 수라도 연결된 방식이 다르면 전혀 다른 결과가 나옴

유망한 노드 수

• 해밀턴 사이클 문제처럼 유망한 노드 개수를 계산할 수 없음
• 같은 개수의 정점이라 하더라도 입력 그래프에 따라 유망한 노드의 수가 달라짐
• 아주 빨리 해답을 얻을 수도 있고 상태 공간 트리를 모두 뒤져야 할 수도 있음