图的着色问题PPT参考幻灯片.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,问题来源,图的着色问题是由地图的着色问题引申而来的：用,m,种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。,问题处理：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。,例如，图,12-1,（,a,）所示的区域图可抽象为,12-1,（,b,）所表示的平面图。,19,世纪,50,年代，英国学者提出了任何地图都可以,4,中颜色来着色的,4,色猜想问题。过了,100,多年，这个问题才由美国学者在计算机上予以证明，这就是著名的四色定理。例如，在图,12-1,中，区域用城市名表示，颜色用数字表示，则图中表示了不同区域的不同着色问题。,1,问题来源,2,图的着色,通常所说的着色问题是指下述两类问题：,1,给定无环图,G,=(,V,E,),，用,m,种颜色为图中的每条边着色，要求每条边着一种颜色，并使相邻两条边有着不同的颜色，这个问题称为图的边着色问题。,2,给定无向图,G,=(,V,E,),，用,m,种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色，这个问题称为图的顶着色问题。,3,顶点着色基本概念,独立集,：对图,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,（但两者不同时成立）,。,4,顶点着色基本概念,K,可着色,：,G,的一个,k,顶点着色是指,k,种颜色,1,2,k,对于,G,各顶点的一个分配，如果任意两个相邻顶点都分配到不同的颜色，则称着色是正常的。换句话说，无环图,G,的一个正常,k,顶点着色是把,V,分成,k,个（可能有空的）独立集的一个分类,(,V,1,V,2,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,（这里,表示为顶点数最大值）,5,顶点着色,求顶色数的算法设计,我们由,“,每个同色顶点集合中的两两顶点不相邻,”,可以看出，同色顶点集实际上是一个独立集，当我们用第,1,种颜色上色时，为了尽可能扩大颜色,1,的顶点个数，逼近所用颜色数最少的目的，事实上就是找出图,G,的一个极大独立集并给它涂上颜色,1,。用第,2,种颜色上色时，同样选择另一个极大独立集涂色，,.,，当所有顶点涂色完毕，所用的颜色数即为所选的极大独立集的个数。,当然，上述颜色数未必就是,X,（G,），而且其和能够含所有顶点的极大独立集个数未必唯一。于是我们必须从一切若干极大独立集的和含所有顶点的子集中，挑选所用极大独立集个数最小者，其个数即为所用的颜色数,X,（,G,）。,由此可以得算法步骤：,Step1,：求,G,图的所有极大独立集；,Step2,：求出一切若干极大独立集的和含所有顶点的子集；,Step3,：从中挑选所用极大独立集个数最小值，即为,X,（,G,）。,6,求极小覆盖法布尔代数法,求极小覆盖的方法,-,布尔代数法,：,对于每个顶点,v,，选择,v,或者选择,v,的所有邻点。首先把“选择顶点,v”,这个指令记为符号,v,，然后对给定的指令,x,和,y,，指令“,x,或y”,和“,x,与,y”,分别记为,x+y,（逻辑和）和,x.y,（逻辑积）。,例如，指令“选择,a,与,b,，或者选择,b,与,c”,记为,ab+bc,。从形式上看，逻辑和与逻辑积类似与集合的和，而且关于和成立的代数法则对于这两个运算也成立。,布尔恒等式,aa=a,a+a=a,a+ab=a,如：,7,求极小覆盖法布尔代数法,例,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,。,8,求极小覆盖法布尔代数法,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,。,由此可见，求色数其需要求极大独立集以及一切若干极大独立集的和含所有顶点的子集，对于大图，因为图计算量过大而成为实际上难以凑效的算法，所以不是一个好算法，一般我们采用贪心法等近似算法来求解。,9,穷举法,Welch Powell,着色法,I,将图,G,中的结点按度数的递减顺序进行排列,(,这种排列可能不是唯一的，因为有些结点的度数相同,),。,II,用第一种颜色对第一结点着色，并按排列顺序对与前面着色结点不邻接的每一结点着上同样的颜色。,III,用第二种颜色对尚未着色的结点重复,II,，用第三种颜色继续这种做法，直到所有的结点全部着上色为止。,10,穷举法,Welch Powell,着色法,给定图,G,，用,Welch Powell,法对图,G,着色,A,4,A,2,A,3,A,6,A,5,3,2,1,1,3,11,穷举法,Welch Powell,着色法,第一步：将图,G,中的结点按度数的递减顺序排列：,第二步：用第一种颜色对,A,5,着第一种颜色，并对与,A,5,不邻接的结点,A,1,也着第一种颜色。,第三步：对结点,A,3,及与,A,3,不邻接的结点,A,4,、,A,8,着第二种颜色。,第四步：对结点,A,7,及与,A,7,不邻接的结点,A,2,、,A,6,着第三种颜色。,可见，图,G,是三色的。但图,G,不可能是二色的，因为,A,1,A,2,A,3,相互邻接，故必须着三种颜色。所以,x,(,G,)=3,。12,回溯法,由于用,m,种颜色为无向图,G,=(,V,E,),着色，其中，,V,的顶点个数为,n,，可以用一个,n,元组,C,=,(c,1,c,2,c,n,),来描述图的一种可能着色，其中，,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,，那么相应的着色是有效的局部着色。这时，就从当前节点出发，继续探索它的儿子节点，并把,13,回溯法,儿子结点标记为当前结点。在另一方面，如果在相应路径上搜索不到有效的着色，就把当前结点标记为,d_,结点，并把控制转移去搜索对应于另一种颜色的兄弟结点。如果对所有,m,个兄弟结点，都搜索不到一种有效的着色，就回溯到它的父亲结点，并把父亲结点标记为,d_,结点，转移去搜索父亲结点的兄弟结点。这种搜索过程一直进行，直到根结点变为,d_,结点，或者搜索路径长度等于,n,，并找到了一个有效的着色为止。,例：利用回溯法给下图（,a,）着色。,step one:,把,5,元组初始化为（,0,0,0,0,0,），从根结点开始向下搜索，以颜色,1,为顶点,A,着色，生成根结点,2,时，产生,(1,0,0,0,0),，是个有效着色。,14,回溯法,15,回溯法,step two:,以颜色,1,为顶点,B,着色生成结点,3,时，产生,(1,1,0,0,0),，是个无效着色，结点,3,为,d_,结点。,Step three,：以颜色,2,为顶点,B,着色生成结点,4,，产生,(12,0,0,0),，是个有效着色。,Step four,：分别以颜色,1,和,2,为顶点,C,着色生成结点,5,和,6,，产生,(1,2,1,0,0),和,(1,2,2,0,0),，都是无效着色，因此结点,5,和,6,都是,d_,结点。,Step five,：以颜色,3,为顶点,C,着色，产生,(1,2,3,0,0),，是个有效着色。重复上述步骤，最后得到有效着色,(1,2,3,3,1),。,16,回溯法,设数组,colorn,表示顶点的着色情况，回溯法求解,m,着色问题的算法如下：,图着色回溯法,：,1,将数组,colorn,初始化为,0,；,2,k=1;,3,while(k=1),3.1依次考察每一种颜色，若顶点,k,的着色与其他顶点的着色不发生冲突，则转步骤,3.2,；否则，搜索下一个颜色；,3.2,若顶点已全部着色，则输出数组,colorn,，返回；,3.3,否则，,3.3.1,若顶点,k,是一个合法着色，则,k=k+1,，转步骤,3,处理下一个顶点；,3.3.2,否则，重置顶点,k,的着色情况，,k=k-1,，转步骤,3,。,17,回溯法,void GraphColor(int n,int c ,int m),/,所有数组下标从,1,开始,for(i=1;i=1),colork=colork+1;,while(colork=m),if Ok(k)break;,else colork=colork+1;/,搜索下一个颜色,if(colork=m&k=n)/,求解完毕，输出解,for(i=1;i=n;i+),coutcolori;,return;,else if(colork=m&kn),k=k+1;/,处理下一个顶点,else colork=0;k=k-1;/,回溯,18,回溯法,bool Ok(int k)/,判断顶点,k,的着色是否发生冲突,for(i=1;ik;i+),if(cki=1&colori=colork),return false;,return true;,19,贪心法,例如，图,12-4(a),所示的图可以只用两种颜色着色，将顶点,1,、3,和,4,着成一种颜色，将顶点,2,和顶点,5,着成另外一种颜色。为简单起见，下面假定,k,个颜色的集合为,颜色,1,颜色,2,颜色,k,。,（,a,）,（,b,）,20,贪心法,贪心策略,：,选择一种颜色，以任意顶点作为开始顶点，依次考察图中的未被着色的每个顶点，如果一个顶点可以用颜色,1,着色，换言之，该顶点的邻接点都还未被着色，则用颜色,1,为该顶点着色，当没有顶点能以这种颜色着色时，选择颜色,2,和一个未被着色的顶点作为开始顶点，用第二种颜色为尽可能多的顶点着色，如果还有未着色的顶点，则选取颜色,3,并为尽可能多的顶点着色，依此类推，如图,12.4,（,b,）所示。,21,设数组,colorn,表示顶点的着色情况，贪心法求解图着色问题的算法如下：,图着色贪心法：,1,color1=1;/,顶点,1,着颜色,1,2,for(i=2;i=n;i+)/,其他所有顶点置未着色状态,colori=0;,3,k=0;,4,循环直到所有顶点均着色,4.1 k+;/,取下一个颜色,4.2 for(i=2;i=n;i+)/,用颜色,k,为尽量多的顶点着色,4.2.1,若顶点,i,已着色，则转步骤,4.2,，考虑下一个顶点,;,4.2.2,若图中与顶点,i,邻接的顶点着色与顶点,i,着颜色,k,不冲突，,则,colori=k;,5,输出,k;,22,蚁群算法,设有,k,只蚂蚁,ai,(,i1,2,k,),分别代表,k,只蚂蚁的初始城市，每一只蚂蚁代表,1,种颜色，,k,只蚂蚁分别遍历所有的城市，,ai,采用随机赋值的方法，城市用,c,=1,2,n,表示，着色蚂蚁的移动规则如图,12-5,所示,23,蚁群算法,ai,：表示第,i,只蚂蚁的起始城市；,p,max,：蚂蚁,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,城市的概率计算公式：,算法：,For t1,将,k,只蚂蚁随机置于,k,个顶点上,将,k,只蚂蚁出发点置于当前解集中,For m1 to n/k,For i1 to k,For c1 to n,按概率,pkic,选择顶点,c,移动蚂蚁,i,到顶点,c,将顶点,c,置于蚂蚁,i,的当前解集,检查着色条件,End for,End for,检查若未完成的任务,End for,tt+1,ic,0,End for,输出满意,h,24,图着色问题的应用安排考试问题,设学校共有,n,门功课需要进行期末考试，因为不少学生不止选修一门课，所以不能把一个同学选修的两门课安排在同一场次进行考试。问学期的期末考试最少需要多少场次才能完成？,25,问题处理：我们以每门功课为一个顶点，当且仅当两门功课被同一个学生选修时，在响应两个顶点之间连一条边，得到一个图,G,。我们将,n,门功课划分成,k,个子集,U,1,U,2,U,K,两两子集的功课都不相同。,每个子集,Ui,（,1,i,k,）的顶点两两子集不相邻，即子集内的任意两门功课都不能被一个学生选修。能这种要求划分的子集数,K,必须最少，即不能划分成,k-1,个子集。然后我们对每个子集内的顶点涂一种颜色。,同色顶点对应的课程安排在同一场次考试，颜色数即为学期考试所需要的最少场次数。,26,图着色问题的应用安排考试问题,例：计算机系某学期开设了,6,门选修课程：数据仓库与数据挖掘，机器学习导论，语音处理与压缩编码，数字媒体动画设计技术，智能信息处理，入侵检测技术，分别用,a,b,c,d,e,f,表示，我们以每门功课为一个顶点，当且仅当两门功课被同一个学生选修时，在相应两个顶点之间连一条边，学生选修情况如图,12-6,所示：,27,图着色问题的应用安排考试问题,分析：利用求极小覆盖的方法求得图的一切极大独立集如下：,显然我们可以选用,6,种颜色给每个顶点涂色，或者选用,5,种颜色分别给,5,个极大独立集涂色，也可以选用,4,种颜色，例如,I,1,中的,a,c,涂颜色，,I,2,中的,b,d,涂颜色,2,，,I,3,中的,f,涂颜色,3,，中的,e,涂颜色,4,。,但上述方案的颜色数不是,X,（,G,），正确的答案应该是,X,（,G,）,=3,有两种方案：,方案一：给,I,1,中的,a,和,c,涂颜色,1,，,I,3,中的,b,，,f,涂颜色,2,，,I,4,中的,d,，,e,涂颜色,3,，故安排,3,场考试。,第一场：数据仓库与数据挖掘，智能信息处理,第二场：机器学习，数字媒体动画设计技术,第三场：入侵检测技术，语言处理与压缩编码。,方案二：给,I,2,中的,b,，,d,涂颜色,1,，给,I,5,中的,c,，,e,涂颜色,2,，给,I,6,中的a,，,f,涂颜色,3,，故安排三场考试：,第一场：机器学习，入侵检测技术,第二场：智能信息处理，语音处理与压缩编码,第三场：数据仓库与数据挖掘，数字媒体动画设计,28,图着色问题的应用,交通管理系统,对于一个多叉路口，设计一个交通信号灯的管理系统：对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。,我们将通行方向作为结点，如果某些通行方向不能同时进行，则在相应的结点间连一条线于是问题就转化为将结点分组，使得相连结点不在同一组里。,例,3,：如图,12-7,所示，某交叉路口有,A,，,B,，,C,，,D,，,E,五条街道，请设计一个交通信号灯的管理系统。图,12-7,分析：首先考虑可以通行的方向,红：,AB,，,AC,，,AD,，,BA,，,DC,，,ED,绿：,DA,，,DB,黄：,EB,，,EC,，,EA,蓝：,BC,，,BD,29,图着色问题的应用,交通管理系统,接下来的通行方向为结点（如图,12-8,所示），考虑结点分组,30,图着色问题的应用,交通管理系统,贪心算法设计：,While,有结点未着色,选择一种新颜色；,在未着色的结点中，给尽可能的彼此结点之间没有边的点着色；,NEW,表示正确的，可以用新颜色着色的结点集合，从,V,1,中找出可用新颜色着色的结点集的程序框架描述为,New=,For,每个,vV1,do,If v,与,NEW,中所有结点间没有边,从,V,1,中去掉,v,；,NEW=NEW,v,；,对图和集合的操作：,判断一个集合是否为空：,isSetEmpty,（,V,1,）,置一个集合为空：,emptySet,（,NEW,）,从集合中去掉一个元素：,removeFromSet,（）,向集合里增加一个元素：,addToSet,（）,31,图着色问题的应用,交通管理系统,算法：,检查结点,v,与结点集合中结点之间在,G,中是否有边连接,Int colorUp(Graph G),int color=0;,V,1=G.V;,While(!isSetEmpty(,V,1)/,判断集合,V,1,是否为空emptySet(NEW);/,置集合,NEW,为空,While(/,检查结点,v,与结点,集合中结点之间在,G,中是否有边连接,addToSet(NEW,v);/,向集合,NEW,里加元素,v,removeFromSet(,V,1,v);/,从集合,V,1,中取掉元素,v,+color;,return(color);,32,图着色问题的应用,交通管理系统,图例中分组情况如下：,绿色：,AB,，,AC,，,AD,，,BA,，,DC,，,ED,蓝色：,BC,，,BD,，,EA,红色：,DA,，,DB,黄色：,EB,，,EC,33,一家公司制造,n,种化学制品,C,1,C,2,Cn,，其中某些制品是互不相容的，如果它们互相接触，则会引起爆炸，作为一种预防措施，公司希望把它的仓库分为间隔，以便把不相容的化学制品储藏在不同的间隔里，试问：这个仓库至少应该分成几个间隔？,问题处理：构造一个图,G,，其顶点集是,v,1,v,2,v,n,两个顶点,vi,和,vj,相连当且仅党化学制品,Ci,和,Cj,互不相容，则仓库的最小间隔数即为,G,的顶点数。,图着色问题的应用储藏问题,34,无环图,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,),，显然：,边着色,边顶对换法,35,例：求图,12-9G,的边色数,将图,12-9G,按边顶对换法转换为,G,(,图,12-10),，用最少颜色数给,G,所有顶点上色的一种方案 是 ，,转换成对图,G,边上色,边着色,边顶对换法,36,问题描述：,给出老师与班级的任课关系，以及教室数的限制，给出一个合理的排课方案。,算法设计：,第一步先求出最佳着色方案，然后再根据教室数的限制求出符合教室数要求的排课方案。,求最佳边着色方案时，先将边转换为点，再采用顶着色的方法来求最佳边着色方法。先设计函数,find,来求得所有的极大独立集，再通过函数,dyeing,根据已求得的极大独立集来求最佳着色方法。,边着色问题的应用排课时间表问题,37,第二步是根据已求得的最佳着色方案和教室数，将着色方案进行调整。,按照教室数和总的课程量来决定同色边集个数，然后再调整各同色边集中的边数。,调整方法为，若两个同色边集,Ei,Ej,所含边的数目之差大于,1,，则按照如下方法调整，假设,Ei,中边数多则此时有两种情况：一是在,Ei,中能找一条与,Ej,中各边都不相邻的边加入到,Ej,中；二是如果没有这样的单边时，则找这样的一条路径，它的起止边都在,Ei,中，然后将在路径中的,Ei,Ej,中的边互换。这样形成的新的同色边集,Ei,和,Ej,分别替换,Ei,和,Ej,。这样一边数差异便缩小了，按照上述方法循环进行直到不存在边数之差大于,1,的同色边集。,边着色问题的应用排课时间表问题,38,会场安排问题,问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。,这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。,算法设计：对于给定的,k,个待安排的活动，计算使用最少会场的时间表。,39,数据输入：给出输入数据。第一行有,1,个正整数,k,，表示有,k,个待安排的活动。接下来的,k,行中，每行有,2,个正整数，分别表示,k,个待安排的活动开始时间和结束时间。时间以,0,点开始的分钟计。,结果输出,:,将计算出的最少会场数输出。,Sample input,51 2312 2825 3527 8036 50,Sample output,3,40,