《图论》第5章 平面图ppt课件.ppt

《《图论》第5章 平面图ppt课件.ppt》由会员分享，可在线阅读，更多相关《《图论》第5章 平面图ppt课件.ppt（39页珍藏版）》请在三一办公上搜索。

1、可平面性 一个图 G=(V, E) ，若能将其画在平面上，且任意两条边的交点只能是G的顶点，则称G可嵌入平面，或称G是一个可平面图 (planar graph)。可平面图在平面上的一个嵌入称为一个平面图(plane graph)。树是一类重要的平面图。应用举例：印刷电路版、集成电路设计。一个可平面图和其平面嵌入是同构的。一般情况下不需作严格区分。,5.1 平面图及其性质,区域 由平面图的边包围而成，其中不含图的顶点。也称为面。包围域 R 的所有边组成的回路称为该域的边界，回路长度称为该域的度，记为deg(R)。,各域的边界：R0: v1 v2 v4 v5 v7 v7 v4 v3 v1R1: v

2、1 v2 v4 v3 v1R2: v4 v5 v7 v4 v6 v4R3: v7 v7,例,deg(R0)=8, deg(R1)=4, deg(R2)=5, deg(R3)=1,5.1 平面图及其性质,5.1 平面图及其性质,定理5-1-1 平面图 G 的所有域的度之和等于其边数 m的2倍，即：,域的度也称为域的次数。内部面和外部面 由平面图的边包围且无穷大的域称为外部面。（如上例的域 R0 为外部面）一个平面图有且只有一个外部面。,球面嵌入 若能将图G画在平面上，且任意两条边的交点只能是G的顶点，则称G可嵌入球面。曲面嵌入 若能将图G画在一个曲面上，且任意两条边的交点只能是G的顶点，则称G可

3、嵌入该曲面。,5.1 平面图及其性质,例 K5可嵌入环面。,5.1 平面图及其性质,例 K3,3可嵌入Mbius带面。,5.1 平面图及其性质,定理5-1-2 一个图可嵌入平面当且仅当它可嵌入球面。证明 通过连续球极投影建立图的平面嵌入与球面嵌入的一一对应关系。,5.1 平面图及其性质,5.1 平面图及其性质,5.1 平面图及其性质,定理5-1-3 一个可平面图的任何平面嵌入的内部面都可以在另一种平面嵌入下成为外部面。证明 将该平面嵌入通过连续球极投影转换为一个球面嵌入，把讨论的平面图内部面所对应的球面部分旋转到北极，再转换为一个平面嵌入。,定理5-1-4 欧拉公式 设平面连通图G有n个顶点，

4、m条边，d个域，则有 nm+d = 2。证明 对d作归纳。 d=1时，G中只有一个区域，G为一棵树（无回路连通图），此时 m = n 1，故 nm+d = n (n1)+1 = 2。设 d=k (k1) 时结论成立。当 d=k+1时，在G中的两个相邻域边界上任取一条边去掉，得到的图G 的区域数 d= d1=k，且仍然是平面连通的，符合归纳假设条件，即 nm+d=2，而 n=n，m=m1，d= d1 ，故 nm+d = 2 成立。由归纳原理，命题得证。,5.1 平面图及其性质,从证明过程易知，欧拉公式对非简单图（多重边、自环）仍然成立。推论 设平面图G的连通分支数为k，并有n个顶点，m条边，d个

5、域，则有 nm+d = k+1。,5.1 平面图及其性质,5.1 平面图及其性质,定理5-1-5 设简单平面连通图G有n个顶点，m条边，d个域，各个域的度至少是 l，则有,证明由欧拉公式： nm+d =2 得 d =2+mn由定理5-1-1：2mld = l (2+mn)= (2n)l +ml联立得不等式： (l2)m (n2)l 又G是简单图， l 2，结论形式可以得到证明。,5.1 平面图及其性质,推论 设简单平面图G的连通分支数为k，且有n个顶点，m条边，d个域，各个域的度至少是 l，则有,证明由欧拉公式： nm+d =k+1 得 d = k+1+mn由定理5-1-1：2mld = l

6、(k+1+mn)= (k+1n)l +ml联立得不等式： (l2)m (n k1)l 又G是简单图， l 2，结论形式可以得到证明。,极大平面图 设G=(V, E)为简单平面图，|V|3，若对任意vi ,vjV，且 (vi ,vj) E，有G=(V, E(vi ,vj)为非平面图，则称G为一个极大平面图。“极大性”乃针对固定顶点数的图的边的数目而言。,5.1 平面图及其性质,定理5-1-6 极大平面图的性质极大平面图是连通图。极大平面图的每个面都由3条边组成。极大平面图有3d =2m（d为面数目，m 为边数目）。极大平面图G=(V, E)，若|V|4，则 vi V，有 deg(vi ) 3。证

7、明1, 2 反证法；3 由 2 和定理5-1-1直接得到；4 反证法，讨论deg(vi ) =2 和 deg(vi ) =1 的情形。,5.1 平面图及其性质,定理5-1-7 设极大平面图有n个顶点，m条边，d个域，则有m=3n6，d=2n4。证明 将极大平面图性质之 3d=2m 代入欧拉公式直接得到。推论 简单平面图有 m3n6，d2n4。定理5-1-8 简单平面图至少有一个顶点的度小于6。证明 对 n6的简单平面图，设任一顶点的度 6，得 2m6n，或 m3n，与推论矛盾。或叙述成：对简单平面图G，有 (G)6。,5.1 平面图及其性质,二部图 图G=(V, E)，若V可划分成V1和V2

8、两部分，使得： v1 V1，若( v1, v2 ) E ，则必 v2V2 ； v2 V2，若( v1, v2 ) E ，则必 v1V1 。 则称G为一个二部图。,例,5.1 平面图及其性质,完全二部图 设G=(V, E)为一个二部图， V1和V2 如上所述，若 (v1) (v2)(v1V1, v2V2 ( v1, v2 ) E)， 则称G为一个完全二部图，记为 Kn1, n2。 ( n1 =|V1| ，n2 =| V2 |),例 K3,3,5.1 平面图及其性质,定理5-1-9 K5 和K3,3 是不可平面的。,证明 反证法。设K5是可平面的。将 n=5，m=10，l=3代入定理5-1-5公式

9、，得 109，矛盾。同理设K3,3是可平面的。将 n=6，m=9，l=4代入定理5-1-5公式，得 98，矛盾。,K5,5.1 平面图及其性质,K3,3,K5 和K3,3 称为基本的不可平面图，或 Kuratowski 图。,5.1 平面图及其性质,凸多面体的平面嵌入 一个凸多面体可嵌入球面因而可嵌入平面，获得一个简单平面图。设凸多面体有n个顶点，m条棱和d个面，则由平面图的Euler公式有 n- m+d = 2。正多面体是一种每个顶点的度相同，每个面的度也相同的凸多面体。,5.1 平面图及其性质,定理5-1-10 存在且只存在5种正多面体：正四面体、正方体、正八面体正十二面体和正二十面体。

10、(称为帕拉图多面体 Platonic Solids) 证明 将正 d 面体嵌入平面得到平面图G，易知G是一个 r 度正则图，且每个面的度相等，设为 k。则有 d k = 2m, n r = 2m，这里 k3，r3。与Euler公式联立得 n = 4k(2kkr+2r)1,5.1 平面图及其性质,证明 续 n = 4k(2kkr+2r)1由于 n0，k0，故须 (2kkr+2r) 0，或 2(k+r)kr(I)又k 3(II)r 3(III)上述不等式组的解恰为5组。,5.1 平面图及其性质,证明 续2,5.1 平面图及其性质,例 帕拉图多面体 。,5.1 平面图及其性质,串联边 图 G=(V,

11、E) ，若e1=(u1 , u2)， e2=(u2 , u3)，且deg(u2)=2，则称e1与e2串联。,例,5.2 Kuratowski 定理,串联边置换 将上述e1, e2 置换成 e3=(u1 , u3) ，并消去可能的多重边的过程，称为串联边置换。,5.2 Kuratowski 定理,同胚 设无向图 G和G，若存在G，使得G和G分别经若干串联边置换后与G同构，则称G和G同胚.与K5同胚的图，称为K(1)型图；与K3,3同胚的图，称为K(2)型图；K(1)型图和K(2)型图统称K型图。定理5-2-1(Kuratowski) 图 G=(V,E) 可平面当且仅当G中不存在任何K型子图。(

12、证略)Kuratowski 定理的实际应用较为困难。,5.2 Kuratowski 定理,例 Petersen 图不是平面图。,K3,3,5.2 Kuratowski 定理,平面性等价图 图G=(V,E)，满足下列条件之一的图G*= (V*,E*) 称为图G的平面性等价图：G是不连通图，在G的两个连通分支之间增加一条边得到G*；对G中存在割点v，将G从v处分割得到由若干连通分支构成的G*；（Gv 的连通分支数比G多时，称 v 是G的一个割点。）对G作串联边置换得到G*;从G中移去自环得到G*；从G中移去多重边得到G*。,5.3 图的平面性检测,平面性的不完全判定 图G*=(V*,E*)是图G的

13、平面性等价图，n=|V*|，m=|E*|。则当 n3n6时，G是不可平面的。上述判定条件不能满足时，需要建立检测算法。平面性检测的DMP算法 参考：戴一奇，图论与代数结构,5.3 图的平面性检测,对偶图 图G=(V,E)，满足下列条件的图G*= (V*,E*) 称为图G的对偶图：G的任一“域 ”fi 内有且仅有一点vi*;对G的域 fi , fj 的共同边界 ek，画一条ek*=(vi*,vj* ) 且只与 ek 交于一点；若 ek 完全处于fi 中，则 vi*有一自环 ek* 且与 ek相交与一点。上述过程称为求对偶图的D(Drawing)过程，得到的对偶图称为原图的拓扑对偶。,5.4 对偶

14、图,对平面图G，D过程构造的G*是唯一的；对于非平面图， D过程可能不成立；对平面图G， D过程构造的G*也是平面图；不论图G是否连通，D过程得到的G*是连通的；若图G连通，且存在G*，则 (G*)*=G；对图G，若存在G*，则 G中回路相对应于G*中割集，G中割集相对应于G*中回路；若GG*，称G为一个自对偶图。,5.4 对偶图,定理5-4-1 对图G施行D过程得到G*，设 n, m, d 和 n*,m*,d* 分别表示G和G*的结点数、边数及域数，则有： m*=m , n*=d , deg(vi*)=deg(fi)证明由D过程直接得到。,5.4 对偶图,定理5-4-2(Whitney) 图

15、G有对偶图当且仅当G是平面图。证明 在平面图上施行D过程即得。 反证：设G有对偶G*且G不是平图。 由 Kuratowski 定理，此时G中含有K型子图。只需证明K(1)型图和K(2)型图，或K5 和K3,3都没有对偶即引起矛盾。,5.4 对偶图,(1) 设K5 有对偶。由D过程知其对偶图中，n*7 , m*=10。又K5的每个域至少由3边围成，即 deg(vi*)3。 故deg(vi*) 37=21又：deg(vi*) =2m*= 210=20于是： 20 21 矛盾。,5.4 对偶图,(2) 设K3,3 有对偶。由D过程知其对偶图中，n*5 , m*=9。又K3,3 的每个域至少由4边围成

16、，即 deg(vi*)4。 故deg(vi*) 45=20又：deg(vi*) =2m*=29=18于是： 18 20 矛盾。,5.4 对偶图,定理5-4-3 设G为平面图，施行D过程得到G*，设 n, m, d 和 n*,m*,d* 如上所述，k为G的连通分支数，则有：d* = nk+1证明 G*是平面连通图：n* m*+ d* = 2(I)由定理5-4-1：m*=m , n*=d(II)(II)代入(I) 得：d m+ d* = 2(III)又G 是平面图：n m+ d = k+1 或：d m = n + k+1(IV)(IV)代入(III) 得： n + k+1 + d* = 2即：d* = nk+1,5.4 对偶图,定理5-4-4 设G为平面图，则下列命题等价G是二部图；G的任意面的度是偶数；G的对偶图是Euler图。证明,5.4 对偶图,