《图论》第5章-平面图

1[可平面性]一个图G=(V,E)，若能将其画在平面上，且任意两条边的交点只能是G的顶点，则称G可嵌入平面，或称G是一个可平面图(planargraph)。可平面图在平面上的一个嵌入称为一个平面图(planegraph)。树是一类重要的平面图。应用举例：印刷电路版、集成电路设计。一个可平面图和其平面嵌入是同构的。一般情况下不需作严格区分。5.1平面图及其性质2[区域]由平面图的边包围而成，其中不含图的顶点。也称为面。包围域R的所有边组成的回路称为该域的边界，回路长度称为该域的度，记为deg(R)。各域的边界：R0:v1v2v4v5v7v7v4v3v1R1:v1v2v4v3v1R2:v4v5v7v4v6v4R3:v7v7[例]deg(R0)=8,deg(R1)=4,deg(R2)=5,deg(R3)=1v2R1R2R0v1v3v4v5v6v7R35.1平面图及其性质35.1平面图及其性质[定理5-1-1]平面图G的所有域的度之和等于其边数m的2倍，即：1deg()2riiRm域的度也称为域的次数。[内部面和外部面]由平面图的边包围且无穷大的域称为外部面。（如上例的域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平面图及其性质N95.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(k1)时结论成立。当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+1。5.1平面图及其性质125.1平面图及其性质[定理5-1-5]设简单平面连通图G有n个顶点，m条边，d个域，各个域的度至少是l，则有(2)2nlml[证明]由欧拉公式：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是简单图，l2，结论形式可以得到证明。135.1平面图及其性质[推论]设简单平面图G的连通分支数为k，且有n个顶点，m条边，d个域，各个域的度至少是l，则有(1)2nklml[证明]由欧拉公式：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是简单图，l2，结论形式可以得到证明。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)3。[证明]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)6。5.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,320K5和K3,3称为基本的不可平面图，或Kuratowski图。K5K3,35.1平面图及其性质21[凸多面体的平面嵌入]一个凸多面体可嵌入球面因而可嵌入平面，获得一个简单平面图。设凸多面体有n个顶点，m条棱和d个面，则由平面图的Euler公式有n-m+d=2。正多面体是一种每个顶点的度相同，每个面的度也相同的凸多面体。5.1平面图及其性质22[定理5-1-10]存在且只存在5种正多面体：正四面体、正方体、正八面体正十二面体和正二十面体。(称为帕拉图多面体PlatonicSolids)[证明]将正d面体嵌入平面得到平面图G，易知G是一个r度正则图，且每个面的度相等，设为k。则有dk=2m,nr=2m，这里k3，r3。与Euler公式联立得n=4k(2kkr+2r)15.1平面图及其性质23[证明续]n=4k(2kkr+2r)1由于n0，k0，故须(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.2Kuratowski定理27[串联边置换]将上述e1,e2置换成e3=(u1,u3)，并消去可能的多重边的过程，称为串联边置换。e1e2u1u2u3e3u1u3u1u3e3e1e2u1u2u3e3u1u3e35.2Kuratowski定理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.2Kuratowski定理29[例]Petersen图不是平面图。AAABBBK3,35.2Kuratowski定理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*|。则当n5时，或n5且m9时，G是可平面的；当m3n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对偶图