068图的着色.pdf

图的着色图的着色 着色问题着色问题 输入输入： 无向连通图无向连通图 G和和 m 种颜色的集合种颜色的集合 用这些颜色给图的顶点着色，每个用这些颜色给图的顶点着色，每个 顶点一种颜色顶点一种颜色. 要求是：要求是：G 的每条的每条 边的两个顶点着不同颜色边的两个顶点着不同颜色. 三着色实例三着色实例 输出输出：所有可能的着色方案：所有可能的着色方案. 如果不存在着色方案，回答“如果不存在着色方案，回答“No”. 2 实例实例 1 2 3 4 5 6 7 n=7, m=3 3 1 2 3 4 5 6 7 解向量解向量 设设 G=(V,E)，V=1,2, . , n 颜色编号：颜色编号：1, 2, , m 结点的部分向量结点的部分向量 x1, x2, , xk, 1 k n， 表示只给顶点表示只给顶点1,2,.,k着色的部分方案着色的部分方案 解向量解向量：， x1, x2, , xn 1,2, ., m 4 算法设计算法设计 搜索树搜索树：m叉树叉树 搜索策略搜索策略：深度优先：深度优先 约束条件约束条件：在结点：在结点处，处， 顶点顶点 k+1 的邻接表中结点已用过的颜的邻接表中结点已用过的颜 色不能再用色不能再用 如果邻接表中结点已用过如果邻接表中结点已用过m种颜色，种颜色， 则结点则结点 k+1没法着色，从该结点回没法着色，从该结点回溯溯 到其父结点到其父结点. 满足多米诺性质满足多米诺性质 时间复杂度时间复杂度：O(n mn) 5 运行实例运行实例 1 1 2 1 32 132 1 32 132 3 1 6 1 2 11 1 1 2 3 4 5 6 7 2 2 搜索树搜索树 1 2 3 2 1 3 1 2 3 1 2 1 3 2 第一个解向量：第一个解向量： 7 1 2 3 4 5 6 7 时间复杂度与时间复杂度与 改进途径改进途径 在在取定取定后后，不可扩张不可扩张成成, 因为因为 7和和1,2,3都都相邻相邻. 7. 7没法着色没法着色. . 可以可以从打叉从打叉 的结点回溯，而不必的结点回溯，而不必搜索其子搜索其子树树. . 时间复杂度：时间复杂度：O(nmn) 根据对称性，只需搜索根据对称性，只需搜索 1/3 的解空间的解空间. 当当 1和和2确定确定, 即即 以后，只有以后，只有 1 个解，个解， 在在 为根的子树中也只有为根的子树中也只有 1 个解个解. 由由 于于3个子树的对称性，总共个子树的对称性，总共6个解个解. 8 着色问题的应用着色问题的应用 会场分配会场分配问题：问题： 有有 n项活动需要安排项活动需要安排, 对于活动对于活动 i, j, 如果如果 i, j 时间冲突，就说时间冲突，就说 i 与与 j 不相不相 容容. 如何分配这些活动如何分配这些活动,使得每个会使得每个会 场的活动相容且占用会场数最少场的活动相容且占用会场数最少? 建模建模： 活动作为图的顶点，如果活动作为图的顶点，如果i, j不相容不相容, 则在则在 i 与与 j之间加一条边，会场标号之间加一条边，会场标号 作为颜色标号作为颜色标号. 求图的一种着色方案求图的一种着色方案, 使得使用的颜色数最少使得使用的颜色数最少. 10 小结小结 着色问题的描述着色问题的描述 着色问题的算法设计着色问题的算法设计 时间复杂度及改进途径时间复杂度及改进途径 着色问题的应用着色问题的应用 11