GraphStream - Welsh-Powell

GraphStream - Welsh-Powell
This is an iterative greedy algorithm:

• Step 1: All vertices are sorted according to the decreasing value of their degree in a list V.
• Step 2: Colors are ordered in a list C.
• Step 3: The first non colored vertex v in V is colored with the first available color in C. <i>available</i> means a color that was not previously used by the algorithm.
• Step 4: The remaining part of the ordered list V is traversed and the same color is allocated to every vertex for which no adjacent vertex has the same color.
• Step 5: Steps 3 and 4 are applied iteratively until all the vertices have been colored.

图的m色判定问题: 给定无向连通图G和m种颜色。用这些颜色为图G的各顶点着色.问是否存在着色方法,使得G中任2邻接点有不同颜色。

图的m色优化问题:给定无向连通图G,为图G的各顶点着色, 使图中任2邻接点着不同颜色,问最少需要几种颜色。所需的最少颜色的数目m称为该图的色数。

若图G是可平面图,则它的色数不超过4色(4色定理).
4色定理的应用:在一个平面或球面上的任何地图能够只用4种
颜色来着色使得相邻的国家在地图上着有不同颜色

a).将G的结点按照度数递减的次序排列.

b).用第一种颜色对第一个结点着色,并按照结点排列的次序 

   对与前面着色点不邻接的每一点着以相同颜色.

c).用第二种颜色对尚未着色的点重复步骤b).用第三种颜色

   继续这种作法, 直到所有点着色完为止.

1. typedef structNode{ //定义节点结构体  
2.    int index; //编号  
3.    int degree; //度  
4.    int color; //改节点的颜色  
5. } Node;  
6.    
7. Nodenodes[10];  
8.    
9. bool com(Nodenode1,Nodenode2) { //按度从高到低排序  
10.    return node1.degree > node2.degree;  
11. }  
12.    
13. bool com2(Nodenode1,Nodenode2) { //按度从高到低排序  
14.    return node1.index < node2.index;  
15. }  

1.       sort(nodes,nodes + m, com);  
2.       int k = 0;//K 代表第几种颜色  
3.       while (true) {  
4.          k++;  
5.          int i;  
6.          for (i = 0; i < m; i++){//先找到第一个未着色的节点  
7.             if (nodes[i].color == 0) {  
8.                 nodes[i].color = k;  
9.                 break;  
10.             }  
11.          }  
12.          if (i == m)//循环退出的条件,所有节点都已着色  
13.             break;  
14.          //再把所有不和该节点相邻的节点着相同的颜色  
15.          for(int j=0; j<m; j++){  
16.             if(nodes[j].color ==0 &&map[nodes[i].index][nodes[j].index] == 0  
17.                    &&i!=j)  
18.                 nodes[j].color = k;  
19.          }  
20.       }  

Read full article from GraphStream - Welsh-Powell