《离散数学》第七章_图论-第5节.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,河南工业大学离散数学课程组,A,(4),=A,(2),A,(5),=A,(3),解：,v1,v2,v3,v4,v5,例,7-3.3,求右图中图,G,中的可达性矩阵。,分析：先计算图的邻接矩阵,A,布尔乘法的的,2,、,3,、,4,、,5,次幂，然后做布尔加即可。,P=A,A,(2),A,(3),A,(4),A,(5),1,补充：二部图,二部图,：,G=,是图，图,G,的两个结点子集,V,1,，V,2,，,满足,V=V,1,V,2,V,1,V,2,=,，且图,G,的每一条边,e,均具有,e(v,i,v,j,),，其中,v,i,V,1,v,j,V,2,。,若,V,1,中任一结点与,V,2,中每一结点均有边相连接，则称二部图为完全二部图。若,|V,1,|=r,，,|V,2,|=t,，则记完全二部图,G,为,K,r,t,。,2,补充：二部图,K,3,3,3,在现实生活中，常常要画一些图形，希望边与边之间尽量减少相交的情况，例如印刷线路板的布线，交通道的设计等，近些年来，大规模集成电路的发展，进一步促进了图的平面性的研究。本节将简要地介绍平面图的概念，欧拉公式和平面图的着色。,7-5,平面图,本章所涉及到的图均指无向图。,4,平面图问题：在一块地上盖有三座房子，并且挖了三口井供房主人使用。,由于土质和气候等关系，这些井中的这一个或那一个常常干枯。因此各座房子的主人有时要到这个井去打水，有时要到那个井去打水，三个井都可能需要去。,不久，这三个房子的主人相互间变成了冤家，于是决定修建各家通往三个井的小道，使得他们在去三个井的途中不会相遇。,请问：你能否帮他们设计整个的小道路线，满足他们的要求？,对于许多问题，一个图怎样画出来无关紧要，只要与原来的图同构怎样画都可以。,但是有些时候的实际问题要求我们在平面上完成该图，使得不是节点的地方不能有边相交出现。例如单层印刷电路板，集成电路的布线，通讯和交通中的某些问题等，这就是可平面图问题。,制印刷电路板必须把电路除结点外导线不相交的印制在线路板上。,虽然交通立交桥、多层电路板已广泛出现在现实生活中，但可平面图问题仍然是其最基本的问题。,5,7-5,平面图,井,1,井,2,井,3,提出问题,6,平面图,知识点：,平面图,面,欧拉公式,Kuratowski,定理,本章中的图均指无向图,7,平面图的定义,定义7-5.1,设,G,V,，,E,是一个无向图，如果能够把,G,的,所有结点和边,画在平面上，且使,任何,两条边除了端点外没有其它的,交点,，就称,G,是一个,平面图,。,非连通图可以对连通分支分别讨论,。,注意,，有些图形从表面上看有几条边是相交的，但不能就此肯定它不是平面图。,8,平面图的例,K,1,(,平凡图)，,K,2,，K,3,，,K,4,都是平面图,K,3,K,4,K,2,9,判别平面图的直观方法,-,观察法,。,（,1,）找出长度尽可能大的且边不相交的圈,C,v,1,v,2,v,3,v,4,v,1,是,G,中的任何圈。,（,2,）找出交叉的边，设,P,1,v,1,v,3,和,P,2,v,2,v,4,是,G,中的任意,两条无公共结点,的边。,交叉,出现在边,P,1,和,P,2,上。,对,P,1,和,P,2,的放置有,4,种,方法，,（,1,）,P,1,和,P,2,或者都在圈,C,内部，或者都在圈,C,外部时，它们才会相交叉。,（,2,）,P,1,和,P,2,分别放置在,圈,的内部或外部，从而避免交叉。,只有,避免不了交叉时,，这种图才是,非平面图,。,v,1,v,2,v,3,v,4,v,1,v,2,v,3,v,4,v,1,v,2,v,3,v,4,v,1,v,2,v,3,v,4,v,1,v,2,v,3,v,4,10,例,K,5,e(K,5,删除任意一条边),是平面图,11,平面图的例,K,3,3,-e,是平面图吗？,12,非平面图的例,完全图,K,5,和,完全二部图,K,3,3,都不是平面图,K,5,K,5,K,5,不是平面图，因为无论如何改画都不能使其所有边不相交。,13,完全二部图,K,3,3,非平面图的例,v1,v2,v3,v4,v6,v5,v1,v2,v3,v4,v6,v5,K,3,3,K,3,3,K,3,3,不是平面图，因为无论如何画都不能使其所有边不相交。,v1,v2,v3,v4,v6,v5,14,完全二部图,K,3,3,非平面图的例,v1,v2,v3,v4,v6,v5,v1,v2,v3,v4,v6,v5,K,3,3,K,3,3,K,3,3,不是平面图，因为无论如何画都不能使其所有边不相交。,15,平面图的简单性质,若图,G,是平面图，则,G,的任何,子图,都是平面图。,若图,G,是非平面图，则,G,的任何,母图,也都是非平面图。,K,n,(n5),和,K,3,n,(n3),都是非平面图。,设,G,是平面图，则在,G,中加平行边或环后所得图还是平面图。,平行边与自回路不影响图的平面性，因此研究图的平面性时，不考虑平行边和环。,16,平面图面、边界、次数的定义,定义7-5.2,面：,设,G,是一个,连通平面图,，由图中的边所包围的区域，,在区域内既不包含图的结点，也不包含图的边，,这样的区域称为图,G,的一个,面,，记为,r,。,边界：,包围该面的,所有边,所构成的回路称为这个,面的边界,。,次数：边界（即回路）,的长度称为该面的,次数,，即回路中边的条数，面,r,的次数记为,deg(r,),。,环的次数,=1,。,内部面：,区域面积有限的面称为,有限面（或内部面）,。,外部面：,区域面积无限的面称为,无限面（或外部面）,。,显然，平面图,有且仅有一个无限面,。,17,例,求面的次数,有,5,个面,由如下回路包围,:,ADBA,deg,(,r,1,),=3,由如下回路包围,:,BCDB,deg,(,r,2,),=3,由如下回路包围,:,CDEFEC,deg,(,r,3,),=5,由如下回路包围,:,ABCEA,deg,(,r,4,),=4,由如下回路包围：,ADEA,deg,(,r,5,),=3,A,B,C,D,E,F,r,1,r,2,r,3,r,4,r,5,相加为,18,，正好是,边数,9,的,2,倍,r,1,r,2,r,4,r,5,r,3,A,B,C,D,E,F,r,1,r,2,r,3,r,4,r,5,18,平面图的握手定理,定理7-5.1 一个,有限平面图,，面的次数之和等于其边数的两倍。,即：,证明：任取,eE(G,)。,若,e,为面,r,i,和,r,j,(ij,),的,公共边界上,的边时，在计算,r,i,和,r,j,的次数时，,e,各提供1。,若,e,只在,某一个面的边界上出现,时，则在计算该面的次数时，,e,提供2。,于是每条边在计算总次数时，都提供2，因而,K,2,19,考察下图所示平面图的面、边界和次数。,a,b,d,e,c,h,i,j,k,r,0,r,1,r,2,r,3,解,平面图把平面分成,4,个面：,r,0,，边界为,abdeheca,，,D(r,0,)=7,r,1,，边界为,abca,，,D(r,1,)=3,r,2,，边界为,becb,，,D(r,2,)=9,r,3,，边界为,bdeb,，,D(r,3,)=3,r,1,、,r,2,和,r,3,是有限面，,r,0,是无限面。,注意：,对于平面图的不同平面表示，虽然面的数目相同，但各面的边界和次数会不同。,i,j,a,b,d,e,c,h,k,r,0,r,1,r,2,r,3,20,补充定理,定理,设,G,是,n(n3),阶,简单连通平面图,，则,G,的每个面的次数大于等于,3,。,证明：因为,G,的任意一个面上至少有,3,个结点，所以,G,的每个面的次数都大于等于,3,。,21,欧拉定理,定理7-5.2,欧拉定理,：,设,G,是,连通平面图,，则,v-e+r,=2,（欧拉公式）,其中,v,是,G,结点数，,e,是,G,边数，,r,是,G,的面数。,例,1,：在下图中验证欧拉公式,v=7,，,e=11,，,r=6,：,7-11+6=2,。,例,2,：连通平面图,20,个结点，每个结点度数为,3,，求这个平面图的面数。,解：,v=20,，,握手定理：,3v=2e,所以，,e=3/2v=30,欧拉公式,v-e+r,=2,得：,r=12,22,证明：,归纳法,若,G,为一个孤立结点，则,v,1,，,e,0,，,r,1,，故,v-e,+,r,2,成立。,若,G,为一条边，则,v,2,，,e,1,，,r,1,，则,v-e,+,r,2,成立。,设,G,为,k,条边时，欧拉公式成立。即,v,k,-,e,k,+,r,k,2,。下面考察,G,为,k,+1,条边时的情况。,因为在,k,条边的连通图上增加一条边，使它仍为连通图，只有下述两种情况：,加上一个新的结点,Q,2,，,Q,2,与图上的一点,Q,1,相连,(,如图,(a),所示,),，此时，,v,k,和,e,k,两者都增加,1,，而面数,r,k,未变，,故,(,v,k,+1)-(,e,k,+1)+,r,k,v,k,-,e,k,+,r,k,2,，即命题成立。,用一条边连接图上的已知点,Q,1,和,Q,2,，如图,(b),所示，此时,e,k,和,r,k,都增加,1,，而结点数未变，,故,v,k,-(,e,k,+1)+(,r,k,+1),v,k,-,e,k,+,r,k,2,，即命题成立。,Q,1,Q,2,欧拉定理证明,v-e+r,=2,Q,1,Q,2,23,运用欧拉,(Euler),公式的局限性,用欧拉公式直接判定一个连通图是否是平面图是很难的，因为你在没有把这个图边不相交地画在一个平面上时，你无法知道区域数是多少。,24,定理：判断平面图的必要条件,-,判断非平面图,定理7-5.3,：设,G,是一个有,v,个结点,e,条边的,连通简单平面图,，若,v3,，则,e,3v-6,。,补充定理：,每个圈至少由,4,条边组成的连通简单平面图，则有,e2v-4,。,逆否命题：,若,e,3v-6,，,则一定是非平面图。,每个圈至少由,4,条边组成的图，,e,2v-4,，则一定是非平面图。,25,定理：判断平面图的必要条件,定理7-5.3,：设,G,是一个有,v,个结点,e,条边的,连通简单平面图,，若,v3,，则,e,3v-6,。,分析：,可利用如下的性质：,(1),简单平面图中各个面的次数大于,3,；,(2),各面次数之和为2,e,；,(3),欧拉定理,v-e+r,=,2,证明：,设连通平面图,G,的面数为,r，,已知,v3,当,v=3，e=2,时，,2,3*3-6,，即,上式成立。,若,v3，,则,每一面的次数大于等于3,，由定理7-5.1知各面次数之和为2,e，,因此：,2,e3r,即,r2/3e,代入欧拉定理：,2=,v-e+r,v-e+2/3e,2v-e/3,e3v-6,26,定理,7-5.3,的应用,定理,7-5.3,是平面图的必要条件，,逆否命题：若,e,3v-6,，,则一定是非平面图。,例：,(1)证明,K,5,不是平面图.解:在,K,5,中有,v=5,个结点，,e=10,条边，因而对它有,3v-6=3*5-6=9,e=109=3v-6,根据定理7-5.3，,K,5,它不是平面图。,K,5,27,例,：,K,3,3,图，,v=6,e=9,有,e=9,3v-6=10，,但,k,3,3,不是平面图。,补充定理：,每个圈至少由,4,条边组成的,连通简单平面图,，则有,e2v-4,。,证明：,由题意知：,每一面的次数大于等于,4,，,2e4r,，,r1/2e,由欧拉公式：,v-e+r,=2,得到,v-e+r,=2v-e+1/2,e,从而,即,e2v-4,，故命题得证。,对于,K,3,3,图，任意三个结点必有两个不邻接，因此每个区域的次数不小于4,。,但,2v-4=2*6-4=8 3v-6,与,e,3v-6,矛盾。,所以，假设不成立，即,G,的最小度,(,G),5。,本定理在图着色理论中占重要地位。,说明,29,例,P317,（,4,）,G=(V,E),是一个,简单,无向图。若,|V|11,，则,G,或者,G,的补图,G,是非平面图。,证明,:,反证法。,设,G,和,G,的补图均是平面图，,G,的结点数为,v.,若,G,有,e,条边，其补有,k,条边，则有,e+k,=v(v-1)/2,。,因为,G,和其补均为平面图，有,e,3v-6,和,k,3v-6,因此,v(v-1)/2=,e+k,6v-12,即,v,2,-13v+24,0,(v-11)(v-2)+2,0,而当,v 11,时，,(v-11)(v-2)+2 0,，从而产生矛盾。因此,G,或,G,的补图 是非平面图。,30,K,3,3,的同构图,31,平面图的判断,判断一个图是否为平面图是一件困难的事。通常我们可以采用直观的方法，即：在图中找出一个长度尽可能大的且边不相交的圈；然后将图中那些相交于非结点的边，适当放置在已选定的圈内侧或外侧，若能避免除结点之外边的相交，则该图为平面图，否则便是非平面图。,例如，,K,5,不是平面图，因为无论如何画都不能使其所有边不相交。,另外，也可以采用下面的定理来判断。,同胚,库拉托夫斯基,(,Kuratowski,)定理,32,平面图的判断,-,库拉托夫斯基,(,Kuratowski,)定理,一、为判断定理做准备（,库拉,托夫斯基,技术,-,波兰数学家,）,1、插入2度结点和消去2度结点,插入2度结点,w,：,设,e,=(,u,v,),为图,G,的一条边，在,G,中删除,e,，,增加新的结点,w,，,使,u,、,v,均与,w,相邻，称为,插入2度结点,w,。,当两点间已有边时，在边上,增加一个结点使一条边变成两条边。,消去2度结点,w,：,设,w,为,G,中一个2度结点，,w,与,u,、,v,相邻，删除,w,，,增加新边(,u,v,)，,称为,消去2度结点,w,。,当两个结点都与第三个结点相邻接，而第三个结点的度数为2时，删去第3个结点，使两边合一边。,2,、当两点间已有边时，在两点间,增加重复边,或,删去重复边。,u,v,u,v,w,u,u,w,v,v,插入,2,度结点,消去,2,度结点,33,例,34,库拉托夫斯基（,Kuratowski,）定理,波兰数学家库拉托夫斯基（,Kuratowski,）在,1930,年给出了判定一个图是平面图的这个充要条件。这个定理证明太复杂，我们仅介绍不证明。,定理7-5.4：,图,G,是平面图,G,没有与,K,5,或,K,3,3,在,2,度结点内同构的子图。,在,2,度结点内同构：,若,G,1,和,G,2,同构，,或者,反复插入或消去2度结点后仍同构，则称,G,1,和,G,2,在,2,度结点内同构的子图。,。,Kuratowski,定理的实际应用较困难,35,例,判定是否是平面图,库拉托夫斯基定理应用,36,库拉托夫斯基定理应用,（,1,）,Petersen,图不是平面图,与,K,3,3,同构,子图,消去,2,度,结点,37,(,2),不是平面图,（自学）,K,3,3,库拉托夫斯基定理应用,子图,消去,2,度,结点,K,3,3,38,(3)解,（自学）,K,5,K,3,3,库拉托夫斯基定理应用,子图,消去,2,度,结点,子图,消去,2,度,结点,39,本节小结,重点掌握平面图的握手定理,重点掌握平面图中的欧拉公式及其应用,重点掌握平面图的必要条件及其应用,理解,库拉托夫斯基定理,应用,40,知识点,对偶图,对偶图性质,图着色,7-6 对偶图与着色,41,1 对偶图,定义7-6.1,给定一个,平面图,G，,通过以下步骤，得到一新的图：,(1),结点的构造：,对图,G,的每个面,F,i,的内部，作一结点且仅作一结点,v,i,*,。,(2),边的构造：,经过每两个面,F,i,和,F,j,的每公共边界,e,k,作一条边,e,k,*,(v,i,*,v,j,*,),与,e,k,相交。,当且仅当,e,k,只是一个面,F,i,的边界时。恰存在一环与,e,k,相交。,所得的图称为图,G,的对偶图，记,G,*。,对偶图定义（构造方法）：,42,例,7-6.1,：对偶图,对偶图,注意图中的一度结点和自环是怎样处理的。,43,2 对偶图的性质,对偶图是,连通平面图,环与桥互相对偶,平行边对偶于2个面之间的多条边界,44,对偶图的性质,v,*,=r,e,*,=e,v-e+r,=2,2,=v,*,-e,*,+r,*,=,r-e,+r,*,=,2-v,+r,*,r,*,=v,deg,G,*,(v,i,*,)=,deg,G,(R,i,),v=6,，,r=4,，,e=8,v,*,=4,，,r=6,，,e,*,=8,45,对偶图的性质,注意，当,G1,，,G2,为同构图的两种不同图示，那么它们的对偶图,G1,与,G2,不仅图示可能不同，而且可能是根本不同的图（不同构）。这就是说，,一个图的对偶图未必是唯一的。,例,G1,G2,不一定,G1*,G2*,46,自对偶(,self-dual),图,定义7-6.2,自对偶图：,G,G,*,.,47,补充定理,定理：若图,G,是自对偶图，则,e=2v-2,。,证明：,若图是自对偶图，,则,v=v*,，,e=e*,，即,r*=v=v*=r,，,e=e*,，,则由欧拉定理,v-e+r,=2,得,v-e+v,=2,，,即,e=2v-2,。,由此，,K,4,是自对偶图，,K,3,不是自对偶图。,K,4,：,4,个结点，,6,条边,K,3,：,3,个结点，,3,条边,48,