资源描述：
《电子科大图论课件——第6章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1第六章平面图电子科技大学应用数学张先迪2问题：假定有三个仓库x1，x2，x3和三个车站y1，y2，y3。为了便于货物运输，准备在仓库与车站间修筑铁路，如图(a)所示,其中边代表铁路。问是否存在一种使铁路不交叉的路线设计方案，以避免修建立交桥。问题的解答但如果在x3与y1之间也要修一条铁路，则可验证满足要求的方案不存在。x1x2x3y1y2y3(a)x1x2x3y1y2y3?3定义1若图G可画在一个平面上使除顶点外边不交叉，则称G可嵌入平面，或称G为可平面图。可平面图G的边不交叉的一种画法称为G的一个平面嵌入，G的平面嵌入表示的图称为平面图。例1=平面图可平面图§6.1平面图
2、4可平面图不可平面图=不可平面图=5可平面图==可平面图6定义：设G是一个平面图，G将所嵌入的平面划分为若干个区域，每个区域的内部连同边界称为G的面，无界的区域称为外部面或无限面。每个平面图有且仅有一个外部面。设f是G的一个面，构成f的边界的边数（割边计算两次）称为f的次数，记为deg(f)。7例2有5个面：f1，f2，f3，f4，f5（f5为外部面）图不连通，其外部面的次数为5f1f2f3f5f4deg(f1)=1deg(f2)=2deg(f3)=3deg(f4)=6deg(f5)=10相加为22，正好是边数11的2倍8定理1设具有m条边的平面图G的所有面的集合为Ψ,则m2
3、)deg(=åYÎff（1.1）证明任取G的一条边e。若e是两个面的公共边，则在计算面的次数时，e被计算两次。若e不是公共边，则e是G的割边，由面的次数的定义，e也被计算两次。所以所有面的次数之和是边数的2倍，即（1.1）式成立。9证明对ф用归纳法。设ф=k时，（1.2）式成立。定理2（Eulen公式）设G是具有n个点m条边ф个面的连通平面图，则有n–m+ф=2（1.2）当ф=1时，G无圈又连通，从而是树，有n=m+1于是n-m+ф=（m+1）-m+1=210同时n’=n，m’=m-1，ф’=ф-1代入（1.3）式得n-（m-1）+（ф-1）=2即n–m+ф=2当ф=k+1时
4、，此时G至少两个面，从而有圈C。删去C中一条边，记所得之图为G’。并设G’的点数、边数和面数依次为n’,m’和ф’,易知G’仍连通，但只有k个面，由归纳假设有n’-m’+ф’=2（1.3）11证明设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+-=2k(1.4)而=ф+（k-1）（这是因外部面多计算了k-1次）12将它们代入（1.4）式得n–m+ф+k-1=2kn–m+ф=k+1
5、定理4设G是具有n个点m条边的连通平面图,Ψ是G中所有面的集合，若对任意的f∈Ψ均有deg(f)≥l≥3，则)2(2--£nmll(1.5)13证明设G有φ个面，因每个面均有deg(f)≥l，故将上式代入Euler公式n–m+φ=2得22³+-mmnlÞ)2(2--£nmll14推论1设简单可平面图G有n个点m条边,且n≥3，则m≤3n-6（1.6）证明先假定G连通。因G至少有三个点又连通且为简单图，故对G相应的平面图中每个面的次数至少是3。由定理3，取l=3得m≤)2(233--n=3-6n15设G不连通。若G存在至少有三个点的连通分支，因对G的这些分支均满足（1.6）式，
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。16推论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和
7、K3,3是不可平面图。17证明若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是不可平面图。18定理5若G是简单
