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개 노드만 방문
@ 같은 노드 수라도 연결된 방식이 다르면 전혀 다른 결과가 나옴

유망한 노드 수

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