图论第5章平面图说课材料.ppt

《图论》第《图论》第5 5章章- -平面图平面图2[ [区域区域] ] 由平面图的边包围而成，其中不含图的顶点也称为面包围域 R 的所有边组成的回路称为该域的边界，回路长度称为该域的度，记为deg(R)各域的边界：R0: v1 v2 v4 v5 v7 v7 v4 v3 v1R1: v1 v2 v4 v3 v1R2: v4 v5 v7 v4 v6 v4R3: v7 v7 [例例]deg(R0)=8, deg(R1)=4, deg(R2)=5, deg(R3)=1v2R1R2R0v1v3v4v5v6v7R35.1 平面图及其性质35.1 平面图及其性质[定理定理5-1-1] 平面图 G 的所有域的度之和等于其边数 m的2倍，即：Ø域的度也称为域的次数[ [内部面和外部面内部面和外部面] ] 由平面图的边包围且无穷大的域称为外部面如上例的域 R0 为外部面）Ø一个平面图有且只有一个外部面4[球面嵌入球面嵌入] 若能将图G画在平面上，且任意两条边的交点只能是G的顶点，则称G可嵌入球面[曲面嵌入曲面嵌入] 若能将图G画在一个曲面上，且任意两条边的交点只能是G的顶点，则称G可嵌入该曲面5.1 平面图及其性质5[ [例例] ] K5可嵌入环面。

5.1 平面图及其性质6[ [例例] ] K3,3可嵌入Mőbius带面5.1 平面图及其性质7[定理定理5-1-2] 一个图可嵌入平面当且仅当它可嵌入球面[证明] 通过连续球极投影建立图的平面嵌入与球面嵌入的一一对应关系5.1 平面图及其性质85.1 平面图及其性质N95.1 平面图及其性质[定理定理5-1-3] 一个可平面图的任何平面嵌入的内部面都可以在另一种平面嵌入下成为外部面[证明] 将该平面嵌入通过连续球极投影转换为一个球面嵌入，把讨论的平面图内部面所对应的球面部分旋转到北极，再转换为一个平面嵌入10[定理定理5-1-4 欧拉公式欧拉公式] 设平面连通图G有n个顶点，m条边，d个域，则有 nm+d = 2[证明] 对d作归纳 d=1时，G中只有一个区域，G为一棵树（无回路连通图），此时 m = n  1，故 nm+d = n (n1)+1 = 2设 d=k (k>1) 时结论成立当 d=k+1时，在G中的两个相邻域边界上任取一条边去掉，得到的图G’ 的区域数 d’= d1=k，且仍然是平面连通的，符合归纳假设条件，即 n’m’+d’=2，而 n’=n，m’=m1，d’= d1 ，故 nm+d = 2 成立。

由归纳原理，命题得证5.1 平面图及其性质11Ø从证明过程易知，欧拉公式对非简单图（多重边、自环）仍然成立[推论推论] 设平面图G的连通分支数为k，并有n个顶点，m条边，d个域，则有 nm+d = k+15.1 平面图及其性质125.1 平面图及其性质[定理定理5-1-5] 设简单平面连通图G有n个顶点，m条边，d个域，各个域的度至少是 l，则有[证明]由欧拉公式： nm+d =2 得 d =2+mn由定理5-1-1：2mld = l (2+mn)= (2n)l +ml联立得不等式： (l2)m (n2)l 又G是简单图， l >2，结论形式可以得到证明135.1 平面图及其性质[推论推论] 设简单平面图G的连通分支数为k，且有n个顶点，m条边，d个域，各个域的度至少是 l，则有[证明]由欧拉公式： nm+d =k+1 得 d = k+1+mn由定理5-1-1：2mld = l (k+1+mn)= (k+1n)l +ml联立得不等式： (l2)m (n k1)l 又G是简单图， l >2，结论形式可以得到证明14[ [极大平面图极大平面图] ] 设G=(V, E)为简单平面图，|V|3，若对任意vi ,vjV，且 (vi ,vj)  E，有G=(V, E{(vi ,vj)})为非平面图，则称G为一个极大平面图。

Ø“极大性”乃针对固定顶点数的图的边的数目而言5.1 平面图及其性质15[定理定理5-1-6 极大平面图的性质极大平面图的性质]1.极大平面图是连通图2.极大平面图的每个面都由3条边组成3.极大平面图有3d =2m（d为面数目，m 为边数目）4.极大平面图G=(V, E)，若|V|4，则 vi V，有 deg(vi )  35.[证明证明]6.1, 2 反证法；3 由 2 和定理5-1-1直接得到；4 反证法，讨论deg(vi ) =2 和 deg(vi ) =1 的情形5.1 平面图及其性质16[定理定理5-1-7] 设极大平面图有n个顶点，m条边，d个域，则有m=3n6，d=2n4[证明证明] 将极大平面图性质之 3d=2m 代入欧拉公式直接得到[推论推论] 简单平面图有 m3n6，d2n4[定理定理5-1-8] 简单平面图至少有一个顶点的度小于6[证明证明] 对 n6的简单平面图，设任一顶点的度 6，得 2m6n，或 m3n，与推论矛盾Ø或叙述成：对简单平面图G，有 (G)65.1 平面图及其性质17[ [二部图二部图] ] 图G=(V, E)，若V可划分成V1和V2 两部分，使得：① v1 V1，若( v1, v2 ) E ，则必 v2V2 ； ② v2 V2，若( v1, v2 ) E ，则必 v1V1 。

则称G为一个二部图[例例]5.1 平面图及其性质18[ [完全二部图完全二部图] ] 设G=(V, E)为一个二部图， V1和V2 如上所述，若 (v1) (v2)(v1V1, v2V2 ( v1, v2 ) E)， 则称G为一个完全二部图，记为 Kn1, n2 ( n1 =|V1| ，n2 =| V2 |)[例例] K3,35.1 平面图及其性质19[定理定理5-1-9] K5 和K3,3 是不可平面的[证明证明] 反证法设K5是可平面的将 n=5，m=10，l=3代入定理5-1-5公式，得 109，矛盾同理设K3,3是可平面的将 n=6，m=9，l=4代入定理5-1-5公式，得 98，矛盾K55.1 平面图及其性质K3,320ØK5 和K3,3 称为基本的不可平面图，或 Kuratowski 图K5K3,35.1 平面图及其性质21[ [凸多面体的平面嵌入凸多面体的平面嵌入] ] 一个凸多面体可嵌入球面因而可嵌入平面，获得一个简单平面图设凸多面体有n个顶点，m条棱和d个面，则由平面图的Euler公式有 n- m+d = 2。

Ø正多面体是一种每个顶点的度相同，每个面的度也相同的凸多面体5.1 平面图及其性质22[定理定理5-1-10] 存在且只存在5种正多面体：正四面体、正方体、正八面体正十二面体和正二十面体 (称为帕拉图多面体 Platonic Solids) [证明证明] 将正 d 面体嵌入平面得到平面图G，易知G是一个 r 度正则图，且每个面的度相等，设为 k则有 d k = 2m, n r = 2m，这里 k3，r3与Euler公式联立得 n = 4k(2kkr+2r)15.1 平面图及其性质23[证明证明 续续] n = 4k(2kkr+2r)1由于 n>0，k>0，故须 (2kkr+2r) >0，或 2(k+r)>kr(I)又k  3(II)r  3(III)上述不等式组的解恰为5组5.1 平面图及其性质24[证明证明 续续2] rknmd33464正四面体正四面体348126正方体正方体35203012正十二面体正十二面体436128正八面体正八面体53123020正二十面体正二十面体5.1 平面图及其性质25[ [例例] ] 帕拉图多面体 5.1 平面图及其性质26[ [串联边串联边] ] 图 G=(V,E) ，若e1=(u1 , u2)， e2=(u2 , u3)，且deg(u2)=2，则称e1与e2串联。

e1e2u1u2u3[例例]5.2 Kuratowski 定理27[ [串联边置换串联边置换] ] 将上述e1, e2 置换成 e3=(u1 , u3) ，并消去可能的多重边的过程，称为串联边置换e1e2u1u2u3e3u1u3u1u3e3e1e2u1u2u3e3u1u3e35.2 Kuratowski 定理28[ [同胚同胚] ] 设无向图 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型子图 证略)ØKuratowski 定理的实际应用较为困难5.2 Kuratowski 定理29[例例] Petersen 图不是平面图AAABBBK3,35.2 Kuratowski 定理30[ [平面性等价图平面性等价图] ] 图G=(V,E)，满足下列条件之一的图G*= (V*,E*) 称为图G的平面性等价图：1.G是不连通图，在G的两个连通分支之间增加一条边得到G*；2.对G中存在割点v，将G从v处分割得到由若干连通分支构成的G*；（Gv 的连通分支数比G多时，称 v 是G的一个割点。

3.对G作串联边置换得到G*;4.从G中移去自环得到G*；5.从G中移去多重边得到G*5.3 图的平面性检测31[ [平面性的不完全判定平面性的不完全判定] ] 图G*=(V*,E*)是图G的平面性等价图，n=|V*|，m=|E*|则当 n<5时，或 n5 且 m<9 时，G是可平面的；当 m>3n6时，G是不可平面的Ø上述判定条件不能满足时，需要建立检测算法[ [平面性检测的平面性检测的DMP算法算法] ] 参考：戴一奇，图论与代数结构5.3 图的平面性检测32[ [对偶图对偶图] ] 图G=(V,E)，满足下列条件的图G*= (V*,E*) 称为图G的对偶图：1.G的任一“域 ”fi 内有且仅有一点vi*;2.对G的域 fi , fj 的共同边界 ek，画一条ek*=(vi*,vj* ) 且只与 ek 交于一点；3.若 ek 完全处于fi 中，则 vi*有一自环 ek* 且与 ek相交与一点Ø上述过程称为求对偶图的D(Drawing)过程，得到的对偶图称为原图的拓扑对偶5.4 对偶图33Ø对平面图G，D过程构造的G*是唯一的；对于非平面图， D过程可能不成立；Ø对平面图G， D过程构造的G*也是平面图；Ø不论图G是否连通，D过程得到的G*是连通的；Ø若图G连通，且存在G*，则 (G*)*=G；Ø对图G，若存在G*，则 G中回路相对应于G*中割集，G中割集相对应于G*中回路；Ø若GG*，称G为一个自对偶图。

5.4 对偶图34[定理定理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 对偶图35[ [定理定理5-4-2(Whitney)] ] 图G有对偶图当且仅当G是平面图[证明证明]  在平面图上施行D过程即得  反证：设G有对偶G*且G不是平图 由 Kuratowski 定理，此时G中含有K型子图只需证明K(1)型图和K(2)型图，或K5 和K3,3都没有对偶即引起矛盾5.4 对偶图36(1) 设K5 有对偶由D过程知其对偶图中，n*7 , m*=10又K5的每个域至少由3边围成，即 deg(vi*)3 故∑deg(vi*) 37=21又：∑deg(vi*) =2m*= 210=20于是： 20  21 矛盾5.4 对偶图37(2) 设K3,3 有对偶由D过程知其对偶图中，n*5 , m*=9又K3,3 的每个域至少由4边围成，即 deg(vi*)4 故∑deg(vi*) 45=20又：∑deg(vi*) =2m*=29=18于是： 18  20 矛盾。

5.4 对偶图38[定理定理5-4-3] 设G为平面图，施行D过程得到G*，设 n, m, d 和 n*,m*,d* 如上所述，k为G的连通分支数，则有：d* = nk+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* = nk+15.4 对偶图39[定理定理5-4-4] 设G为平面图，则下列命题等价(1)G是二部图；(2)G的任意面的度是偶数；(3)G的对偶图是Euler图[证明证明]5.4 对偶图结束结束。