알고리즘: 그래프 색칠하기(m-coloring)(Backtracking 문제)

m-coloring 문제는 비방향그래프에서 서로 인접한 정점이 같은 색을 같지 않도록 

m개의 다른 색으로 칠하는 방법을 찾는 문제다.

 

 

예를 들어, 이 그래프에서는 두 가지 색으로

문제를 푸는 것은 불가능하다. 

 

세가지 색을 이용하면 6가지의 해답을 얻을 

수 있다

 

 

 

 

 

 

 

 

 

 

그래프 색칠하기의 주요 응용분야는 지도 색칠하기이다.

(이외에도 GSM에서 주파수 할당문제, Aircraft scheduling, final exam timetable등에 사용된다)

 

여기서 우리는 지도를 평면그래프(planar graph)로 나타낼 수 있는데

 

평면그래프란 두 개의 이음선이 서로 교차하지 않도록 그린 그래프를 말한다.

 

다음은 왼쪽의 지도를 평면그래프로 나타낸 것이다. 

 

 

(만약 v1과 v5를 연결하거나 v2와 v4를 연결한다면 평면 그래프가 아니다)

 

이 그래프 색칠하기 문제에서 되추적을 이용하여 색칠가능한 모든 경우를 구할 수 있다. 

 

어떤 마디에서 색칠한 정점과 인접한 정점이 이미 그 마디에 사용된 색인 경우 그 마디는

유망하지 않기 때문이다. 

 

 

 

다음은 위에서 다른 평면 그래프의 상태공간트리 일부이다. 

(유망하지 않은 마디는 x로 처리되어 있다)

 

 

- v1: v1에서 색1을 색칠한다.

 

- v2: v1에서 색1을 칠한 후, v2에서 색1을 칠하면 v1과 v2는 연결되어 있기 때문에

유망하지 않다. 따라서 색2를 선택한다. 

 

- v3: v1과 v3은 연결되어 있으므로 색1은 유망하지 않고, v2과 v3은 연결되어 있으므로 

색2는 유망하지 않다. 따라서 색3을 선택한다.  

 

위와 같은 과정을 반복하여 되추적한다.

 

 

 

 

그렇다면 위 문제를 수도코드를 통해 더 자세히 알아보자 

 

void m_coloring(index i){

	int color;
    if(promising(i))
    	if(i==n)
        	cout<<vcolor[1] 에서 vcolor[n]까지;
        else
        	for(color=1; color<=m; color++){  // 다음 정점의 모든 색을 시도해본다. 
            vcolor[i+1] = color;  //dfs
            m_coloring(i+1);
            }
}

bool promising(index i){
	index j;
    bool switch = true;
    j = 1;
    while(j < i && switch){
    if(W[i][j] && vcolor[i] == vcolor[j])  // 연결되어 있고 색이 같은지 
    	switch = false;
    j++;
    }
    return switch;
}

 

 

 

 

이 알고리즘의 상태공간트리에 있는 마디의 개수는 다음과 같다. 

 

 

또한 이 되추적 알고리즘의 추정시간을 확인하는 몬테칼로 알고리즘을

 

이용하여 걸리는 시간을 확인할 수도 있다.

 

 

알고리즘: 몬테칼로 알고리즘을 이용한 효율성 추적!

출처 : Foundations of Algorithms, Using C++ Pseudocode