图着色问题

图的着色问题主讲人：XXX内容问题来源基本概念常用算法回溯法程序演示问题来源——四色问题•图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。•四色问题：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”问题处理：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。例：图（a）所示的区域图可抽象为图（b）所表示的平面图。区域用城市名表示，颜色用数字表示，则图中表示了不同区域的不同着色问题。图着色问题的分类顶点着色:给定无向图G=(V,E)，用m种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色，这个问题称为图的顶点着色问题。边着色:给定无环图G=(V,E)，用m种颜色为图中的每条边着色，要求每条边着一种颜色，并使相邻两条边有着不同的颜色，这个问题称为图的边着色问题。顶点着色问题的基本概念m可着色：若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同的颜色，则称m为该图的色数。求m的问题称为图的m可着色优化问题。独立集：对图G=(V,E)，设S是V的一个子集，其中任意两个顶点在G中均不相邻，则称S为G的一个独立集。最大独立集：如果G不包含适合|S'|＞|S|的独立集S'，则称S为G的最大独立集。极大覆盖：设K是G的一个独立集，并且对于V-K的任一顶点v，K+v都不是G的独立集，则称K是G的一个极大覆盖。极小覆盖：极大独立集的补集称为极小覆盖。V的子集K是G的极小覆盖当且仅当：对于每个顶点v或者v属于K，或者v的所有邻点属于K（但两者不同时成立）。BACD•独立集：S1={A，D}，S2={B，C}找不到比它们更大的独立集，故S1、S2是最大独立集。•极大覆盖：{A，B，C，D}–S1={B，C}，对于任意的v∈{B，C}，加入集合S1之后，S1不再是一个独立集。S1是一个极大覆盖。例子顶点着色的算法思想由“每个同色顶点集合中的两两顶点不相邻”可以看出，同色顶点集实际上是一个独立集，当我们用第1种颜色上色时，为了尽可能扩大颜色1的顶点个数，逼近所用颜色数最少的目的，事实上就是找出图G的一个极大独立集并给它涂上颜色1。用第2种颜色上色时，同样选择另一个极大独立集涂色，...，当所有顶点涂色完毕，所用的颜色数即为所选的极大独立集的个数。当然，上述颜色数未必就是X（G），而且其和能够含所有顶点的极大独立集个数未必唯一。顶点着色问题的常用算法目前解决该问题的算法很多，如回溯算法、分支界定法、Welsh-Powell算法、布尔代数法、蚁群算法、贪婪算法、禁忌搜索算法、神经网络、遗传算法以及模拟退火算法等。通常的解决着色问题的算法采用蛮力法、贪婪法、深度优先或广度优先等思想可以得到最优解，但时间复杂性太大，如回溯法，其计算时间复杂性为指数阶的；有的在多项式时间内能得到可行解，但不是最优解，如Welsh-Powell算法和贪婪算法。而对于像遗传算法和神经网络这样复杂的启发式算法，通常算法本身复杂性较大，并且算法效率难以分析，最终得到的是近似解，其是否最优解也不能保证。穷举法－WELCHPOWELL着色法步骤：I．将图G中的结点按度数的递减顺序进行排列(这种排列可能不是唯一的，因为有些结点的度数相同)。II．用第一种颜色对第一结点着色，并按排列顺序对与前面着色结点不邻接的每一结点着上同样的颜色。III．用第二种颜色对尚未着色的结点重复II，用第三种颜色继续这种做法，直到所有的结点全部着上色为止。贪心法贪心策略：选择一种颜色，以任意顶点作为开始顶点，依次考察图中的未被着色的每个顶点，如果一个顶点可以用颜色1着色，换言之，该顶点的邻接点都还未被着色，则用颜色1为该顶点着色，当没有顶点能以这种颜色着色时，选择颜色2和一个未被着色的顶点作为开始顶点，用第二种颜色为尽可能多的顶点着色，如果还有未着色的顶点，则选取颜色3并为尽可能多的顶点着色，依此类推。回溯法局部有效着色：如果其中i个顶点已经着色，满足相邻两个顶点的颜色都不一样并且仍有颜色未被使用，就称当前的着色是局部有效着色。无效着色：如果其中i个顶点已经着色，并且存在相邻两个顶点的颜色一样，就称当前的着色是无效着色。着色有效？有节点下移标记死节点没有所有节点颜色都置成零回溯法流程图程序演示开始取节点？着色有颜色可取？存在相邻顶点颜色一样？有完成着色？不存在节点下移未完成当前节点的颜色置零没有返回到上一节点所有节点颜色都置成零取另一种颜色着色存在输出结果没有结束有完成有效着色回溯法解决着色问题流程图例子：邻接矩阵：ABCDEA01100B10111C11001D01001E01110谢谢！