2013-5-23 3/9
m着色问题 图的 图的m � 图的m着色问题 ： 为无向图的各顶点着色。要求：有边相 邻的顶点不能着同一种颜色。
2013-5-23
4/9
m着色问题 图的 图的m � 解空间：完全m叉树 设X[i]表示第i个节点的填的颜色，1代表填 入颜色1，. . . ，m代表填入颜色m，搜索的 空间为n元一维数组（X[1],X[2],X[3],……， X[n]） mn） � 取值范围 ：（ ：（m 为（1，1，1……，1，1），（1，1，1……，1，2
种颜色 i 时，依次和上层 的每一个节点 j (j<t)比较
a[t][j]=1 && x[t]=x[j]
解空间图示
2013-5-23 7/9
m着色问题 图的 图的m
� 实例演示： 无向图有3个节点，分别相连，用 3种颜色为该 t=1 图着色。
1 2 3 t=2
t=3
t=4
2013-5-23 8/9
），（1，1，1……，2，2），……，（m，m， m……，m，m）。
2013-5-23
5/9
m着色问题 图的 图的m � 解空间图示 ： 以3个节点,3种可用图颜色为例。
解空间图示
2013-5-23 6/9
m着色问题 图的 图的m � 颜色是否可填判断条件 ： 与已填入颜色的节点比较：有边相连 且颜色相同，则不能填入。 新加入来得节点t 取某一
m着色问题 图的 图的m
� private static void backtrack(int t) � { 到达叶节点找到一个解 � if (t>n) sum++; � else � for (int i=1;i<=m;i++) { 颜色能填入向下搜索解 � x[t]=i; � if (ok(t)) backtrack(t+1); � } 判断当前颜色能否填入 � } � private static boolean ok(int k) � {// 检查颜色可用性 � for (int j=1;j<=n;j++) � if (a[k][j] && (x[j]==x[k])) return false; � return true; � } �}
华南师范大学计算机学院 – 计算机算法
图的 m着色问题 图的m
作者：杨劲松
2013-5-23
目录
� 图的m着色问题 � 问题描述 � 实例演示
2013图的 图的m � 国王的遗嘱： 五位王子，想各自立国，可以将国土分 为五份。要求：每个小国都要与其他的四 个小国有共同的国界。 � 四色猜想： 任意一个无飞地的 地图都可以用四种颜色 填色，使得没有两个相 邻国家填的颜色相同。
2013-5-23 9/9