图的着色问题.ppt

问题来源 图的着色问题是由地图的着色问题引申而来的 用m种颜色为地图着色 使得地图上的每一个区域着一种颜色 且相邻区域颜色不同 问题处理 如果把每一个区域收缩为一个顶点 把相邻两个区域用一条边相连接 就可以把一个区域图抽象为一个平面图 例如 图12 1 a 所示的区域图可抽象为12 1 b 所表示的平面图 19世纪50年代 英国学者提出了任何地图都可以4中颜色来着色的4色猜想问题 过了100多年 这个问题才由美国学者在计算机上予以证明 这就是著名的四色定理 例如 在图12 1中 区域用城市名表示 颜色用数字表示 则图中表示了不同区域的不同着色问题 问题来源 图的着色 通常所说的着色问题是指下述两类问题 1 给定无环图G V E 用m种颜色为图中的每条边着色 要求每条边着一种颜色 并使相邻两条边有着不同的颜色 这个问题称为图的边着色问题 2 给定无向图G V E 用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 但两者不同时成立 顶点着色 基本概念 K可着色 G的一个k顶点着色是指k种颜色1 2 k对于G各顶点的一个分配 如果任意两个相邻顶点都分配到不同的颜色 则称着色是正常的 换句话说 无环图G的一个正常k顶点着色是把V分成k个 可能有空的 独立集的一个分类 V1 V2 Vk 当G有一个正常k顶点着色时 就成G是k顶点可着色的 G的色数X G 是指G为k可着色的k的最小值 若X G k 则称G是k色的 事实上 如果我们将同色的顶点列入一个顶点子集 那么求X G 就转为求满足下列条件的最少子集数k 1 两两子集中的顶点不同 2 子集中的两两顶点不相邻 显然有 i 若G为平凡图 则X G 1 ii 若G为偶图 则X G 2 iii 对任意图G 有X G 1 这里 表示为顶点数最大值 顶点着色 求顶色数的算法设计 我们由 每个同色顶点集合中的两两顶点不相邻 可以看出 同色顶点集实际上是一个独立集 当我们用第1种颜色上色时 为了尽可能扩大颜色1的顶点个数 逼近所用颜色数最少的目的 事实上就是找出图G的一个极大独立集并给它涂上颜色1 用第2种颜色上色时 同样选择另一个极大独立集涂色 当所有顶点涂色完毕 所用的颜色数即为所选的极大独立集的个数 当然 上述颜色数未必就是X G 而且其和能够含所有顶点的极大独立集个数未必唯一 于是我们必须从一切若干极大独立集的和含所有顶点的子集中 挑选所用极大独立集个数最小者 其个数即为所用的颜色数X G 由此可以得算法步骤 Step1 求G图的所有极大独立集 Step2 求出一切若干极大独立集的和含所有顶点的子集 Step3 从中挑选所用极大独立集个数最小值 即为X G 求极小覆盖法 布尔代数法 求极小覆盖的方法 布尔代数法 对于每个顶点v 选择v或者选择v的所有邻点 首先把 选择顶点v 这个指令记为符号v 然后对给定的指令x和y 指令 x或y 和 x与y 分别记为x y 逻辑和 和x y 逻辑积 例如 指令 选择a与b 或者选择b与c 记为ab bc 从形式上看 逻辑和与逻辑积类似与集合的 和 而且关于 和 成立的代数法则对于这两个运算也成立 布尔恒等式aa aa a aa ab a如 求极小覆盖法 布尔代数法 例1 求图12 2G的顶色数解 Step1 求极大独立集先求图G的极小覆盖 化简得故G的极小覆盖为取其补集 得到G的所有极大独立集 Step2 求出一切若干极大独立集和所有顶点的子集显然我们可以选用4种颜色给每个顶点涂色 或者选用3种颜色分别给3个极大独立集涂色 例如为 b d f 中的b d f涂颜色1 为 a f 中的a涂颜色2 为 a c g 中的c和g涂颜色3 为 a e g 中的e涂颜色4 求极小覆盖法 布尔代数法 Step3 从中挑选所用极大独立集个数最小者 即为X G 但上述子集的颜色数都不是X G 正确的应该是X G 3 该子集为 给 b d f 中的b d f涂颜色1 为 a e g 中a e g涂颜色2为 a c g 中的c涂颜色3 由此可见 求色数其需要求极大独立集以及一切若干极大独立集的和含所有顶点的子集 对于大图 因为图计算量过大而成为实际上难以凑效的算法 所以不是一个好算法 一般我们采用贪心法等近似算法来求解 穷举法 WelchPowell着色法 I 将图G中的结点按度数的递减顺序进行排列 这种排列可能不是唯一的 因为有些结点的度数相同 II 用第一种颜色对第一结点着色 并按排列顺序对与前面着色结点不邻接的每一结点着上同样的颜色 III 用第二种颜色对尚未着色的结点重复II 用第三种颜色继续这种做法 直到所有的结点全部着上色为止 穷举法 WelchPowell着色法 给定图G 用WelchPowell法对图G着色 A4 A2 A3 A6 A5 3 2 1 1 3 穷举法 WelchPowell着色法 第一步 将图G中的结点按度数的递减顺序排列 第二步 用第一种颜色对A5着第一种颜色 并对与A5不邻接的结点A1也着第一种颜色 第三步 对结点A3及与A3不邻接的结点A4 A8着第二种颜色 第四步 对结点A7及与A7不邻接的结点A2 A6着第三种颜色 可见 图G是三色的 但图G不可能是二色的 因为A1 A2 A3相互邻接 故必须着三种颜色 所以x G 3 回溯法 由于用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个顶点的无向图12 3 a 的一种着色 顶点1着颜色1 顶点2着颜色2 顶点3着颜色2 如此等等 如果在n元组C中 所有相邻顶点都不会着相同颜色 就称此n元组为可行解 否则为无效解 回溯法求解图着色问题 首先把所有顶点的颜色初始化为0 然后依次为每个顶点着色 如果其中i个顶点已经着色 并且相邻两个顶点的颜色都不一样 就称当前的着色是有效的局部着色 否则 就称为无效的着色 如果由根节点到当前节点路径上的着色 对应于一个有效着色 并且路径的长度小于n 那么相应的着色是有效的局部着色 这时 就从当前节点出发 继续探索它的儿子节点 并把 回溯法 儿子结点标记为当前结点 在另一方面 如果在相应路径上搜索不到有效的着色 就把当前结点标记为d 结点 并把控制转移去搜索对应于另一种颜色的兄弟结点 如果对所有m个兄弟结点 都搜索不到一种有效的着色 就回溯到它的父亲结点 并把父亲结点标记为d 结点 转移去搜索父亲结点的兄弟结点 这种搜索过程一直进行 直到根结点变为d 结点 或者搜索路径长度等于n 并找到了一个有效的着色为止 例 利用回溯法给下图 a 着色 stepone 把5元组初始化为 0 0 0 0 0 从根结点开始向下搜索 以颜色1为顶点A着色 生成根结点2时 产生 1 0 0 0 0 是个有效着色 回溯法 回溯法 steptwo 以颜色1为顶点B着色生成结点3时 产生 1 1 0 0 0 是个无效着色 结点3为d 结点 Stepthree 以颜色2为顶点B着色生成结点4 产生 1 2 0 0 0 是个有效着色 Stepfour 分别以颜色1和2为顶点C着色生成结点5和6 产生 1 2 1 0 0 和 1 2 2 0 0 都是无效着色 因此结点5和6都是d 结点 Stepfive 以颜色3为顶点C着色 产生 1 2 3 0 0 是个有效着色 重复上述步骤 最后得到有效着色 1 2 3 3 1 回溯法 设数组color n 表示顶点的着色情况 回溯法求解m着色问题的算法如下 图着色回溯法 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 回溯法 voidGraphColor intn intc intm 所有数组下标从1开始 for i 1 i 1 color k color k 1 while color k m ifOk k break elsecolor k color k 1 搜索下一个颜色if color k m 回溯 回溯法 boolOk intk 判断顶点k的着色是否发生冲突 for i 1 i k i if c k i 1 贪心法 例如 图12 4 a 所示的图可以只用两种颜色着色 将顶点1 3和4着成一种颜色 将顶点2和顶点5着成另外一种颜色 为简单起见 下面假定k个颜色的集合为 颜色1 颜色2 颜色k a b 贪心法 贪心策略 选择一种颜色 以任意顶点作为开始顶点 依次考察图中的未被着色的每个顶点 如果一个顶点可以用颜色1着色 换言之 该顶点的邻接点都还未被着色 则用颜色1为该顶点着色 当没有顶点能以这种颜色着色时 选择颜色2和一个未被着色的顶点作为开始顶点 用第二种颜色为尽可能多的顶点着色 如果还有未着色的顶点 则选取颜色3并为尽可能多的顶点着色 依此类推 如图12 4 b 所示 设数组color n 表示顶点的着色情况 贪心法求解图着色问题的算法如下 图着色贪心法 1 color 1 1 顶点1着颜色12 for i 2 i n i 其他所有顶点置未着色状态color i 0 3 k 0 4 循环直到所有顶点均着色4 1k 取下一个颜色4 2for i 2 i n i 用颜色k为尽量多的顶点着色4 2 1若顶点i已着色 则转步骤4 2 考虑下一个顶点 4 2 2若图中与顶点i邻接的顶点着色与顶点i着颜色k不冲突 则color i k 5 输出k 蚁群算法 设有k只蚂蚁ai i 1 2 k 分别代表k只蚂蚁的初始城市 每一只蚂蚁代表1种颜色 k只蚂蚁分别遍历所有的城市 ai采用随机赋值的方法 城市用c 1 2 n表示 着色蚂蚁的移动规则如图12 5所示 蚁群算法 ai 表示第i只蚂蚁的起始城市 pmax 蚂蚁i下一步所选城市中最大的概率 建立邻接矩阵Y为n n的矩阵 表示地区与地区之间的邻接关系 Yic表示城市i与城市c的邻接关系 当城市i与城市c是同一个城市用Yic 0表示 当城市i与城市c不相邻 Yic取一较小值 如Yic 1 当城市i与城市c相邻Yic取一较大值 如Yic 1 ai与c城市的表更新方程 ai到c城市的概率计算公式 算法 Fort 1将k只蚂蚁随机置于k个顶点上将k只蚂蚁出发点置于当前解集中Form 1ton kFori 1tokForc 1ton按概率pkic选择顶点c移动蚂蚁i到顶点c将顶点c置于蚂蚁i的当前解集检查着色条件EndforEndfor检查若未完成的任务Endfort t 1 ic 0Endfor输出满意h 图着色问题的应用 安排考试问题 设学校共有n门功课需要进行期末考试 因为不少学生不止选修一门课 所以不能把一个同学选修的两门课安排在同一场次进行考试 问学期的期末考试最少需要多少场次才能完成 问题处理 我们以每门功课为一个顶点 当且仅当两门功课被同一个学生选修时 在响应两个顶点之间连一条边 得到一个图G 我们将n门功课划分成k个子集U1 U2 UK两两子集的功课都不相同 每个子集Ui 1 i k 的顶点两两子集不相邻 即子集内的任意两门功课都不能被一个学生选修 能这种要求划分的子集数K必须最少 即不能划分成k 1个子集 然后我们对每个子集内的顶点涂一种颜色 同色顶点对应的课程安排在同一场次考试 颜色数即为学期考试所需要的最少场次数 图着色问题的应用 安排考试问题 例 计算机系某学期开设了6门选修课程 数据仓库与数据挖掘 机器学习导论 语音处理与压缩编码 数字媒体动画设计技术 智能信息处理 入侵检测技术 分别用a b c d e f表示 我们以每门功课为一个顶点 当且仅当两门功课被同一个学生选修时 在相应两个顶点之间连一条边 学生选修情况如图12 6所示 图着色问题的应用 安排考试问题 分析 利用求极小覆盖的方法求得图的一切极大独立集如下 显然我们可以选用6种颜色给每个顶点涂色 或者选用5种颜色分别给5个极大独立集涂色 也可以选用4种颜色 例如I1中的a c涂颜色 I2中的b d涂颜色2 I3中的f涂颜色3 中的e涂颜色4 但上述方案的颜色数不是X G 正确的答案应该是X G 3有两种方案 方案一 给I1中的a和c涂颜色1 I3中的b f涂颜色2 I4中的d e涂颜色3 故安排3场考试 第一场 数据仓库与数据挖掘 智能信息处理第二场 机器学习 数字媒体动画设计技术第三场 入侵检测技术 语言处理与压缩编码 方案二 给I2中的b d涂颜色1 给I5中的c e涂颜色2 给I6中的a f涂颜色3 故安排三场考试 第一场 机器学习 入侵检测技术第二场 智能信息处理 语音处理与压缩编码第三场 数据仓库与数据挖掘 数字媒体动画设计 图着色问题的应用 交通管理系统 对于一个多叉路口 设计一个交通信号灯的管理系统 对车辆的可能行驶方向作某种分组 对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞 我们将通行方向作为结点 如果某些通行方向不能同时进行 则在相应的结点间连一条线于是问题就转化为将结点分组 使得相连结点不在同一组里 例3 如图12 7所示 某交叉路口有A B C D E 五条街道 请设计一个交通信号灯的管理系统 图12 7分析 首先考虑可以通行的方向红 AB AC AD BA DC ED绿 DA DB黄 EB EC EA蓝 BC BD 图着色问题的应用 交通管理系统 接下来的通行方向为结点 如图12 8所示 考虑结点分组 图着色问题的应用 交通管理系统 贪心算法设计 While有结点未着色 选择一种新颜色 在未着色的结点中 给尽可能的彼此结点之间没有边的点着色 NEW表示正确的 可以用新颜色着色的结点集合 从V1中找出可用新颜色着色的结点集的程序框架描述为New For每个v V1doIfv与NEW中所有结点间没有边 从V1中去掉v NEW NEW v 对图和集合的操作 判断一个集合是否为空 isSetEmpty V1 置一个集合为空 emptySet NEW 从集合中去掉一个元素 removeFromSet 向集合里增加一个元素 addToSet 图着色问题的应用 交通管理系统 算法 检查结点v与结点集合中结点之间在G中是否有边连接IntcolorUp GraphG intcolor 0 V1 G V While isSetEmpty V1 判断集合V1是否为空 emptySet NEW 置集合NEW为空While 检查结点v与结点集合中结点之间在G中是否有边连接 addToSet NEW v 向集合NEW里加元素vremoveFromSet V1 v 从集合V1中取掉元素v color return color 图着色问题的应用 交通管理系统 图例中分组情况如下 绿色 AB AC AD BA DC ED蓝色 BC BD EA红色 DA DB黄色 EB EC 一家公司制造n种化学制品C1 C2 Cn 其中某些制品是互不相容的 如果它们互相接触 则会引起爆炸 作为一种预防措施 公司希望把它的仓库分为间隔 以便把不相容的化学制品储藏在不同的间隔里 试问 这个仓库至少应该分成几个间隔 问题处理 构造一个图G 其顶点集是 v1 v2 vn 两个顶点vi和vj相连当且仅党化学制品Ci和Cj互不相容 则仓库的最小间隔数即为G的顶点数 图着色问题的应用 储藏问题 无环图G的一个k边着色是指k种颜色对于G的各边一个分配 若没有两条边有着色相同的颜色 则称着色是正常的 若G有正常的k边着色 则称k边可着色的 若至少要用k种颜色 即可以正常k边着色而不能k 1边着色 时 则称k为G的边色数 记成 顶点v关联的边中有i色边时 称颜色i色在顶点v出现 在顶点i出现的颜色数目记成C v 通过边顶对换法将图G转换为图G G图中的边e转换为图G 中的一个顶点v 若图G中两条边相邻 则G 中对应两个顶点之间连一条边 然后对图G 进行顶点着色或求顶色数x G 显然 边着色 边顶对换法 例 求图12 9G的边色数将图12 9G按边顶对换法转换为G 图12 10 用最少颜色数给G 所有顶点上色的一种方案是 转换成对图G边上色 边着色 边顶对换法 问题描述