《图论图染色问题课件》由会员分享，可在线阅读，更多相关《图论图染色问题课件（34页珍藏版）》请在金锄头文库上搜索。
1、图的着色问题图的着色问题问题来源问题来源:由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。问题处理：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。例如，图12-1（a）所示的区域图可抽象为12-1（b）所表示的平面图。在图12-1中，区域用城市名表示，颜色用数字表示，则图中表示了不同区域的不同着色问题 。问题来源图的着色n n通常所说的着色问题是指下述两类问题：n n1给定无环图G=(V,E)，用m种颜色为图中的每条边着色，要求每条边着一种颜色，并使相邻两条边有着不同的颜色，这个问题称为
2、图的边着色问题。n n2给定无向图G=(V,E)，用m种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色，这个问题称为图的顶着色问题。边的着色问题边的着色问题定义：给图G的边着色，使得有共同顶点的边异色的最少颜色数，称为边色数边色数。边色数=3一、边的着色问题一、边的着色问题n n课程考试安排： 用顶点v1,v2,vn表示n门课程，若其中两门课i,j被同时选，则vi,vj间连一条边。一、边的着色问题一、边的着色问题3n n定理：二分图G的边色数图中顶点的最大度。x1x2y1x3x4x5y2y3y4y5一、边的着色问题一、边的着色问题3n n定理(Vizing
3、1964)：若图G为简单图，图中顶点最大度为d，则G的边色数为d或d+1。x1x2y1x3x4x5y2y3y4y5单星妖怪第一类图第一类图第二类图第二类图目前仍无区分目前仍无区分(判别判别)任给定图属任给定图属第几类图的有效方法。第几类图的有效方法。顶点的着色问题顶点的着色问题n n定义：给图G的顶点着色，使得相邻的顶点异色的最少颜色数，称为图图G顶点色数顶点色数，简称色数色数；记作(G)。(G)=2四色定理四色定理 在在18521852年，一个英国青年名叫盖思里（年，一个英国青年名叫盖思里（Francis Francis GuthrieGuthrie）提出：）提出：任何连通的平面图，可以用不
4、多于任何连通的平面图，可以用不多于4 4种颜色对每一个区域着色，使相邻区域着不同颜色种颜色对每一个区域着色，使相邻区域着不同颜色。1878187818801880年两年间，数学家肯普和泰勒两人分别宣年两年间，数学家肯普和泰勒两人分别宣布证明了四色定理。后来，人们发现他们实际上证明布证明了四色定理。后来，人们发现他们实际上证明了一个较弱的命题了一个较弱的命题五色定理五色定理。就是说对平面图着。就是说对平面图着色，用五种颜色就够了。色，用五种颜色就够了。 19761976年美国伊利诺州立大学的两位教授，阿佩年美国伊利诺州立大学的两位教授，阿佩尔（尔（Kenneth Kenneth AppelApp
5、el）和海肯（）和海肯（Wolfgang Wolfgang HakenHaken）宣布，）宣布，用计算机证明了这个问题。他们的证明需要对用计算机证明了这个问题。他们的证明需要对19001900多多种情况进行详尽的分析，在一台高速计算机上耗时超种情况进行详尽的分析，在一台高速计算机上耗时超过过12001200小时。对数学家来说总还是希望能找到数学方小时。对数学家来说总还是希望能找到数学方法的证明。法的证明。 二、顶点的着色问题二、顶点的着色问题1n n色数的性质：（1）图G只有孤立点时，(G)=1；（2）n个顶点的完全图G有(G)=n；二、顶点的着色问题二、顶点的着色问题1（3）若图G是n个顶点
6、的回路，则 (G)=2 n为偶数(G)= 3 n为奇数；二、顶点的着色问题二、顶点的着色问题1（4）图G是顶点数超过1的树时，(G)=2；二、顶点的着色问题二、顶点的着色问题1（5）若图G是二分图，则(G)=2。x1x2y1x3x4x5y2y3y4y5二、顶点的着色问题二、顶点的着色问题2n n定理：若图G=(V,E)，d=maxd(vi),viV，则(G)d+1。顶点着色的近似算法顶点着色的近似算法（一）下面给出顶点着色的算法(假定G的顶点为v1,v2,vn;用来染色的颜色为c1,c2,cn)：（1）对i=1,2,n,作Ci=c1,c2,ci；（2）标顶点vi (i=1,2,n)的颜色集Ci
7、的第一种颜色ck；（3）对顶点vi的所有邻接点vj(ji)，作Cj= Cj-ck；（4）转到（2），直到所有顶点都着色为止。注注：上述算法并不能保证求出的着色方案用的颜色是最少的。例例28 给相邻顶点着上不同给相邻顶点着上不同的颜色的颜色.要求颜色数目最小要求颜色数目最小.韦尔奇鲍威尔(WelchPowell)着色算法（穷举法）n n步骤如下：（1）将图G中的顶点按度数递减次序排列；（2）用第一种颜色对第一顶点着色，并将与已着色顶点不邻接的顶点也着第一种颜色；（3）按排列次序用第二种颜色对未着色的顶点重复（2）；用第三种颜色继续以上做法，直到所有的顶点均着上色为止。韦尔奇鲍威尔法例（1）各顶点
8、按度数递减次序排列： c，a，e，f，b，h，g，d。（2）对c和与c不邻接的e，b着第一种颜色。解解abhcdefg韦尔奇鲍威尔法例（1）各顶点按度数递减次序排列： c，a，e，f，b，h，g，d。（2）对c和与c不邻接的e，b着第一种颜色。（3）对a和与a不邻接的g，d着第二种颜色。解解abhcdefg韦尔奇鲍威尔法例（1）各顶点按度数递减次序排列： c，a，e，f，b，h，g，d；（2）对c和与c不邻接的e，b着第一种颜色；（3）对a和与a不邻接的g，d着第二种颜色；（4）对f和与f不邻接的h着第三种颜色。解解abhcdefg一、边的着色问题一、边的着色问题4n n边的着色问题可以转化为
9、顶点的着色问题。图着色问题的应用安排考试问题n n设学校共有设学校共有n n门功课需要进行期末考试，因为不少学生门功课需要进行期末考试，因为不少学生不止选修一门课，所以不能把一个同学选修的两门课不止选修一门课，所以不能把一个同学选修的两门课安排在同一场次进行考试。问学期的期末考试最少需安排在同一场次进行考试。问学期的期末考试最少需要多少场次才能完成？要多少场次才能完成？一、边的着色问题一、边的着色问题n n课程考试安排： 用顶点v1,v2,vn表示n门课程，若其中两门课i,j被同时选，则vi,vj间连一条边。边色数即为最少场次数二、顶点的着色问题二、顶点的着色问题n n物资存储问题： 设有n种
10、物资要存放在仓库里，但有的物资不能放在同一房间里，否则引起损坏，甚至会发生危险。问存放这n种物资最少需要几个房间？n n用顶点v1,v2,vn表示n种物资，若其中两种不能放在同一房间里，则vi,vj间连一条边。abhcdefg顶点色数即为最少房间数数图着色问题的应用交通管理系统 n n对于一个多叉路口，设计一个交通信号灯的管理系统：对车辆的可能行驶对于一个多叉路口，设计一个交通信号灯的管理系统：对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。以同时安全行驶而不发生碰撞。n n
11、我们将通行方向作为结点，如果某些通行方向不能同时进行，则在相应的我们将通行方向作为结点，如果某些通行方向不能同时进行，则在相应的结点间连一条线于是问题就转化为将结点分组，使得相连结点不在同一结点间连一条线于是问题就转化为将结点分组，使得相连结点不在同一组里。组里。n n例例3 3：如图：如图12-712-7所示，某交叉路口有所示，某交叉路口有A A，B B，C C，DD，E,E,五条街道，请设计一五条街道，请设计一个交通信号灯的管理系统。个交通信号灯的管理系统。图图12-712-7n n分析：首先考虑可以通行的方向分析：首先考虑可以通行的方向n n红：红：ABAB，ACAC，ADAD，BABA
12、，DCDC，EDEDn n绿：绿：DADA，DBDBn n黄：黄：EBEB，ECEC，EAEAn n蓝：蓝：BCBC，BDBD图着色问题的应用交通管理系统 接下来的通行方向为结点（如图接下来的通行方向为结点（如图12-812-8所示），考虑结点分组所示），考虑结点分组图着色问题的应用交通管理系统 n n图例中分组情况如下：图例中分组情况如下：n n 绿色：绿色：ABAB，ACAC，ADAD，BABA，DCDC，EDEDn n 蓝色：蓝色：BCBC，BDBD，EAEAn n 红色：红色：DADA，DBDBn n 黄色：黄色：EBEB，ECEC会场安排问题会场安排问题n n问题描述：问题描述：假设
13、要在足够多的会场里安排一批活动，并希望假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。使用尽可能少的会场。n n这个问题实际上是著名的图着色问题。若将每一这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。应于要找的最小会场数。n n算法设计：算法设计：对于给定的对于给定的k k个待安排的活动，计算使用最少会场个待安排的活动，计算使用最少会场的时间表。的时间表。n n问题描述： 给出老师与班级的任课关系，以及教室数的限制，给出一个合理的排课方案。匹配、边着色或顶点着色未解决好着色问题的应用排课时间表问题
