平面图.ppt

第四章 平面图第一节 平面图定义1 如果图G能示画在曲面S上且使得它的边仅在端点处相交，则称G可嵌入曲面S如果G可嵌入平面上，则称G是可平面图，已经嵌入平面上的图 称为G的平面表示可平面图G与G的平面表示 同构，都简称为平面图球极投影)定理1 图G可嵌入球面图G可嵌入平面例1 Q3是否可平面性？定义2 (平面图的面,边界和度数). 设G是一个平面图，由G中的边所包围的区域 ，在区域内既不包含G的结点，也不包含G的边 ，这样的区域称为G的一个面有界区域称为 内部面，无界区域称为外部面包围面的长度 最短的闭链称为该面的边界面的边界的长度 称为该面的度数例2 指出下图所示平面图的面、面的边界及 面的度数123456 7e6e1e2 e3e4e5e7e8e10e9f1f4f3 f2f5解:面f1,其边界1e15e24e43e72e101,d(f1)=5.面f2,其边界1e102e87e91,d(f2)=3.面f3,其边界2e73e67e82,d(f3)=3.面f4,其边界3e44e57e63,d(f4)=3.外部面f5,其边界1e15e24e36e34 e57e91,d(f5)=6.定理2 对任何平面图G，面的度数之和是边数的二倍。

证明:对内部面而言,因为其任何一条非割边同时在两个 面中,故每增加一条边图的度数必增加2.对外部面的边 界,若某条边不同时在两个面中, 边必为割边,由于边界 是闭链,则该边也为图的度数贡献2.从而结论成立.定理3 设G是带v个顶点，e条边，r个面的连通的平面 图，则 v-e+r=2欧拉公式）证明:(1)当n=e=1时,如下图,结论显然成立.v=2,e=1,r=1v=1,e=1,r=2(2)下用数学归纳法证明.假设公式对n条边的图成立.设G有n+1条边.若G不含 圈,任取一点x,从结点x开始沿路行走.因G不含圈,所以 每次沿一边总能达到一个新结点,最后会达到一个度数 为1的结点,不妨设为a,在结点a不能再继续前进.删除结 点a及其关联的边得图G’,G’含有n条边.由假设公式对 G’成立,而G比G’多一个结点和一条边,且G与G’面数相 同,故公式也适合于G.若G含有圈C,设y是圈C上的一边,则边y一定是两个 不同面的边界的一部分.删除边y得图G’,则G’有n条边. 由假设公式对G’成立而G比G’多一边和多一面,G与G’ 得顶点数相同.故公式也成立.推论1 设G是带v个顶点，e条边的连通的平面简 单图，其中v3，则e3v-6。

证明:由于G是简单图,则G中无环和无平行边.因此 G的任何面的度数至少为3.故 2e=d(f)3r (1)其中r为G的面数.由欧拉公式 v-e+r=2 所以r=2-v+e,代入(1)中有: 2e3(2-v+e) 即e3v-6推论2 设G是带v个顶点，e条边的连通的平面简单图，其 中v3且没有长度为3的圈，则e2v-4证明:因为图G中没有长度为3的圈,从而G的每个面的度数 至少为4.因此有2e=d(f)4r (1) 其中r为G的面数.由欧拉公式 v-e+r=2 所以r=2-v+e,代入(1)中有: 2e4(2-v+e) 即e2v-4例3 K5和K3.3都是非平面图解:图K5有5个顶点10条边,而3*5-6=9,即10>9,由推论1知,K5是非平面图.显然K3,3没有长度为3的圈,且有6个顶点9条边,因 而9>2*6-4,由推论2知K3,3是非平面图. 推论3 设G是带v个顶点，e条边，r个面的平面图， 则 v- e+ r=1+w其中w为G的连通分支数 证明:由欧拉公式有: vi- ei+ ri=2(i=1,2,…,w) 从而有  vi-  ei+  ri =2w 又 vi=v,  ei=e,  ri =r+(w-1)(外部面被重 复计算了w-1次.).所以有: V-e+r+(w-1)=2w 整理即得: v- e+ r=1+w.推论4 设G是任意平面简单图，则（G）5。

证明:设G有v个顶点e条边.若e6,结论显然成立;若e>6, 假设G的每个顶点的度数6,则由推论1,有6v 2e 6v-12矛盾,所以（G）5.例4平面上有n个顶点，其中任两个点之间的距离至少为1 ，证明在这n个点中距离恰好为1的的点对数至多是3n- 6证明:首先建立图G=,其中V就取平面上给定的n个点 (位置相同),当两个顶点之间的距离为1时,两顶点之间 用一条直线段连接,显然图G是一个n阶简单图.由推论1,只要证明G为一平面图时即知结论成立.反设G中存在两条不同的边{a,b}和{x,y}相交于非端点 处o,如下图(a)所示,其夹角为(0<  <).若 =,这时如下图(b),显然存在两点距离小于1,与已知 矛盾,从而0<  <.由于a到b的距离为1,x到y的距离为1, 因此a,b,x,y中至少有两个点,从交点o到这两点的距离不 超过1/2,不妨设为a,x,则点a与x之间的距离小于1,与已知 矛盾,所以G中的边除端点外不再有其它交点,即G为平面 图.再据推论1,知结论成立.ayxbo (a)axb y(b)。