资源描述：
《图论讲义第7章-平面图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第七章平面图§7.1平面图的概念定义7.1.1如果图G能画在曲面S上，使得任意两边互不交叉，则称G可嵌入曲面S。若图G可嵌入平面，则称G是可平面图或平面图，画出的无交叉边的图形称为图G的平面嵌入。例如，下面是三个平面图及其平面嵌入。根据定义，下列定理是显然的。定理7.1.1若图G是平面图，则G的任何子图都是平面图。定理7.1.2若图G是非平面图，则G的任何母图都是非平面图。定理7.1.3若图G是平面图,则在G中添加重边或环边后所得之图仍是平面图。注：由以上定理知(1)Kn(n≤4)和K1,n(n≥1)及其所有子图都是平面图。(2)环边和重边不影响图的平面性
2、。故以下讨论平面性时总假定图G是简单图。定义7.1.2设图G是平面图(已平面嵌入)，G的边将平面划分出的若干区域都称为图G的面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为该面的次数(割边按两次计)，面R的次数记为deg(R)。定理7.1.4平面图G中所有面的次数之和等于G的边数的两倍，即r∑deg(RGi)=2().εi=1其中R1,R2,…,Rr是G的所有面。证明：对G的任何一条边e，若e是两个面Ri和Rj的公共边界，则在计算Ri和Rj的次数时，e各提供了1；若e只是某一个
3、面的边界，则在计算该面的次数时，e提供了2。可见每条边在计算总次数时，都提供2。因而结论成立。1定义7.1.3设G为简单平面图，若在G的任意不相邻的顶点u,v之间加边uv后，所得之图成为非平面图，则称G是极大平面图。易见K1,K2,K3,K4,K5–e都是极大平面图。定义7.1.4若非平面图G任意删除一条边后，所得之图都是平面图，则称G为极小非平面图。容易证明下列定理定理7.1.5极大平面图是连通的。定理7.1.6n阶（n≥3）极大平面图中没有割边和割点。§7.2欧拉公式定理7.2.1（欧拉公式）设G是连通的平面图，n,m,r分别是其顶点数、边数和面数，则
4、n–m+r=2。证明：对边数m作数学归纳法。当m=0时，因G是连通图，所以G只能是平凡图，结论显然成立。假设当m=k时，结论成立。下面证明m=k+1的情况。若G是树，则G至少有两片树叶。设v是G的一片树叶。令G′=G−v，则G′仍是连通图,且G′的边数m′=m−1=k,由归纳假设知,n′–m′+r′=2,而n′=n−1,r′=r,于是n–m+r=(n′+1)–(m′+1)+r′=n′–m′+r′=2。若G不是树，则G中含有圈。设边e在G的某个圈上。令G′=G−e，则G′仍是连通图，且G′的边数m′=m−1=k，由归纳假设知n′–m′+r′=2,而n′=n,
5、r′=r−1，于是n–m+r=n′–(m′+1)+(r′+1)=n′–m′+r′=2。证毕。定理7.2.2（欧拉公式的推广形式）对于具有w(w≥1)个连通分支的平面图G,有n–m+r=w+1。其中n,m,r分别是其顶点数、边数和面数。证明：设G的连通分支分别为G1,G2,…,Gw，并设Gi的顶点数、边数和面数分别为ni,mi,ri。由欧拉公式可知2nmr−+=2,(i=1,2,"w).iiiww易知mm==∑∑ii,.nn由于的每个分支有一个外部面而只有一个外部面G,G,ii==11w故的面数Grr=−∑iw+1,于是i=1wwww2(wn=−∑∑iiim
6、+rnmr)=−+=i∑i∑in−m+r+w−1ii==11i=1i=1整理即得结论.证毕.定理7.2.3设G是连通的平面图，且每个面的次数至少为l(l≥3)，则G的边数m与顶点数n有如下关系：lmn≤(2−).l−2证明：由定理7.1.4可知r2dmR=≥∑eg(i)l⋅ri=1由欧拉公式可知rm=+−2.n将此式代入上式,得2m≥+−lm(2)n,整理便得结论。证毕。推论7.2.1K和K都不是平面图。53,3证明：若K是平面图，由于K中无环边和重边，故每个面的次数至少为3，553而K的边数为10。由定理7.2.3，应有10≤(52),−=9这是不可能的
7、。因532−此K不是平面图。5若K是平面图，由于K中最短圈的长度为4，故每个面的次数至少为3,33,344，而K的边数为9。由定理7.2.3，应有9(≤6,−=2)8这是不可能的。3,342−因此K不是平面图。证毕。3,3推论7.2.2Kn(n≥5)和K3,n(n≥3)都不是平面图。证明：由定理7.1.2和推论7.2.1立即可知。推论7.2.3K5和K3,3都是极小非平面图。由推论7.2.1和极小非平面图的定义容易验证。定理7.2.4设G是具有w(w≥1)个连通分支的平面图,各面的次数至少为l(l≥3)，则G的边数m与顶点数n有如下关系：lmn≤(1−−w
8、).l−2证明：利用欧拉公式的推广形式(定理7.2.2)，与上一定
