图论第6章

第六章平面图电子科技大学数学科学学院王也洲[e-mail]定义1若图G可画在一个平面上使除顶点外边不交叉，则称G可嵌入平面，或称G为可平面图。可平面图G的边不交叉的一种画法称为G的一个平面嵌入，G的平面嵌入表示的图称为平面图。例1=平面图可平面图§6.1平面图可平面图不可平面图=不可平面图可平面图==可平面图定义：设G是一个平面图，G将所嵌入的平面划分为若干个区域，每个区域的内部连同边界称为G的面，无界的区域称为外部面或无限面。每个平面图有且仅有一个外部面。设f是G的一个面，构成f的边界的边数（割边计算两次）称为f的次数，记为deg(f)。6例2有5个面：f1，f2，f3，f4，f5（f5为外部面）图不连通，其外部面的次数为5f1f2f3f5f4deg(f1)=1deg(f2)=2deg(f3)=3deg(f4)=6deg(f5)=10相加为22，正好是边数11的2倍定理1设具有m条边的平面图G的所有面的集合为Ψ,则m2)deg(=Yff（1.1）证明任取G的一条边e。若e是两个面的公共边，则在计算面的次数时，e被计算两次。若e不是公共边，则e是G的割边，由面的次数的定义，e也被计算两次。所以所有面的次数之和是边数的2倍，即（1.1）式成立。证明对ф用归纳法。设=k时，（1.2）式成立。定理2（Euler公式）设G是具有n个点m条边ф个面的连通平面图，则有n–m+ф=2（1.2）当ф=1时，G无圈又连通，从而是树，有n=m+1于是n-m+ф=（m+1）-m+1=2同时n’=n，m’=m-1，ф’=ф-1代入（1.3）式得n-（m-1）+（ф-1）=2即n–m+ф=2当ф=k+1时，此时G至少两个面，从而有圈C。删去C中一条边，记所得之图为G’。并设G’的点数、边数和面数依次为n’,m’和ф’,易知G’仍连通，但只有k个面，由归纳假设有n’-m’+ф’=2（1.3）证明设G的k个连通分支分别为G1,G2,…,Gk,对每个Gi用欧拉公式可得：ni–mi+фi=2，i=1，2，…，k其中ni，mi，фi分别为Gi的点数、边数和面数，将k个等式两边相加得定理3设G是具有ф个面k个连通分支的平面图，则n-m+ф=k+1=kiin1=kiim1=kii1+-=2k(1.4)而,1nnkii==mmkii==1=kii1=ф+（k-1）（这是因外部面多计算了k-1次）将它们代入（1.4）式得n–m+ф+k-1=2kn–m+ф=k+1定理4设G是具有n个点m条边的连通平面图,Ψ是G中所有面的集合，若对任意的f∈Ψ均有deg(f)≥l≥3，则)2(2--nmll(1.5)证明设G有φ个面，因每个面均有deg(f)≥l，故将上式代入Euler公式n–m+φ=2得22+-mmnl)2(2--nmllY=fmfl2)deg()1.1(ml2推论1设简单可平面图G有n个点m条边，且n≥3，则m≤3n-6（1.6）证明先假定G连通。因G至少有三个点又连通且为简单图，故对G相应的平面图中每个面的次数至少是3。由定理3，取l=3得m≤)2(233--n=3－6n设G不连通。若G存在至少有三个点的连通分支，因对G的这些分支均满足（1.6）式，将各不等式相加也得类似不等式，设为m1≤3n1-6。设G没有多于两个点的连通分支。此时m≤n。因n≥3时，n≤3n-6，所以有m≤3n-6。再设G的所有少于3个点的连通分支的总边数为m2，总点数为n2。此时有m2≤n2≤3n2，于是m1+m2≤3(n1+n2)-6，从而有m≤3n-6。推论2设G是具有n个点m条边的连通平面图，若G中所有面均由长度为l的圈围成，则m(l-2)=l(n-2)(1.7）证明只需在定理4的证明中将所有不等号改为等号即可得(1.7)式。例3在右图所示的图中，m=12，n=8，l=4有12×(4-2)=4×(8-2)，满足（1.7）式。例4证明K5和K3,3是不可平面图。证明若K5是可平面图，则因K5是至少三个点的简单图，由推论1，K5应满足m≤3n-6。而K5中m=10，n=5，代入不等式(1.6)得10≤3×5–6=9矛盾，所以K5是不可平面图。对K3,3，因K3,3没有长小于4的圈，所以若K3,3是可平面图，则对其相应的平面图中每个面的次数至少为4。由定理4，K3,3应满足l=4的不等式（1.5）即m≤（-2）=2-4244-nn而K3,3中m=9，n=6，代入上式得:9≤2×6-4=8矛盾，所以K3,3是不可平面图。定理5若G是简单平面图，则δ≤5.证明对点数n=1，2，直接验证可知结论成立。设n≥3，若δ≥6，则=)(2)(6GVvdnmnm＞3n-6这与定理4的推论1矛盾。所以δ≤5。1.若图G能画在曲面S上使它的边仅在端点相交，则称图G可嵌入曲面S；图G的这样一种画法（若存在的话）称为G的一个S嵌入。AAAACCBBK5不可嵌入平面，但能嵌入环面，也存在不可嵌入环面的图。平面嵌入概念的推广例下图表示了K5的环面嵌入，其中矩形的两对对边相等同。2.可以证明对每个曲面S总存在不可嵌入S的图。另一方面每个图又存在可以嵌入的某个可定向的曲面。3.一个图可嵌入平面当且仅当它可嵌入球面。PzyOx图6-9简证将球面S放在一个平面P上，设切点为O，过O点作垂直于P的直线，此直线与S的交点设为z。作映射PzSf-:定义f（x）=y当且仅当点z，x，y共线。这样的映射f（如图6-9所示）便称为球极平面射影。通过球极平面射影可将嵌入球面S的图映射为嵌入平面的图，反之亦然。4.如果将一个有n个顶点，m条棱和φ个面的凸多面体的顶点作为顶点，棱作为边，则这个多面体可视为一个图G，很明显G可嵌入球面，从而可嵌入平面而得到一个连通的平面图。因而由定理2，凸多面体的顶点数，棱数与面数也满足n-m+φ=2。这个公式也称为欧拉公式。定理6（Platonic）存在且只存在5种正多面体：正四面体、正方体、正八面体、正十二面体和正二十面体。证明任取一个正φ面体A，设A有n个顶点，m条棱。将A嵌入平面记所得的平面图为G。易知G是一个每个面的次数均相同（设为l）的r度简单正则图。从而有φl=2m，nr=2m，l≥3，r≥3将上两式代入Euler公式n-m+φ=2得22=+-lnrnrn2ln–lnr+2nr=4ln(2l–lr+2r)=4ln=4l(2l–lr+2r)-1(1.9)2nrm=lnrlm=2,Φ=(1.8)因n和l均为正，由（1.9）式得2l–lr+2r＞02(l+r)＞lr(1.10)这样我们得到不等式组+33)(2rllrrl此不等式组的整数解恰为5组。将这5组解分别代入（1.9）和(1.8)式可求得相应的φ值，其结果见下表。n=4l(2l–lr+2r)-1(1.9)序号lrnmф相应的正多面体133464正四面体2348126正方体335203012正十二面体4436128正八面体553123020正二十面体正八面体正二十面体正八面体和正二十面体的平面表示为定理7一个连通平面图是2连通的，当且仅当它的每个面的边界是圈。证明不失一般性，假设G没有环，那么G没有割边，也没有割点。所以，每个面的边界一定是一条闭迹。“必要性”设C是G的任意面的一个边界，我们证明，它一定为圈。若不然，设C是G的某面的边界，但它不是圈。因C是一条闭迹且不是圈，因此，C中存在子圈。设该子圈是W1。因C是某面的边界，所以W1与C的关系可以表示为如图的形式：vvj-1v1v2vi-1vi+1vnW1容易知道：v为G的割点。矛盾！“充分性”设平面图G的每个面的边界均为圈。此时删去G中任意一个点不破坏G的连通性，这表明G是2连通的。推论若一个平面图是2连通的，则它的每条边恰在两个面的边界上。§6.2一些特殊平面图及平面图的对偶图一、一些特殊平面图定义1设G是简单可平面图，如果G是Ki(1≦i≦4),或者在G的任意两个不相邻的顶点间添加一条边后，得到的图均是不可平面图，则称G是极大可平面图。极大可平面图的平面嵌入称为极大平面图。例1极大可平面图极大可平面图非极大可平面图引理设G是极大平面图，则G必连通；若G的点数n≥3，则G无割边。证明若G不连通，则G至少存在两个连通分支G1与G2。显然G1与G2也是平面图。将G2画在G1的外部面内，并分别在G1与G2的外部面上各取一个点u和v。很明显，u与v不相邻。易知G*也是平面图，这与G是极大平面图矛盾，所以G连通。连接u和v，记所得的图为G*。uvG1G2因n≥3，所以G1与G2中必有一个至少含两个点，不妨设G2至少含两个点。设n≥3。若G存在割边uv，则G-uv不连通，恰有两个连通分支G1与G2。设f是G1中含点u的面，将G2画在f内。vuG1G2tuvG1G2f因G2是简单图，故在G2的外部面上存在不等于v的点t。在G中连接不相邻点u和t，记所得的图为G*，易知G*也是平面图，这与G是极大平面图矛盾。所以G不含割边。定理8设G是至少有3个顶点的平面图。则G是极大平面图的充分必要条件为G中各面的次数均为3且为简单图。证明充分性显然，下证必要性。设G是极大平面图。由定义知，G是简单图。又因G至少有3个顶点，所以G中各面次数至少为3。这样，若结论不成立，则G中必存在一个面f，满足deg(f)≥4。由引理知，G无割边，所以围成f的边界所成的回路是一个圈，不妨设为v1v2…vtv1，其中t≥4。若v1与v3不相邻，则在f内连接v1与v3不破坏G的平面性，这与G为极大平面图矛盾。所以v1与v3必相邻。v1v2fv3v4因面f内无边，故边v1v3必在f外。同理，v2与v4必相邻并且边v2v4也在f外。这样边v1v3与边v2v4必相交(如图所示)，这就与G是平面图矛盾。所以G中各面次数只能为3。推论设G是一个有n个点m条边ф个面的极大平面图，且n≥3，则（1）m=3n-6；（2）ф=2n-4。证明留作习题。推论表明对一个极大平面图G，当其点数n给定时，G的边数和面数也就确定了，从而G的结构框架也大体确定了。例如，当n=4时，G为K4；当n=6时，G为正八面体；当n=9时，G有21条边14个面，其中一个的结构如图所示：当n=12时，G有30条边20个面，此时，其中的两个G一个为正二十面体，另一个如图右所示。定义2如果在不可平面图G中任意删去一条边所得的图为可平面图，则称G为极小不可平面图。例如K5和K3,3。定义3若一个可平面图存在一个所有顶点均在同一个面的平面嵌入，则称该图为外可平面图。外可平面图的任一外平面嵌入（即所有顶点均在同一个面的嵌入）称为外平面图。565656（a）（b）（c）111222343434例下图给出了一个外可平面图(a)及两种外平面嵌入(b)和(c)。注：对外可平面图G来说，一定存在一种外平面嵌入，使得G的顶点均在外部面的边界上。这由球极投影法可以说明。定义4设G是一个简单外可平面图，若在G中任意不邻接顶点间添上一条边后，G成为非外可平面图，则称G是极大外可平面图。极大外可平面图的外平面嵌入，称为极大外平面图。极大外平面图的外部面的周界是由多边形组成，内部面均有三角形围成。极大外平面图例如定理9设G是一个有n(n≥3)个点，且所有点均在外部面上的极大外平面图，则G有n-2个内部面。证明对G的阶数作数学归纳。当n=3时，G是三角形，显然只有一个内部面；设当n=k时，结论成立。当n=k+1时，首先，注意到G必有一个2度顶点u在G的外部面上。考虑G1=G-v。由归纳假设，G1有k-2个内部面。这样G有k-1个内部面。于是定理得证。定理10设G是一个有n(n≥3)个点，且所有点均在外部面上的外平面图，则G是极大外平面图，当且仅当其外部面的边界是圈，内部面是三角形。证明先证明必要性。(1)证明G的外部面的边界是圈。容易知道：G的外部面边界一定为闭迹，否则，G不能为极大外平面图。设W=v1v2…vnv1是G的外部面边界。若W不是圈，则存在i与j,使vi=vj=v。此时，G如图所示：vi-1v1vnv2