[알고리즘] 되추적(Backtracking) - Part 2 그래프색칠하기(Graph Coloring)

* m - 색칠하기 문제
 비방향 그래프에서 서로 인접한 종점들이 같은 색을 갖지 않도록 하면서 최대 m개의 다른 색으로 칠하는 모든 방법을 찾아라. 

 

 
* 평면그래프(Planar graph)
 - 평면 상에서 연결선들이 서로 교차하지 않는 그래프

옆 그래프는 연결선이 서로 교차하지 않으므로 평면 그래프라고 할 수

있다. 위 그래프에서 두개의 연결선 (v1,v5)와 (v2,v3)를 추가하면 연결

선중 일부는 교차하게 되고, 이에 따라 평면 그래프가 될 수 없다.









* 지도와 평면 그래프
 - 지도에서 각 지역을 그래프의 정점으로 하고, 한 지역이 어떤 다른 지역과 인접해 있으면 그 지역들을 나타내는
   정점들 사이에 연결선을 그으면, 모든 지도는 그에 상응하는 평면 그래프로 표시할 수 있다. 

 

* m - 색칠하기 되추적 알고리즘
 - input
  > n : 그래프내의 정점들의 수
  > vcolor[1..n] : 각 노드별 색
  > m : 칠할 수 있는 색들의 수
  > W : 비방향 그래프를 나타내는 인접행렬(배열)
 - source
 void m-coloring(int i){
   int color;
   if ( promising(i) )
     if ( i == n ) " vcolor[1..n]을 출력";
     else // 다음 정점에 모든 색을 시도해본다.
     for ( color = 1 ; color <= m ; color++ ){ 
       vcolor[i+1] = color;
       m-coloring(i+1);
     } 
 }
 boolean promising(int i){
   int j = 1;
   boolean switch = true;
   while ( j < i && switch ) { // 인접한 정점에 같은 색이 이미 칠해져 있는지 점검한다.
     if ( w[i][j] && vcolor[i] == vcolor[j] )switch = false;
     j++;
   }
   return switch;
 } 

 - 분석 : 상태공간 트리상의 노드들의 총수 = 1 + m + m^2 + ... + m^n
                                                          = (m^(n+1) - 1) / (m - 1)