《《离散数学》第七章图论-第5节.ppt》由会员分享，可在线阅读，更多相关《《离散数学》第七章图论-第5节.ppt（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、A(4)=A(2)A(5)=A(3)解：解：v1v1v2v2v3v3v4v4v5v5例例7-3.3 求右图中图求右图中图G中的可达性矩中的可达性矩阵。阵。v分析：先计算图的邻接矩阵分析：先计算图的邻接矩阵A布尔乘法的的布尔乘法的的2、3、4、5次幂，然后做布尔加即可。次幂，然后做布尔加即可。P=A A(2)A(3)A(4)A(5)1补充：二部图补充：二部图v二部图二部图：G=是图，图是图，图G的两个结点子的两个结点子集集V1，V2，满足满足V=V1V2,V1 V2=，且，且图图G的每一条边的每一条边e均具有均具有e(vi,vj)，其中，其中vi V1,vj V2。n若若V1中任一结点与中任一结
2、点与V2中每一结点均有边相连接，则中每一结点均有边相连接，则称二部图为完全二部图。若称二部图为完全二部图。若|V1|=r，|V2|=t，则记完全，则记完全二部图二部图G为为Kr,t。2补充：二部图补充：二部图vK3,33v在现实生活中，常常要画一些图形，希望在现实生活中，常常要画一些图形，希望边与边之间尽量减少相交的情况，例如印边与边之间尽量减少相交的情况，例如印刷线路板的布线，交通道的设计等，近些刷线路板的布线，交通道的设计等，近些年来，大规模集成电路的发展，进一步促年来，大规模集成电路的发展，进一步促进了图的平面性的研究。本节将简要地介进了图的平面性的研究。本节将简要地介绍平面图的概念，欧
3、拉公式和平面图的着绍平面图的概念，欧拉公式和平面图的着色。色。7-5 平面图平面图本章所涉及到的图均指无向图。本章所涉及到的图均指无向图。4 v平面图问题：在一块地上盖有三座房子，并且挖了三平面图问题：在一块地上盖有三座房子，并且挖了三口井供房主人使用。口井供房主人使用。v由于土质和气候等关系，这些井中的这一个或那一个由于土质和气候等关系，这些井中的这一个或那一个常常干枯。因此各座房子的主人有时要到这个井去打常常干枯。因此各座房子的主人有时要到这个井去打水，有时要到那个井去打水，三个井都可能需要去。水，有时要到那个井去打水，三个井都可能需要去。v不久，这三个房子的主人相互间变成了冤家，于是决不
4、久，这三个房子的主人相互间变成了冤家，于是决定修建各家通往三个井的小道，使得他们在去三个井定修建各家通往三个井的小道，使得他们在去三个井的途中不会相遇。的途中不会相遇。请问：你能否帮他们设计整个的小道路线，满足他们的请问：你能否帮他们设计整个的小道路线，满足他们的要求？要求？v对于许多问题，一个图怎样画出来无关紧要，只要与对于许多问题，一个图怎样画出来无关紧要，只要与原来的图同构怎样画都可以。原来的图同构怎样画都可以。v但是有些时候的实际问题要求我们在平面上完成该图，但是有些时候的实际问题要求我们在平面上完成该图，使得不是节点的地方不能有边相交出现。例如单层印使得不是节点的地方不能有边相交出现
5、。例如单层印刷电路板，集成电路的布线，通讯和交通中的某些问刷电路板，集成电路的布线，通讯和交通中的某些问题等，这就是可平面图问题。题等，这就是可平面图问题。制印刷电路板必须把电路除结点外导线不相交的印制在制印刷电路板必须把电路除结点外导线不相交的印制在线路板上。线路板上。v虽然交通立交桥、多层电路板已广泛出现在现实生活虽然交通立交桥、多层电路板已广泛出现在现实生活中，但可平面图问题仍然是其最基本的问题。中，但可平面图问题仍然是其最基本的问题。57-5 平面图平面图 井1井2井3提出问题提出问题6平面图平面图知识点：知识点：v平面图平面图,面面,v欧拉公式欧拉公式vKuratowski定理定理v
6、本章中的图均指无向图本章中的图均指无向图7平面图的定义平面图的定义v定义定义7-5.1 设设GV，E是一个无向图，是一个无向图，如果能够把如果能够把G的的所有结点和边所有结点和边画在平面上，画在平面上，且使且使任何任何两条边除了端点外没有其它的两条边除了端点外没有其它的交点交点，就称就称G是一个是一个平面图平面图。v非连通图可以对连通分支分别讨论非连通图可以对连通分支分别讨论。v注意注意，有些图形从表面上看有几条边是相交，有些图形从表面上看有几条边是相交的，但不能就此肯定它不是平面图。的，但不能就此肯定它不是平面图。8平面图的例平面图的例vK1(平凡图平凡图)，K2，K3，K4都是平面图都是平
7、面图K3K4K29判别平面图的直观方法判别平面图的直观方法-观察法观察法。（1）找出长度尽可能大的且边不相交的圈）找出长度尽可能大的且边不相交的圈 Cv1v2v3v4v1是是G中的任何圈。中的任何圈。（2）找出交叉的边，设）找出交叉的边，设P1v1v3和和P2v2v4是是G中的中的任意任意两条无公共结点两条无公共结点的边。的边。交叉交叉出现在边出现在边P1和和P2上。上。v对对P1和和P2的放置有的放置有4种种方法，方法，（1）P1和和P2或者都在圈或者都在圈C内部，或者都在圈内部，或者都在圈C外外部时，它们才会相交叉。部时，它们才会相交叉。（2）P1和和P2分别放置在分别放置在圈圈的内部或外
8、部，从而避的内部或外部，从而避免交叉。免交叉。v只有只有避免不了交叉时避免不了交叉时，这种图才是，这种图才是非平面图非平面图。v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v410例例K5e(K5删除任意一条边删除任意一条边)是平是平面图面图 11平面图的例平面图的例vK3,3-e是平面图吗？是平面图吗？12非平面图的例非平面图的例v完全图完全图K5和完全二部图和完全二部图K3,3都不是平面图都不是平面图K5K5nK5不是平不是平面图，因为面图，因为无论如何改无论如何改画都不能使画都不能使其所有边不其所有边不相交。相交。13完全二部图完全二部图K3,3非平面图的例
9、非平面图的例v1v2v3v4v6v5v1v2v3v4v6v5K3,3K3,3nK3,3不是平面图，因为无论如何画都不能不是平面图，因为无论如何画都不能使其所有边不相交。使其所有边不相交。v1v2v3v4v6v514完全二部图完全二部图K3,3非平面图的例非平面图的例v1v2v3v4v6v5v1v2v3v4v6v5K3,3K3,3nK3,3不是平面图，因为无论如何画都不能不是平面图，因为无论如何画都不能使其所有边不相交。使其所有边不相交。15平面图的简单性质平面图的简单性质v若图若图G是平面图，则是平面图，则G的任何子图都是平面图。的任何子图都是平面图。v若图若图G是非平面图，则是非平面图，则G
10、的任何的任何母图母图也都是非平也都是非平面图。面图。Kn(n5)和和K3,n(n3)都是非平面图。都是非平面图。v设设G是平面图，则在是平面图，则在G中加平行边或环后所得图中加平行边或环后所得图还是平面图。还是平面图。平行边与自回路不影响图的平面性，因此研究图平行边与自回路不影响图的平面性，因此研究图的平面性时，不考虑平行边和环。的平面性时，不考虑平行边和环。16平面图面、边界、次数的定平面图面、边界、次数的定义义v定义定义7-5.2 面：面：设设G是一个是一个连通平面图连通平面图，由图中的边所包，由图中的边所包围的区域，围的区域，在区域内既不包含图的结点，也不在区域内既不包含图的结点，也不包
11、含图的边，包含图的边，这样的区域称为图这样的区域称为图G的一个的一个面面，记，记为为r。边界：边界：包围该面的包围该面的所有边所有边所构成的回路称为这所构成的回路称为这个个面的边界面的边界。次数：边界（即回路）次数：边界（即回路）的长度称为该面的的长度称为该面的次数次数，即回路中边的条数，面即回路中边的条数，面r的次数记为的次数记为deg(r)。v环的次数环的次数=1。内部面：内部面：区域面积有限的面称为区域面积有限的面称为有限面（或内有限面（或内部面）部面）。外部面：外部面：区域面积无限的面称为区域面积无限的面称为无限面（或外无限面（或外部面）部面）。显然，平面图显然，平面图有且仅有一个无限
12、面有且仅有一个无限面。17例例 求面的次数求面的次数有有5个面个面 由如下回路包围由如下回路包围:ADBAdeg(r1)=3 由如下回路包围由如下回路包围:BCDBdeg(r2)=3 由如下回路包围由如下回路包围:CDEFECdeg(r3)=5 由如下回路包围由如下回路包围:ABCEAdeg(r4)=4 由如下回路包围：由如下回路包围：ADEAdeg(r5)=3ABCDEFr1r2r3r4r5相加为相加为18，正好是，正好是边数边数9的的2倍倍r1r2r4r5r3ABCDEFr1r2r3r4r518平面图的握手定理平面图的握手定理v定理定理7-5.1 一个一个有限平面图有限平面图，面的次数之和
13、，面的次数之和等于其边数的两倍。等于其边数的两倍。v即：即：v证明：任取证明：任取eE(G)。若若e为面为面ri和和rj(ij)的的公共边界上公共边界上的边时，的边时，在计算在计算ri和和rj的次数时，的次数时，e各提供各提供1。若若e只在只在某一个面的边界上出现某一个面的边界上出现时，则在时，则在计算该面的次数时，计算该面的次数时，e提供提供2。于是每条边在计算总次数时，都提供于是每条边在计算总次数时，都提供2，因，因而而K219考察下图所示平面图的面、边界考察下图所示平面图的面、边界和次数。和次数。a ab bd de ec ch hi ij jk kr r0 0r r1 1r r2 2r
14、 r3 3v解解 平面图把平面分成平面图把平面分成4个面：个面：vr0，边界为，边界为abdeheca，D(r0)=7vr1，边界为，边界为abca，D(r1)=3vr2，边界为，边界为becb，D(r2)=9vr3，边界为，边界为bdeb，D(r3)=3vr1、r2和和r3是有限面，是有限面，r0是是无限面。无限面。注意：注意：对于平面图的不同平面表示，虽然面对于平面图的不同平面表示，虽然面的数目相同，但各面的边界和次数会不同。的数目相同，但各面的边界和次数会不同。i ij ja ab bd de ec ch hk kr r0 0r r1 1r r2 2r r3 320补充定理补充定理v定理
15、定理 设设G是是n(n3)阶阶简单连通平面图简单连通平面图，则，则G的每个面的次数大于等于的每个面的次数大于等于3。v证明：因为证明：因为G的任意一个面上至少有的任意一个面上至少有3个个结点，所以结点，所以G的每个面的次数都大于等于的每个面的次数都大于等于3。21欧拉定理欧拉定理v定理定理7-5.2 欧拉定理欧拉定理：设设G是是连通平面图连通平面图，则，则 v-e+r=2（欧拉公（欧拉公式）式）其中其中v是是G结点数，结点数，e是是G边数，边数，r是是G的面数。的面数。例例1：在下图中验证欧拉公式在下图中验证欧拉公式vv=7，e=11，r=6：7-11+6=2。例例2：连通平面图：连通平面图2
16、0个结点，个结点，每个结点度数为每个结点度数为3，求这个平，求这个平面图的面数。面图的面数。解：解：v=20，握手定理：握手定理：3v=2e所以，所以，e=3/2v=30欧拉公式欧拉公式v-e+r=2得：得：r=1222证明：证明：归纳法归纳法v若若G为一个孤立结点，则为一个孤立结点，则v1，e0，r1，故，故v-e+r2成立。成立。v若若G为一条边，则为一条边，则v2，e1，r1，则，则v-e+r2成立。成立。v设设G为为k条边时，欧拉公式成立。即条边时，欧拉公式成立。即 vk-ek+rk2。下面考察下面考察G为为k+1条边时的情况。条边时的情况。因为在因为在k条边的连通图上增加一条边，使它
17、仍为连通图，条边的连通图上增加一条边，使它仍为连通图，只有下述两种情况：只有下述两种情况：加上一个新的结点加上一个新的结点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，即命题成立。，即命题成立。Q1Q2
18、欧拉定理欧拉定理证明证明v-e+r=2Q1Q223运用欧拉运用欧拉(Euler)公式的局限公式的局限性性用欧拉公式直接判定一个连通图是否是平面图用欧拉公式直接判定一个连通图是否是平面图是很难的，因为你在没有把这个图边不相交地是很难的，因为你在没有把这个图边不相交地画在一个平面上时，你无法知道区域数是多少。画在一个平面上时，你无法知道区域数是多少。24定理：判断平面图的必要条件定理：判断平面图的必要条件-判判断非平面图断非平面图v定理定理7-5.3：设设G是一个有是一个有v个结点个结点e条边的条边的连通连通简单平面图简单平面图，若，若v3，则，则e3v-6。v补充定理：补充定理：每个圈至少由每个
19、圈至少由4条边组成的连通简单条边组成的连通简单平面图平面图，则有，则有e2v-4。v逆否命题：逆否命题：v若若e3v-6，则一定是非平面图。则一定是非平面图。v每个圈至少由每个圈至少由4条边组成的图，条边组成的图，e 2v-4，则一，则一定是非平面图。定是非平面图。25定理：判断平面图的必要条件定理：判断平面图的必要条件v定理定理7-5.3：设设G是一个有是一个有v个结点个结点e条边的条边的连通连通简单平面图简单平面图，若，若v3，则，则e3v-6。v分析：分析：可利用如下的性质：可利用如下的性质：(1)简单平面图中各个面的次数大于简单平面图中各个面的次数大于3；(2)各面次数之和为各面次数之
20、和为2e；(3)欧拉定理欧拉定理v-e+r=2v证明：证明：设连通平面图设连通平面图G的面数为的面数为r，已知已知v3当当v=3，e=2时，时，2 3*3-6，即，即上式成立。上式成立。若若v3，则则每一面的次数大于等于每一面的次数大于等于3，由定理，由定理7-5.1知各面次数之和为知各面次数之和为2e，因此：因此：v 2e3r 即即 r2/3ev 代入欧拉定理：代入欧拉定理：2=v-e+rv-e+2/3e 2v-e/3 e3v-626定理定理7-5.3的应用的应用v定理定理7-5.3是平面图的必要条件，是平面图的必要条件，v逆否命题：若逆否命题：若e3v-6，则一定是非平面则一定是非平面图。
21、图。v例：例：(1)证明证明K5不是平面图不是平面图.解解:在在K5中有中有v=5个结点，个结点，e=10条边，因条边，因而对它有而对它有 3v-6=3*5-6=9 e=109=3v-6,根据定理根据定理7-5.3，K5它不是平面图。它不是平面图。K527例例：K3,3图，图，v=6,e=9,有有e=93v-6=10，但但k3,3 不是平面图。不是平面图。v补充定理：补充定理：每个圈至少由每个圈至少由4条边组成的条边组成的连通简连通简单平面图单平面图，则有，则有e2v-4。证明：证明：v由题意知：由题意知：v每一面的次数大于等于每一面的次数大于等于4，v2e4r，r1/2e,由欧拉公式：由欧拉
22、公式：v-e+r=2,得到得到 v-e+r=2v-e+1/2 e,从而从而 即即e2v-4，故命题得证。，故命题得证。v对于对于K3,3图，任意三个结点必有两个不邻接，图，任意三个结点必有两个不邻接，因此每个区域的次数不小于因此每个区域的次数不小于4。但但2v-4=2*6-4=8 3v-6,与与 e3v-6 矛盾。矛盾。v所以，假设不成立，即所以，假设不成立，即G的最小度的最小度(G)5。q本定理在图着色理论中占重要地位。本定理在图着色理论中占重要地位。说明说明29例例 P317（4）G=(V,E)是一个是一个简单简单无向图。若无向图。若|V|11，则，则G或或者者G的补图的补图 G 是非平面
23、图。是非平面图。证明证明:反证法。反证法。v设设G和和G的补图均是平面图，的补图均是平面图，G的结点数为的结点数为v.v 若若G有有e条边，其补有条边，其补有k条边，则有条边，则有 e+k=v(v-1)/2。v 因为因为G和其补均为平面图，有和其补均为平面图，有v e 3v-6v 和和 k 3v-6,v因此因此v(v-1)/2=e+k 6v-12,即即v2-13v+24 0,v(v-11)(v-2)+2 0,v而当而当v 11时，时，(v-11)(v-2)+2 0，从而产，从而产生矛盾。因此生矛盾。因此G或或G的补图的补图 是非平面图。是非平面图。30K3,3的同构图的同构图 31平面图的判断
24、平面图的判断v判断一个图是否为平面图是一件困难的事。通判断一个图是否为平面图是一件困难的事。通常我们可以采用直观的方法，即：在图中找出常我们可以采用直观的方法，即：在图中找出一个长度尽可能大的且边不相交的圈；然后将一个长度尽可能大的且边不相交的圈；然后将图中那些相交于非结点的边，适当放置在已选图中那些相交于非结点的边，适当放置在已选定的圈内侧或外侧，若能避免除结点之外边的定的圈内侧或外侧，若能避免除结点之外边的相交，则该图为平面图，否则便是非平面图。相交，则该图为平面图，否则便是非平面图。v例如，例如，K5不是平面图，因为无论如何画都不能不是平面图，因为无论如何画都不能使其所有边不相交。使其所
25、有边不相交。v另外，也可以采用下面的定理来判断。另外，也可以采用下面的定理来判断。v同胚同胚v库拉托夫斯基库拉托夫斯基(Kuratowski)定理定理32平面图的判断平面图的判断-库拉托夫斯基库拉托夫斯基(Kuratowski)定理定理一、为判断定理做准备（一、为判断定理做准备（库拉库拉托夫斯基托夫斯基技术技术-波兰数波兰数学家学家）1、插入插入2度结点和消去度结点和消去2度结点度结点v插入插入2度结点度结点w：设设e=(u,v)为图为图G的一条边，在的一条边，在G中删中删除除e，增加新的结点增加新的结点w，使使u、v均与均与w相邻，称为相邻，称为插入插入2度结点度结点w。当两点间已有边时，在
26、边上当两点间已有边时，在边上增加一个结点使一条边变成增加一个结点使一条边变成两条边。两条边。v消去消去2度结点度结点w：设设w为为G中一个中一个2度结点，度结点，w与与u、v相相邻，删除邻，删除w，增加新边增加新边(u,v)，称为称为消去消去2度结点度结点w。当两个结点都与第三个结点相邻接，而第三个结点的度当两个结点都与第三个结点相邻接，而第三个结点的度数为数为2时，删去第时，删去第3个结点，使两边合一边。个结点，使两边合一边。2、当两点间已有边时，在两点间、当两点间已有边时，在两点间增加重复边增加重复边或或删去重删去重复边。复边。uvuvwuuwvv插入插入2度度结点结点消去消去2度结点度结
27、点33例例34库拉托夫斯基（库拉托夫斯基（Kuratowski）定理定理v波兰数学家库拉托夫斯基（波兰数学家库拉托夫斯基（Kuratowski）在）在1930年给出了判定一个图是平面图的这个充年给出了判定一个图是平面图的这个充要条件。这个定理证明太复杂，我们仅介绍要条件。这个定理证明太复杂，我们仅介绍不证明。不证明。v定理定理7-5.4：图图G是平面图是平面图 G没有与没有与K5或或K3,3在在2度结点内同构的子图。度结点内同构的子图。v在在2度结点内同构：度结点内同构：若若G1和和G2同构，同构，或者或者反复反复插入或消去插入或消去2度结点后仍同构，则称度结点后仍同构，则称G1和和G2在在2
28、度结点内同构的子图。度结点内同构的子图。Kuratowski定理的实际应用较困难定理的实际应用较困难35例例 判定是否是平面图判定是否是平面图库拉托夫斯基定理应用库拉托夫斯基定理应用36库拉托夫斯基定理应库拉托夫斯基定理应用用v（1）Petersen 图不是平面图图不是平面图与与K3,3同构同构子图子图消去消去2度度结点结点37(2)不是平面图不是平面图（自学）（自学）K3,3库拉托夫斯基定理应用库拉托夫斯基定理应用子图子图消去消去2度度结点结点K3,338(3)解解（自学）（自学）K5K3,3库拉托夫斯基定理应用库拉托夫斯基定理应用子图子图消去消去2度度结点结点子图子图消去消去2度度结点结点
29、39本节小结本节小结v重点掌握平面图的握手定理重点掌握平面图的握手定理v重点掌握平面图中的欧拉公式及其应用重点掌握平面图中的欧拉公式及其应用v重点掌握平面图的必要条件及其应用重点掌握平面图的必要条件及其应用v理解理解库拉托夫斯基定理库拉托夫斯基定理应用应用40知识点知识点v对偶图对偶图v对偶图性质对偶图性质v图着色图着色 7-6 对偶图与着色对偶图与着色411 对偶图对偶图v定义定义7-6.1 给定一个给定一个平面图平面图G，通过以下步骤，通过以下步骤，得到一新的图：得到一新的图：v(1)结点的构造：结点的构造：对图对图G的每个面的每个面Fi的内部，作一结点且仅作的内部，作一结点且仅作一结点一
30、结点vi*。v(2)边的构造：边的构造：经过每两个面经过每两个面Fi和和Fj的每的每公共边界公共边界ek作作一条边一条边ek*(vi*,vj*)与与ek相交。相交。当且仅当当且仅当ek只是一个面只是一个面Fi的边界时。恰存的边界时。恰存在一环与在一环与ek相交。相交。v 所得的图称为图所得的图称为图G的对偶图，记的对偶图，记G*。对偶图定义（构造方法）：对偶图定义（构造方法）：42例例7-6.1：对偶图：对偶图对偶图对偶图注意图中的一度结点和自注意图中的一度结点和自环是怎样处理的。环是怎样处理的。432 对偶图的性质对偶图的性质v对偶图是对偶图是连通平面图连通平面图v环与桥互相对偶环与桥互相对
31、偶v平行边对偶于平行边对偶于2个面之间的多条边界个面之间的多条边界44对偶图的性质对偶图的性质vv*=r,e*=e,v-e+r=2 2=v*-e*+r*=r-e+r*=2-v+r*,vr*=vvdegG*(vi*)=degG(Ri)v=6，r=4，e=8v*=4，r=6，e*=845对偶图的性质对偶图的性质v注意，当注意，当G1，G2为同为同构图的两种不同图示，构图的两种不同图示，那么它们的对偶图那么它们的对偶图G1与与G2不仅图示可不仅图示可能不同，而且可能是能不同，而且可能是根本不同的图（不同根本不同的图（不同构）。这就是说，构）。这就是说，一一个图的对偶图未必是个图的对偶图未必是唯一的。唯一的。例例nG1 G2,不一定不一定G1*G2*46自对偶自对偶(self-dual)图图v定义定义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。由此，由此，K4是自对偶图，是自对偶图，K3不是自对偶图。不是自对偶图。K4：4个结点，个结点，6条边条边 K3：3个结点，个结点，3条边条边48