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

《《离散数学》第七章图论-第5节.ppt》由会员分享，可在线阅读，更多相关《《离散数学》第七章图论-第5节.ppt（48页珍藏版）》请在三一办公上搜索。

1、,A(4)=A(2)A(5)=A(3),解：,例7-3.3 求右图中图G中的可达性矩阵。,分析：先计算图的邻接矩阵A布尔乘法的的2、3、4、5次幂，然后做布尔加即可。,P=A A(2)A(3)A(4)A(5),补充：二部图,二部图：G=是图，图G的两个结点子集V1，V2，满足V=V1V2,V1 V2=，且图G的每一条边e均具有e(vi,vj)，其中vi V1,vj V2。,若V1中任一结点与V2中每一结点均有边相连接，则称二部图为完全二部图。若|V1|=r，|V2|=t，则记完全二部图G为Kr,t。,补充：二部图,K3,3,在现实生活中，常常要画一些图形，希望边与边之间尽量减少相交的情况，例如

2、印刷线路板的布线，交通道的设计等，近些年来，大规模集成电路的发展，进一步促进了图的平面性的研究。本节将简要地介绍平面图的概念，欧拉公式和平面图的着色。,7-5 平面图,本章所涉及到的图均指无向图。,平面图问题：在一块地上盖有三座房子，并且挖了三口井供房主人使用。由于土质和气候等关系，这些井中的这一个或那一个常常干枯。因此各座房子的主人有时要到这个井去打水，有时要到那个井去打水，三个井都可能需要去。不久，这三个房子的主人相互间变成了冤家，于是决定修建各家通往三个井的小道，使得他们在去三个井的途中不会相遇。请问：你能否帮他们设计整个的小道路线，满足他们的要求？对于许多问题，一个图怎样画出来无关紧要

3、，只要与原来的图同构怎样画都可以。但是有些时候的实际问题要求我们在平面上完成该图，使得不是节点的地方不能有边相交出现。例如单层印刷电路板，集成电路的布线，通讯和交通中的某些问题等，这就是可平面图问题。制印刷电路板必须把电路除结点外导线不相交的印制在线路板上。虽然交通立交桥、多层电路板已广泛出现在现实生活中，但可平面图问题仍然是其最基本的问题。,7-5 平面图,井1,井2,井3,提出问题,平面图,知识点：平面图,面,欧拉公式Kuratowski定理本章中的图均指无向图,平面图的定义,定义7-5.1 设GV，E是一个无向图，如果能够把G的所有结点和边画在平面上，且使任何两条边除了端点外没有其它的交

4、点，就称G是一个平面图。非连通图可以对连通分支分别讨论。注意，有些图形从表面上看有几条边是相交的，但不能就此肯定它不是平面图。,平面图的例,K1(平凡图)，K2，K3，K4都是平面图,K3,K4,K2,判别平面图的直观方法-观察法。,（1）找出长度尽可能大的且边不相交的圈 Cv1v2v3v4v1是G中的任何圈。（2）找出交叉的边，设P1v1v3和P2v2v4是G中的任意两条无公共结点的边。交叉出现在边P1和P2上。对P1和P2的放置有4种方法，（1）P1和P2或者都在圈C内部，或者都在圈C外部时，它们才会相交叉。（2）P1和P2分别放置在圈的内部或外部，从而避免交叉。只有避免不了交叉时，这种图

5、才是非平面图。,例K5e(K5删除任意一条边)是平面图,平面图的例,K3,3-e是平面图吗？,非平面图的例,完全图K5和完全二部图K3,3都不是平面图,K5,K5,K5不是平面图，因为无论如何改画都不能使其所有边不相交。,完全二部图K3,3,非平面图的例,v1,v2,v3,v4,v6,v5,K3,3,K3,3,K3,3不是平面图，因为无论如何画都不能使其所有边不相交。,v1,v2,v3,v4,v6,v5,完全二部图K3,3,非平面图的例,v1,v2,v3,v4,v6,v5,K3,3,K3,3,K3,3不是平面图，因为无论如何画都不能使其所有边不相交。,平面图的简单性质,若图G是平面图，则G的任

6、何子图都是平面图。若图G是非平面图，则G的任何母图也都是非平面图。Kn(n5)和K3,n(n3)都是非平面图。设G是平面图，则在G中加平行边或环后所得图还是平面图。平行边与自回路不影响图的平面性，因此研究图的平面性时，不考虑平行边和环。,平面图面、边界、次数的定义,定义7-5.2 面：设G是一个连通平面图，由图中的边所包围的区域，在区域内既不包含图的结点，也不包含图的边，这样的区域称为图G的一个面，记为r。边界：包围该面的所有边所构成的回路称为这个面的边界。次数：边界（即回路）的长度称为该面的次数，即回路中边的条数，面r的次数记为deg(r)。环的次数=1。内部面：区域面积有限的面称为有限面（

7、或内部面）。外部面：区域面积无限的面称为无限面（或外部面）。显然，平面图有且仅有一个无限面。,例 求面的次数,有5个面 由如下回路包围:ADBAdeg(r1)=3 由如下回路包围:BCDBdeg(r2)=3 由如下回路包围:CDEFECdeg(r3)=5 由如下回路包围:ABCEAdeg(r4)=4 由如下回路包围：ADEAdeg(r5)=3,A,B,C,D,E,F,r1,r2,r3,r4,r5,相加为18，正好是边数9的2倍,r1,r2,r4,r5,r3,平面图的握手定理,定理7-5.1 一个有限平面图，面的次数之和等于其边数的两倍。即：证明：任取eE(G)。若e为面ri和rj(ij)的公共

8、边界上的边时，在计算ri和rj的次数时，e各提供1。若e只在某一个面的边界上出现时，则在计算该面的次数时，e提供2。于是每条边在计算总次数时，都提供2，因而,K2,考察下图所示平面图的面、边界和次数。,解 平面图把平面分成4个面：r0，边界为abdeheca，D(r0)=7r1，边界为abca，D(r1)=3r2，边界为becb，D(r2)=9r3，边界为bdeb，D(r3)=3r1、r2和r3是有限面，r0是无限面。,注意：对于平面图的不同平面表示，虽然面的数目相同，但各面的边界和次数会不同。,补充定理,定理 设G是n(n3)阶简单连通平面图，则G的每个面的次数大于等于3。证明：因为G的任意

9、一个面上至少有3个结点，所以G的每个面的次数都大于等于3。,欧拉定理,定理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,证明：归纳法若G为一个孤立结点，则v1，e0，r1，故v-e+r2成立。若G为一条边，则v2，e1，r1，则v-e+r2成立。设G为k条边时，欧拉公式成立。即 vk-ek+rk2。

10、下面考察G为k+1条边时的情况。因为在k条边的连通图上增加一条边，使它仍为连通图，只有下述两种情况：加上一个新的结点Q2，Q2与图上的一点Q1相连(如图(a)所示)，此时，vk和ek两者都增加1，而面数rk未变，故(vk+1)-(ek+1)+rkvk-ek+rk2，即命题成立。用一条边连接图上的已知点Q1和Q2，如图(b)所示，此时ek和rk都增加1，而结点数未变，故vk-(ek+1)+(rk+1)vk-ek+rk2，即命题成立。,欧拉定理证明v-e+r=2,运用欧拉(Euler)公式的局限性,用欧拉公式直接判定一个连通图是否是平面图是很难的，因为你在没有把这个图边不相交地画在一个平面上时，你

11、无法知道区域数是多少。,定理：判断平面图的必要条件-判断非平面图,定理7-5.3：设G是一个有v个结点e条边的连通简单平面图，若v3，则e3v-6。补充定理：每个圈至少由4条边组成的连通简单平面图，则有e2v-4。逆否命题：若e3v-6，则一定是非平面图。每个圈至少由4条边组成的图，e 2v-4，则一定是非平面图。,定理：判断平面图的必要条件,定理7-5.3：设G是一个有v个结点e条边的连通简单平面图，若v3，则e3v-6。分析：可利用如下的性质：(1)简单平面图中各个面的次数大于3；(2)各面次数之和为2e；(3)欧拉定理v-e+r=2证明：设连通平面图G的面数为r，已知v3当v=3，e=2

12、时，2 3*3-6，即上式成立。若v3，则每一面的次数大于等于3，由定理7-5.1知各面次数之和为2e，因此：2e3r 即 r2/3e 代入欧拉定理：2=v-e+rv-e+2/3e 2v-e/3 e3v-6,定理7-5.3的应用,定理7-5.3是平面图的必要条件，逆否命题：若e3v-6，则一定是非平面图。例：(1)证明K5不是平面图.解:在K5中有v=5个结点，e=10条边，因而对它有 3v-6=3*5-6=9 e=109=3v-6,根据定理7-5.3，K5它不是平面图。,K5,例：K3,3图，v=6,e=9,有e=93v-6=10，但k3,3 不是平面图。补充定理：每个圈至少由4条边组成的连

13、通简单平面图，则有e2v-4。证明：由题意知：每一面的次数大于等于4，2e4r，r1/2e,由欧拉公式：v-e+r=2,得到 v-e+r=2v-e+1/2 e,从而 即e2v-4，故命题得证。对于K3,3图，任意三个结点必有两个不邻接，因此每个区域的次数不小于4。但2v-4=2*6-4=89=e，即k3,3图不是平面图。,定理7-5.3的应用,K3,3,P319定理,定理：设G是至少三个结点的连通平面图，则(G)5。证明：反证法：若阶数 v6，结论显然成立。若阶数v7时，用反证法证明。假设(G)6，由握手定理可知：2e=deg(vi)v 6v e 3v 3v-6,与 e3v-6 矛盾。所以，假

14、设不成立，即G的最小度(G)5。,本定理在图着色理论中占重要地位。,说明,例 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,即v2-13v+24 0,(v-11)(v-2)+2 0,而当v 11时，(v-11)(v-2)+2 0，从而产生矛盾。因此G或G的补图 是非平面图。,K3,3的同构图,平面图的判断,判断一个图是否为平面图是

15、一件困难的事。通常我们可以采用直观的方法，即：在图中找出一个长度尽可能大的且边不相交的圈；然后将图中那些相交于非结点的边，适当放置在已选定的圈内侧或外侧，若能避免除结点之外边的相交，则该图为平面图，否则便是非平面图。例如，K5不是平面图，因为无论如何画都不能使其所有边不相交。另外，也可以采用下面的定理来判断。同胚库拉托夫斯基(Kuratowski)定理,平面图的判断-库拉托夫斯基(Kuratowski)定理,一、为判断定理做准备（库拉托夫斯基技术-波兰数学家）1、插入2度结点和消去2度结点插入2度结点w：设e=(u,v)为图G的一条边，在G中删除e，增加新的结点w，使u、v均与w相邻，称为插入

16、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度结点,例,库拉托夫斯基（Kuratowski）定理,波兰数学家库拉托夫斯基（Kuratowski）在1930年给出了判定一个图是平面图的这个充要条件。这个定理证明太复杂，我们仅介绍不证明。定理7-5.4：图G是平面图 G没

17、有与K5或K3,3在2度结点内同构的子图。在2度结点内同构：若G1和G2同构，或者反复插入或消去2度结点后仍同构，则称G1和G2在2度结点内同构的子图。Kuratowski定理的实际应用较困难,例 判定是否是平面图,库拉托夫斯基定理应用,库拉托夫斯基定理应用,（1）Petersen 图不是平面图,与K3,3同构,子图,消去2度结点,(2)不是平面图（自学）,库拉托夫斯基定理应用,子图,消去2度结点,K3,3,(3)解（自学）,K5,K3,3,库拉托夫斯基定理应用,子图,消去2度结点,子图,消去2度结点,本节小结,重点掌握平面图的握手定理重点掌握平面图中的欧拉公式及其应用重点掌握平面图的必要条件

18、及其应用理解库拉托夫斯基定理应用,知识点对偶图对偶图性质图着色,7-6 对偶图与着色,1 对偶图,定义7-6.1 给定一个平面图G，通过以下步骤，得到一新的图：(1)结点的构造：对图G的每个面Fi的内部，作一结点且仅作一结点vi*。(2)边的构造：经过每两个面Fi和Fj的每公共边界ek作一条边ek*(vi*,vj*)与ek相交。当且仅当ek只是一个面Fi的边界时。恰存在一环与ek相交。所得的图称为图G的对偶图，记G*。,对偶图定义（构造方法）：,例7-6.1：对偶图,对偶图,注意图中的一度结点和自环是怎样处理的。,2 对偶图的性质,对偶图是连通平面图环与桥互相对偶平行边对偶于2个面之间的多条边

19、界,对偶图的性质,v*=r,e*=e,v-e+r=2 2=v*-e*+r*=r-e+r*=2-v+r*,r*=vdegG*(vi*)=degG(Ri),v=6，r=4，e=8v*=4，r=6，e*=8,对偶图的性质,注意，当G1，G2为同构图的两种不同图示，那么它们的对偶图G1与G2不仅图示可能不同，而且可能是根本不同的图（不同构）。这就是说，一个图的对偶图未必是唯一的。,例,G1G2,不一定G1*G2*,自对偶(self-dual)图,定义7-6.2 自对偶图：G G*.,补充定理,定理：若图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。由此，K4是自对偶图，K3不是自对偶图。K4：4个结点，6条边 K3：3个结点，3条边,