第四章平面图

第四章平面图（planargraph）4.1平面图的基本概念4.1.1平面图及平面嵌入在一张纸上画图的图解时常常会发现，不仅需要允许各条边在结点上相交，而且还允许各条边在某些点上相交。这样的点称为交叉点；而相交的边，说成是相互交叉的边。例4.1在图4.1(a)中，给出了一个无向图，其中有三个交叉：边(v1,v4)和边(v2,v3)交叉；边(v1,v5)和边(v2,v3)交叉；边(v1,v5)和边(v3,v4)交叉。(a)(b)图4.1平面图定义4.1设图G=V,E是一个无向图，如果能够把G的所有结点和边画在平面上，且使得任何两条边除此了端点外没有其他的交点，就称G是一个平面图（planargraph）。或称G可嵌入平面S。若G可嵌入平面，则称G是可平面图。画出的无边相交的图称为G的平面嵌入(drawninaplane)。无平面嵌入的图称为非平面图（nonplanar）。Definition:agraphcanbedrawninaplanesothatnoedgescrossexceptatvertices.例4.2对于图4.1(a)中和无向图来说，将此图的图解重新画之后，它不包含任何交叉，如图4.1(b)所示。因此，给定的图是一个平面图。例4.3K1(平凡图)，K2，K3，K4都是平面图，其中，K1，K2，K3本身就已经是平面嵌入，K4的平面嵌入为图4.2中(4)所示。K5－e(K5删除任意一条边)也是平面图，它的平面嵌入可表示为图4.2中(5)。完全二部图K1,n(n≥1),K2,n(n≥2),也都是平面图，其中标准画法画出的K1,n已经是平面嵌入，K2,3的平面嵌入可由图4.2中(6)给出。图4.2中(1)，(2)，(3)分别为K4,K5－e,K2,3的标准画法。v1v3v4v5v2v1v3v4v5v2图4.2可平面化图例4.4图4.3(a)所示的立方体是否可平面化？.（a）(b)(c)图4.3可平面化立方体解：图4.3(a)的图解包括有交叉边。它对它的图解难重新画之后，没有任何两个边是交叉的。因此它是可平面的。见图4.3(b)和（c）.将结点和边画成彩色的可清楚地看出平面嵌入。设G=V,E是能够画于平面上的图解中的无向图，并且设C=v1…v2…v3…v4…v1是图中的任何基本循环。此外，设x=v1…v3和x′=v2…v4是图中的任意两条不交叉的基本路径。在图4.4中，给出了两种可能的结构。显然，当且仅当x和x′或者都在基本循环C的内部，或者都在基本循环C的外部，G才是个非平面图，因为这时基本路径x和x′是相互交叉的。判断一个图是非平面图时，上面的性质甚为有效。图4.4例4.5设有一个电路，它含有两个结点集V1和V2，且21VV=3。用导线把一个集合中的每一个结点，都与另外一个集合中的每一个结点连通，如图所示。试问，是否有可能这样来连线，使得导线相互不交叉？图4.5解：这个问题等价于判断图4.5是否是个平面图。可以看出，给定图中有一个基本循环C=v1v6v3v5v2v4v1，如图4.6(a)所示。试考察三条边(v1,v5),(v2,v6)和(v3,v4)。上述的边中的每一条，或者处于C的内侧，或者处于C的外侧。显然，三条边中至少有两条边必定处于C的同一侧，因此避免不了交叉，如图4.6(b)所示。故给定图是非平面图。(a)(b)图4.6在研究平面图理论中居重要地位的两个图，这就是完全图K5和完全二部图K3,3，它们都不是平面图。V1V2V3V4V1V2V3V4V5V6v1v2v3v4v5v6图4.7还有两个非常显然的事实，用下面定理给出。定理4.1若图G是平面图，则G的任何子图都是平面图。由定理4.1立刻可知，Kn(n≤4)和K1,n(n≥1)的所有子图都是平面图。定理4.2若图G是非平面图，则G的任何母图也都是非平面图。母图：设G=V，E，G'=V'，E'为两个图(同为无向图或同为有向图)，若V'V且E'E，则称G'是G的子图，G为G'的母图推论Kn(n≥5)和K3,n(n≥3)都是非平面图。本推论由K5，K3,3不是平面图及定理4.2得证。还有一个明显的事实也用定理给出。定理4.3设G是平面图，则在G中加平行边或环后所得图还是平面图。本定理说明平行边和环不影响图的平面性，因而在研究一个图是否为平面图时可不考虑平行边和环。4.1.2平面图的面与次数定义4.2设G是一个连通平面图(且已是平面嵌入)，由图中的边所包围的区域称为G的一个面(face)，包围该面的诸边所构成的回路称为这个面的边界(boundary)。例4.5图4.8具有6个结点和9条边，它把平面划分成五个面。其中r1,r2,r3,r4四个面是由回路构成边界，如r1由回路badb所围，r2由回路bdcb所围，,r3可看作从点c开始围绕,r3按反时针方向，得到一个回路cdefec所围。另外还有一个面r5在图形之外，不受边界约束，称作无限面。图4.8规定：面的边界的回路长度称作是该面的度数（degreeofaplane），记为deg(r)。例如图4.8中，deg(r1)=3,deg(r2)=3,deg(r3)=5,deg(r4)=4，deg(r5)=3定理4.4一个有限平面图，面的次数之和等于其边的两倍。证明：因为任何一条边，或者是二个面的公共边，或者在一个面中作为边界被重复计算两次，故面的次数之和等于其边数的两倍。例4.8图中，18)deg(51iir，正好是边数的两倍。4.1.3极大平面图及性质定义4.3设G为简单平面图，若在G的任意不相邻的顶点u，v之间加边(u，v)，所得图为非平面图，则称G为极大平面图。从定义不难看出，K1，K2，K3，K4，,K5-e(K5删除任意一条边)都是极大平面图。还可以容易地证明下面两个定理。定理4.5极大平面图是连通的。定理4.6设G是n(n≥3)阶极大平面图，则G中不可能存在割点和桥。极大平面图的特点由下面定理给出。定理4.7设G为n(n≥3)阶简单连通的平面图，G为极大平面图充分必要条件是：（1）G的每个面的次数均为3.（2）设G有m条边r个面，则3r=2m。（3）设G有n个顶点，m条边和r个面，则m=3n-6，r=2n-4例4.5在图4.9所示的各平面图中，只有(3)是极大平面图。Cr1abr4defr2r3r5图4.94.1.4、极小非平面图定义4.4若在非平面图G中任意删除一条边，所得图为平面图，则称G为极小非平面图。可以验证，K5和K3,3都是极小非平面图。4.2欧拉公式4.2.1欧拉公式及其推广欧拉在研究多面体时发现，多面体的顶点数减去棱数加上面数等于2。后来发现，连通的平面图的阶数，边数，面数之间也有同样的关系。定理4.8(欧拉公式)对于任意的连通的平面图G，有n-m+r=2n，m，r分别为G的顶点数，边数和面数。例如下图中，r=4,n=6,m=8,则n-m+r=6-8+4=2图4.10证对边数m作归纳法。(1)m＝0时，由于G为连通图，所以G只能是平凡图，则有n=1，m=0，r=1，结论成立。r3r2erraabcdfr4r1（2）若m=1,即n=2,m=1,r=1,则n-m+r=2,结论成立。（3）设m＝k(k≥1)时欧拉公式成立。即n'-m'+r'=2。证明当m＝k+1时，结论也成立。对G进行如下讨论。因为G是连通的，在有k条边的连通图上增加一条边，仍为连通图。于是有下面两种情况：①若G是树，则在G中加一条边使G仍为树。见图4.11(a)。此时，G的点数和边数各增加了1，而面数没变。即m=m'+1,n=n'+1，r=r'。由归纳假设可知n'-m'+r'=2n-m+r=(n'+1)-(m'+1)+r'=n'-m'+r'=2②若G不是树，则G中含回路。用一条边连接图上的两个已知点u和v，如图4.11(b)所示。此时，边数和面数都增加了1,而结点数没变。即m=m'+1，n'=n，r'=r-1，由归纳假设有n'-m'+r'=2:n-m+r=n'-(m'+1)-(r'+1)=n'-m'+r'=2结论成立。（a）(b)图4.11欧拉公式中，平面图G的连通性是不可少的。对于非连通的平面图有下面定理成立。欧拉公式常用来判断一个图是非平面图。例4.6证明K3,3是非平面图。证：假设K3,3是平面图。则图中的任何一个回路至少有4条边，作为面的边界的边至少是4r。而在平面图中，任何一条边至多是两个回路的边界。因此有：2m≥4r应用欧拉公式：n-m+r=2得：2m≥4(m-n+2)对于K3,3，m=9,n=6代入上式：18≥4(9-6+2)=20矛盾所以，K3,3不是平面图。同理可证K5不是平面图。uv定理4.9(欧拉公式的推广)对于具有k(k≥2)个连通分支的平面图G，有n-m+r=k+1n，m，r分别为G的顶点数，边数和面数。证设G的连通分支分别为G1，G2，…，Gk，并设Gi的顶点数，边数，面数分别为ni，mi，ri，i=1，2，…，k.由欧拉公式可知:ni-mi+ri=2，i=1，2，…，k(4.1)m=kiim1，n=kiin1，由于每个Gi有一个外部面，而G只有一个外部面，所以G的面数r=kiir1-k+1,于是，对(4.1)的两边同时求和得2k=ki1(ni-mi+ri)=ki1ni-ki1mi+ki1ri=n-m+r+k-1n-m+r=k+1将定理4.9称为欧拉公式的推广。由欧拉公式及其推广可以得到平面图的另外一些性质。4.2.2平面图的边数m与顶点数n的关系定理4.10设G是连通的平面图，且每个面的次数至少为l(l≥3)，则G的边数m与顶点数n有如下关系：m≤2ll(n－2)由定理4.4可知:2m=ri1deg(Ri)≥l·r(4.2):r=2+m-n(4.3)将(4.3)代入(4.2)得2m≥l(2+m-n):m≤2ll(n－2)推论K5与K3,3都不是平面图。证若K5是平面图，由于K5中无环和平行边，所以每个面的次数均大于或等于l≥3，由定理4.10可知边数10应满足10≤233(5-2)=9K5不是平面图。类似地，若K3,3是平面图，由于K3,3中最短圈的长度为l≥4，于是边数9应满足9≤244(6-2)=8K3,3也不是平面图。利用欧拉公式的推广形式容易证明此定理。而对于有k个连通分支的平面图，边数与顶点之间的关系可由下列定理给出。定理4.11设G是有k(k≥2)个连通分支的平面图，各面的次数至少为l(l≥3)，则边数m与顶点数n应有如下关系：m≤2ll(n-k-1)证明略。定理4.12设G是n(n≥3)阶m条边的连通平面图，则m≤3n-6证由于G是连通平面图，又因为n≥3，故对图G中的每个面来说，deg(ri)≥3,因而有：2m=rrrii3)deg(1再由欧拉公式:n-m+r=23n-3m+3r=63n-6=3m-3r≥3m-2m=m即m≤3n-6证毕。定理4.13若G是连通的简单平面图，则5)(G。证明：用反证法。若5)(G，则有6n≤2m，即3n≤m，由定理4.12，有3n≤3n-6,矛盾。4.3平面图的判断虽然欧拉公式有时能用来判定某一个图是非平面图，但是还没有简便的方法可以确定某个图是平面图。4.3.1库拉托夫斯基定理为了讨论平面图的判别法，还需要给出下面两个定义。在图4.12中，给出了两个图解。如图4.12（a）所示，试往图中的一条边上，插入一个新的次数为二的结点，把一条边分解成两条边，则不会改变给定图的平面性。另外，如图4.12（b）所示，把联系于一个次数为二的结点的两条边，合并成一条边，也不会改变给定图的平面性。(a)(b)图4.12定义4.5设G1和G2是两个无向图，如果图G1与G2同构，或通过反复插入或消去2度顶点后是同构的，则称G1与G2是同胚（homeomorphic）。例如：在图4.13中，(1)与K3同胚,(2)与K4同胚。图4.13在具体使用时，常用边压缩方法。定义4.6图G的一个边压缩为：将图G中的两个邻接顶点vi，vj及边(vi,vj)压缩成一个顶点，可用一个新的符号w代替，使