《离散数学第十七章平面.ppt》由会员分享，可在线阅读，更多相关《离散数学第十七章平面.ppt（28页珍藏版）》请在三一办公上搜索。
1、1,第十七章 平面图,本章的主要内容平面图的基本概念欧拉公式平面图的判断平面图的对偶图,2,引言,许多实际问题可以抽象为这样的模式：在一些表示客体的结点之间“布线”、“建通道”，以建立它们之间的某些联系，要求这些“线”、“通道”在一个平面上而又不相互交叠。这正是本章要讨论的图论问题。例如，要在三个工作点A,B,C和三个原料库L,M,N之间建立各工作点到原料库的传输线，问是否可能使这些线路互不相交？如果用结点表示工作站，用边表示传输线，那么上述问题便可描述为：K3,3是否可以在一个平面上图示出来，使图中各边除端点外均不相交？另外，印刷电路板上的布线与交通道路的设计等都是此类问题。为了深入讨论这个
2、问题，需要引入平面图的概念。,3,在图中，(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.,17.1 平面图的基本概念,定义17.1(1)G可嵌入曲面S若能将G除顶点外无边相交地画在S上(2)G是可平面图或平面图G可嵌入平面(3)平面嵌入画出的无边相交的平面图(4)非平面图无平面嵌入的无向图,(1)(2)(3)(4),4,几点说明及一些简单结论,一般所谈平面图不一定是指平面嵌入，上图中4个图都是平面图，但讨论某些性质时，一定是指平面嵌入.结论：(1)K5,K3,3都不是平面图（待证）(2)设GG，若G为平面图，则G也是平面图（定理17.1）(3)设GG，若G为非平面图，则G也是非平面图（定
3、理17.2），由此可知，Kn(n6)，K3,n(n4)都是非平面图.(4)平行边与环不影响平面性.,5,平面图(平面嵌入)的面与次数,定义17.2(1)G的面由G的平面嵌入的边将平面化分成的区域(2)无限面或外部面（可用R0表示）面积无限的面(3)有限面或内部面（可用R1,R2,Rk等表示）面积 有限的面(4)面 Ri 的边界包围Ri的回路组(5)面 Ri 的次数Ri边界的长度，用deg(Ri)表示,6,定理17.4 平面图各面次数之和等于边数的两倍.,几点说明,若平面图G有k个面，可笼统地用R1,R2,Rk表示，不需要指出外部面.定义17.2(4)中回路组是指：边界可能是初级回路(圈)，可能
4、是简单回路，也可能是复杂回路.特别地，还可能是非连通的回路之并.,平面图有4个面，deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8.请写各面的边界.,7,极大平面图,定义17.3 若在简单平面图G中的任意两个不相邻的顶点之间加一条新边所得图为非平面图，则称G为极大平面图.注意：若简单平面图G中已无不相邻顶点，G显然是极大平面图，如K1(平凡图),K2,K3,K4都是极大平面图.,极大平面图的主要性质定理17.5 极大平面图是连通的.证明线索：否则，加新边不破坏平面性,定理17.6 n（n3）阶极大平面图中不可能有割点和桥.证明线索：由定理17.5及n3可知，G中若
5、有桥，则一定有割点，因而只需证无割点即可.方法还是反证法.,8,证明线索：(1)由于n3,又G必为简单平面图可知，G每个面的次数均3.(2)因为G为平面图，又为极大平面图.可证G不可能存在次数3的面.就给出的图讨论即可.,极大平面图的性质,定理17.7 设G为n（n3）阶极大平面图，则G的每个面的次数均为3.,9,定理17.7中的条件也是极大平面图的充分条件.定理17.7 设G为n(n3)阶平面图，且每个面的次数均为3，则G为极大平面图.,定理的应用,上图中，只有(3)为极大平面图,(1)(2)(3),10,极小非平面图,定义17.4 若在非平面图G中任意删除一条边，所得图G为平面图，则称G为
6、极小非平面图.由定义不难看出：(1)K5,K3,3都是极小非平面图(2)极小非平面图必为简单图,图中所示各图都是极小非平面图.,11,定理17.9（欧拉公式的推广）设G是具有k（k2）个连通分支的平面图，则nm+r=k+1证明中对各连通分支用欧拉公式，并注意即可.,17.2 欧拉公式,定理17.8 设G为n阶m条边r个面的连通平面图，则nm+r=2（此公式称为欧拉公式）证 对边数m做归纳法m=0，G为平凡图，结论为真.设m=k（k1）结论为真，m=k+1时分情况讨论.(1)G中无圈，则G为树，删除一片树叶，用归纳假设.(2)否则，在某一个圈上删除一条边，进行讨论.,12,解得,定理17.11
7、在具有k（k2）个连通分支的平面图中，,与欧拉公式有关的定理,定理17.10 设G为连通的平面图，且deg(Ri)l,l3，则,证 由定理17.4及欧拉公式得,推论 K5,K3,3不是平面图.,13,定理17.12 设G为n（n3）阶m条边的简单平面图，则m3n6.证 设G有k（k1）个连通分支，若G为树或森林，当n3时，m3n6为真.否则G中含圈，每个面至少由l（l3）条边围成，又,定理17.13 设G为n（n3）阶m条边的极大平面图，则m=3n6.证 由定理17.4,欧拉公式及定理17.7所证.定理17.14 设G 为简单平面图，则(G)5.证 阶数 n6，结论为真.当n7 时，用反证法.
8、否则会推出2m6n m3n，这与定理17.12矛盾.,与欧拉公式有关的定理,在l=3达到最大值，由定理17.11可知m3n6.,14,17.3 平面图的判断,1.插入2度顶点和消去2度顶点定义17.5(1)消去2度顶点v，见下图中，由(1)到(2)(2)插入2度顶点v，见下图中，从(2)到(1).,(1)(2),15,2.收缩边e，见下图所示.,3.图之间的同胚定义17.6 若G1G2，或经过反复插入或消去2度顶点后所得G1G2，则称G1与G2同胚.,图的同胚,右边两个图同胚,16,平面图判定定理,定理17.15 G是平面图 G中不含与K5或K3,3同胚的子图.定理17.16 G是平面图 G中
9、无可收缩为K5或K3,3的子图,例1 证明所示图(1)与(2)均为非平面图.,(1)(2),右图(1),(2)分别为原图(1),(2)的子图与K3,3,K5同胚.,子图(1)(2),17,17.4 平面图的对偶图,定义17.7 设G是某平面图的某个平面嵌入，构造G的对偶图G*如下：(1)在G的面Ri中放置G*的顶点v*i.(2)设e为G的任意一条边.若e在G的面 Ri与 Rj 的公共边界上，做G*的边e*与e相 交，且e*关联G*的位于Ri与Rj中的顶点v*i与v*j，即 e*=(v*i,v*j)，e*不与其它任何边相交.若e为G中的桥且在面Ri的边界上，则e*是以Ri中G*的顶 点v*i为端
10、点的环，即e*=(v*i,v*i).,18,下面两图中，实线边图为平面图，虚线边图为其对偶图.,实例,19,G 的对偶图G*有以下性质：(1)G*是平面图，而且是平面嵌入.(2)G*是连通图(3)若边e为G中的环，则G*与e对应的边e*为桥，若e为桥，则G*中与e对应的边e*为环.(4)在多数情况下，G*为多重图（含平行边的图）.(5)同构的平面图（平面嵌入）的对偶图不一定是同构的.如上面的例子.,对偶图的性质,20,平面图与对偶图的阶数、边数与面数之间的关系,定理17.17 设G*是连通平面图G的对偶图，n*,m*,r*和n,m,r分别为G*和G的顶点数、边数和面数，则(1)n*=r(2)m
11、*=m(3)r*=n(4)设G*的顶点v*i位于G的面Ri中，则dG*(v*i)=deg(Ri)证明线索(1)、(2)平凡.(3)应用欧拉公式.(4)的证明中注意，桥只能在某个面的边界中，非桥边在两个面的边界上.,21,平面图与对偶图的阶数、边数与面数之间的关系,定理17.18 设G*是具有k（k2）个连通分支的平面图G的对偶图，则(1)n*=r(2)m*=m(3)r*=nk+1(4)设G*的顶点v*i位于G的面Ri中，则dG*(v*i)=deg(Ri)其中n*,m*,r*,n,m,r同定理17.17.证明(3)时应同时应用欧拉公式及欧拉公式的推广.,22,自对偶图,定义17.8 设G*是平面
12、图G的对偶图，若G*G，则称G为自对偶图.轮图定义如下：在n1（n4）边形Cn1内放置1个顶点，使这个顶点与Cn1上的所有的顶点均相邻.所得n 阶简单图称为n阶轮图.n为奇数的轮图称为奇阶轮图，n为偶数的轮图称为偶阶轮图，常将 n 阶轮图记为Wn.轮图都是自对偶图.图中给出了W6和W7.请画出它们的对偶图，从而说明它们都是自对偶图.,23,第十七章 习题课,主要内容平面图的基本概念欧拉公式平面图的判断平面图的对偶图基本要求深刻理解本部分的基本概念：平面图、平面嵌入、面、次数、极大平面图、极小非平面图、对偶图牢记极大平面图的主要性质和判别方法熟记欧拉公式及推广形式，并能用欧拉公式及推广形式证明有
13、关定理与命题会用库拉图斯基定理证明某些图不是平面图 记住平面图与它的对偶图阶数、边数、面数之间的关系,24,练习1,解 设G的阶数、边数、面数分别为n,m,r.(1)否则，由欧拉公式得 2m 5r=5(2+mn)由于(G)3及握手定理又有 2m 3n 由与得 m30 又有 r=2+mn 12 由及又可得 m30,是矛盾的.(2)正十二面体是一个反例,1.设G是连通的简单的平面图，面数r12，(G)3.(1)证明G中存在次数4的面(2)举例说明当r=12时，(1)中结论不真.,25,2.设G是阶数n11的无向平面图，证明G和 不可能全是平面图.,证 只需证明G和 中至少有一个是非平面图.采用反证
14、法.否则 与G 都是平面图，下面来推出矛盾.G与 的边数m,m应满足(Kn的边数)由鸽巢原理知m或m，不妨设m，,又由定理17.12 知 m 3n 6 由与得 n213n+24 0 由解得 2 n 10 与n 11矛盾.其实，当n=9,10时，命题结论已真.,练习2,26,3.证明下图为非平面图,练习3,27,证明,证 用库拉图斯基定理证明方法一.下图为原图的子图，它是K3,3，由库拉图斯基定理得证命题.,方法二.下图为原图的子图（删除边(a,f)），收缩本图中的(a,e)和(f,g)所得图为K5,由库拉图斯基定理得证命题.,28,图20,图19,练习4,4.设G为n（n3）阶极大平面图，证明G的对偶图G*是2-边连通的3-正则图.,证 证明中用上n3的极大平面图的性质，以及平面图与对偶图的关系，对偶图的连通性等.(1)证G*是2-边连通的.由G*的连通性可知，(G*)1，又因为G为极大平面 图，故G为简单图，所以G*中无桥（因为G中无环），所以，(G*)2.故G*为2-边连通的.(2)证G*是3-正则图.易知G*为简单图，且每个顶点的度数均为3（由定理 17.7决定），故G*为3-正则图.,
