《图论》第5章平面图

1[可平面性]一个图G=(V,E)，若能将其画在平面上，且任意两条边的交点只能是G的顶点，则称G可嵌入平面，或称G是可平面的。可平面图在平面上的一个嵌入称为一个平面图。树是一类重要的平面图。应用举例：印刷电路版、集成电路设计。5.1平面图及其性质2[区域]由平面图的边包围而成，其中不含图的顶点。也称为面。包围域R的所有边组成的回路称为该域的边界，回路长度称为该域的度，记为deg(R)。5.1平面图及其性质v2R1R2R0v1v3v4v5v6v7各域的边界：R0:v1v2v4v5v7v7v4v3v1R1:v1v2v4v3v1R2:v4v5v7v4v6v4R3:v7v7[例]deg(R0)=8,deg(R1)=4,deg(R2)=5,deg(R3)=1R33[内部面和外部面]由平面图的边包围且无穷大的域称为外部面。（如上例的域R0为外部面）一个平面图有且只有一个外部面。[曲面嵌入]一个图可嵌入平面当且仅当它可嵌入曲面.5.1平面图及其性质1deg()2riiRm[定理5-1-1]平面图G的所有域的度之和等于其边数m的2倍，即：4[定理5-1-2欧拉公式]设平面连通图G有n个顶点，m条边，d个域，则有n-m+d=2。[证明1]对m作归纳。[证明2]对d作归纳。欧拉公式对非简单图仍然成立。[推论]设平面图G的连通分支数为k，并有n个顶点，m条边，d个域，则有n-m+d=k+1。5.1平面图及其性质5[极大平面图]设G=(V,E)为简单平面图，|V|3，若对任意vi,vjV，且(vi,vj)E，有G=(V,E{(vi,vj)})为非平面图，则称G为一个极大平面图。“极大性”乃针对固定顶点数的图的边的数目而言。5.1平面图及其性质6[极大平面图的性质]1.极大平面图是连通图。2.极大平面图的每个面都由3条边组成。3.极大平面图有3d=2m（d为面数目，m为边数目）。4.极大平面图G=(V,E)，若|V|4，则viV，有deg(vi)3。[证明]5.1平面图及其性质7[定理5-1-3]设极大平面图G有n个顶点，m条边，d个域，则有m=3n-6，d=2n-4。[证明]将3d=2m代入欧拉公式。[推论]简单平面图G有m3n-6，d2n-4。[定理5-1-4]简单平面图至少有一个顶点的度小于6。[证明]设任一点的度6，得m3n，矛盾。5.1平面图及其性质8[二部图]图G=(V,E)，若V可划分成V1和V2两部分，使得：①v1V1，若(v1,v2)E，则必v2V2;②v2V2，若(v1,v2)E，则必v1V1。则称G为一个二部图。5.1平面图及其性质[例]9[完全二部图]设G=(V,E)为一个二部图，V1和V2如上所述，若(v1)(v2)(v1V1,v2V2(v1,v2)E)，则称G为一个完全二部图，记为Kn1,n2。(n1=|V1|，n2=|V2|)5.1平面图及其性质[例]K3,310[定理5-1-5]K5和K3,3是不可平面的。[证明]反证法并由欧拉公式导出矛盾.K5和K3,3称为基本的不可平面图，或Kuratowski图。K5K3,35.1平面图及其性质11[串联边]图G=(V,E)，若e1=(u1,u2)，e2=(u2,u3)，且deg(u2)=2，则称e1与e2串联。e1e2u1u2u35.2Kuratowski定理[例]12[串联边置换]将上述e1,e2置换成e3=(u1,u3)，并消去可能的多重边的过程，称为串联边置换。e1e2u1u2u3e3u1u3u1u3e3e1e2u1u2u3e3u1u3e35.2Kuratowski定理13[同胚]设无向图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定理14[例]Petersen图不是平面图。5.2Kuratowski定理AAABBBK3,315[平面性等价图]图G=(V,E)，满足下列条件之一的图G*=(V*,E*)称为图G的平面性等价图：1.G是不连通图，在G的两个连通分支之间增加一条边得到G*;2.对G中存在割点v，将G从v处分割得到由若干连通分支构成的G*；3.对G作串联边置换得到G*;4.从G中移去自环得到G*；5.从G中移去多重边得到G*。5.3图的平面性检测16[平面性的不完全判定]图G*=(V*,E*)，n=|V|，m=|E|，则当n5，或n=5且m9时，G是可平面的；当m3n-6，G是不可平面的；[平面性检测的DMP算法]戴书P755.3图的平面性检测17[对偶图]图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过程，得到的对偶图称为原图的拓扑对偶。5.4对偶图18对平面图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对偶图19[定理5-4-1(Whitney)]图G有对偶图当且仅当G是平面图。[证明]在平面图上施行D过程即得。反证：设G有对偶G*且G不是平图。由Kuratowski定理，此时G中含有K型子图。只需证明K(1)型图和K(2)型图，或K5和K3,3都没有对偶即引起矛盾。5.4对偶图20[定理5-4-2]对图G施行D过程得到G*，设n,m,d和n*,m*,d*分别表示G和G*的结点数、边数及域数，则有：m*=m,n*=d,deg(vi*)=deg(fi)[证明]由D过程直接得到。5.4对偶图21[定理5-4-3]设G为平面图，施行D过程得到G*，设n,m,d和n*,m*,d*如上所述，k为G的连通分支数，则有：d*=nk+1[证明]G*是平面连通图:n*m*+d*=2G是平面图:nm+d=k+1由[定理5-3-2]:m*=m,n*=d综上可得：d*=nk+15.4对偶图