图论图染色问题课件.ppt

《图论图染色问题课件.ppt》由会员分享，可在线阅读，更多相关《图论图染色问题课件.ppt（34页珍藏版）》请在三一办公上搜索。

1、图的着色问题,问题来源:由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。,问题处理：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。例如，图12-1（a）所示的区域图可抽象为12-1（b）所表示的平面图。在图12-1中，区域用城市名表示，颜色用数字表示，则图中表示了不同区域的不同着色问题。,问题来源,图的着色,通常所说的着色问题是指下述两类问题：1给定无环图G=(V,E)，用m种颜色为图中的每条边着色，要求每条边着一种颜色，并使相邻两条边有着不同的颜色，这个问题称为图的边着色问题。2给定无

2、向图G=(V,E)，用m种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色，这个问题称为图的顶着色问题。,边的着色问题,定义：给图G的边着色，使得有共同顶点的边异色的最少颜色数，称为边色数。,边色数=3,一、边的着色问题,课程考试安排：用顶点v1,v2,vn表示n门课程，若其中两门课i,j被同时选，则vi,vj间连一条边。,一、边的着色问题3,定理：二分图G的边色数图中顶点的最大度。,一、边的着色问题3,定理(Vizing 1964)：若图G为简单图，图中顶点最大度为d，则G的边色数为d或d+1。,第一类图,第二类图,目前仍无区分(判别)任给定图属第几类图的有

3、效方法。,顶点的着色问题,定义：给图G的顶点着色，使得相邻的顶点异色的最少颜色数，称为图G顶点色数，简称色数；记作(G)。,(G)=2,四色定理,在1852年，一个英国青年名叫盖思里（Francis Guthrie）提出：任何连通的平面图，可以用不多于4种颜色对每一个区域着色，使相邻区域着不同颜色。18781880年两年间，数学家肯普和泰勒两人分别宣布证明了四色定理。后来，人们发现他们实际上证明了一个较弱的命题五色定理。就是说对平面图着色，用五种颜色就够了。1976年美国伊利诺州立大学的两位教授，阿佩尔（Kenneth Appel）和海肯（Wolfgang Haken）宣布，用计算机证明了这个

4、问题。他们的证明需要对1900多种情况进行详尽的分析，在一台高速计算机上耗时超过1200小时。对数学家来说总还是希望能找到数学方法的证明。,二、顶点的着色问题1,色数的性质：（1）图G只有孤立点时，(G)=1；（2）n个顶点的完全图G有(G)=n；,二、顶点的着色问题1,（3）若图G是n个顶点的回路，则(G)=2 n为偶数(G)=3 n为奇数；,二、顶点的着色问题1,（4）图G是顶点数超过1的树时，(G)=2；,二、顶点的着色问题1,（5）若图G是二分图，则(G)=2。,二、顶点的着色问题2,定理：若图G=(V,E)，d=maxd(vi),viV，则(G)d+1。,顶点着色的近似算法,（一）下

5、面给出顶点着色的算法(假定G的顶点为v1,v2,vn;用来染色的颜色为c1,c2,cn)：（1）对i=1,2,n,作Ci=c1,c2,ci；（2）标顶点vi(i=1,2,n)的颜色集Ci的第一种颜色ck；（3）对顶点vi的所有邻接点vj(ji)，作Cj=Cj-ck；（4）转到（2），直到所有顶点都着色为止。,注：上述算法并不能保证求出的着色方案用的颜色是最少的。,例28 给相邻顶点着上不同的颜色.要求颜色数目最小.,韦尔奇鲍威尔(WelchPowell)着色算法（穷举法）,步骤如下：（1）将图G中的顶点按度数递减次序排列；（2）用第一种颜色对第一顶点着色，并将与已着色顶点不邻接的顶点也着第一种

6、颜色；（3）按排列次序用第二种颜色对未着色的顶点重复（2）；用第三种颜色继续以上做法，直到所有的顶点均着上色为止。,韦尔奇鲍威尔法例,（1）各顶点按度数递减次序排列：c，a，e，f，b，h，g，d。（2）对c和与c不邻接的e，b着第一种颜色。,解,韦尔奇鲍威尔法例,（1）各顶点按度数递减次序排列：c，a，e，f，b，h，g，d。（2）对c和与c不邻接的e，b着第一种颜色。（3）对a和与a不邻接的g，d着第二种颜色。,解,韦尔奇鲍威尔法例,（1）各顶点按度数递减次序排列：c，a，e，f，b，h，g，d；（2）对c和与c不邻接的e，b着第一种颜色；（3）对a和与a不邻接的g，d着第二种颜色；（4）

7、对f和与f不邻接的h着第三种颜色。,解,一、边的着色问题4,边的着色问题可以转化为顶点的着色问题。,图着色问题的应用安排考试问题,设学校共有n门功课需要进行期末考试，因为不少学生不止选修一门课，所以不能把一个同学选修的两门课安排在同一场次进行考试。问学期的期末考试最少需要多少场次才能完成？,一、边的着色问题,课程考试安排：用顶点v1,v2,vn表示n门课程，若其中两门课i,j被同时选，则vi,vj间连一条边。,边色数即为最少场次数,二、顶点的着色问题,物资存储问题：设有n种物资要存放在仓库里，但有的物资不能放在同一房间里，否则引起损坏，甚至会发生危险。问存放这n种物资最少需要几个房间？,用顶点

8、v1,v2,vn表示n种物资，若其中两种不能放在同一房间里，则vi,vj间连一条边。,顶点色数即为最少房间数数,图着色问题的应用交通管理系统,对于一个多叉路口，设计一个交通信号灯的管理系统：对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。我们将通行方向作为结点，如果某些通行方向不能同时进行，则在相应的结点间连一条线于是问题就转化为将结点分组，使得相连结点不在同一组里。例3：如图12-7所示，某交叉路口有A，B，C，D，E,五条街道，请设计一个交通信号灯的管理系统。图12-7分析：首先考虑可以通行的方向红：AB，AC，AD，BA，DC，E

9、D绿：DA，DB黄：EB，EC，EA蓝：BC，BD,图着色问题的应用交通管理系统,接下来的通行方向为结点（如图12-8所示），考虑结点分组,图着色问题的应用交通管理系统,图例中分组情况如下：绿色：AB，AC，AD，BA，DC，ED 蓝色：BC，BD，EA 红色：DA，DB 黄色：EB，EC,会场安排问题,问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。算法设计：对于给定的k个待安排的活动，计算使用最少会场的时间表。,问题描述：给出老师与班级的任课关系，以及教室数的限制，给出一个合理的排课方案。匹配、边着色或顶点着色未解决好,着色问题的应用排课时间表问题,