8.2.1 图着色问题.ppt

* 第8章 流塑法 8.2.1 图着色问题 8.2.1 图着色问题 图着色问题描述为：给定无向连通图G=(V, E)和正整数m，求最小的整数m，使得用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。 由于用m种颜色为无向图G=(V, E)着色，其中，V的顶点个数为n，可以用一个n元组C=(c1, c2, …, cn)来描述图的一种可能着色，其中，ci∈{1, 2, …, m} (1≤i≤n)表示赋予顶点i的颜色。 例如，5元组(1, 2, 2, 3, 1)表示对具有5个顶点的无向图的一种着色，顶点1着颜色1，顶点2着颜色2，顶点3着颜色2，如此等等。 如果在n元组C中，所有相邻顶点都不会着相同颜色，就称此n元组为可行解，否则为无效解。 流塑法求解图着色问题，首先把所有顶点的颜色初始化为0，然后依次为每个顶点着色。在图着色问题的解空间树中，如果从根结点到当前结点对应一个部分解，也就是所有的颜色指派都没有冲突，则在当前结点处选择第一棵子树继续有哪些信誉好的足球投注网站，也就是为下一个顶点着颜色1，否则，对当前子树的兄弟子树继续有哪些信誉好的足球投注网站，也就是为当前顶点着下一个颜色，如果所有m种颜色都已尝试过并且都发生冲突，则流塑到当前结点的父结点处，上一个顶点的颜色被改变，依此类推。 设数组color[n]表示顶点的着色情况，流塑法求解m着色问题的算法如下： 算法8.1——图着色问题 1．将数组color[n]初始化为0； 2．k=1; 3．while (k=1) 3.1 依次考察每一种颜色，若顶点k的着色与其他顶点的着色不发生冲突，则转步骤3.2；否则，有哪些信誉好的足球投注网站下一个颜色； 3.2 若顶点已全部着色，则输出数组color[n]，返流； 3.3 否则， 3.3.1 若顶点k是一个合法着色，则k=k+1，转步骤3处理下一个顶点； 3.3.2 否则，重置顶点k的着色情况，k=k-1，转步骤3流塑； 算法8.2—— 图着色问题 void GraphColor(int n, int c[ ][ ], int m) //所有数组下标从1开始 { for (i=1; i=n; i++ ) //将数组color[n]初始化为0 color[i]=0; k=1; while (k=1) { color[k]=color[k]+1; while (color[k]=m) if Ok(k) break; else color[k]=color[k]+1; //有哪些信誉好的足球投注网站下一个颜色 if (color[k]=m k= =n) //求解完毕，输出解 { for (i=1; i=n; i++) coutcolor[i]; return; } else if (color[k]=m kn) k=k+1; //处理下一个顶点 else { color[k]=0; k=k-1; //流塑 } } } bool Ok(int k) //判断顶点k的着色是否发生冲突 { for (i=1; ik; i++) if (c[k][i]= =1 color[i]= =color[k]) return false; return true; } 一般情况下，在问题的解向量X=(x1, x2, …, xn)中，分量xi (1≤i≤n)的取值范围为某个有限集合Si={ai1, ai2, …, airi}，因此，问题的解空间由笛卡儿积A=S1×S2×…×Sn构成，并且第1层的根结点有|S1|棵子树，则第2层共有|S1|个结点，第2层的每个结点有|S2|棵子树，则第3层共有|S1|×|S2|个结点，依此类推