第一节平面图课件.ppt

《第一节平面图课件.ppt》由会员分享，可在线阅读，更多相关《第一节平面图课件.ppt（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一节平面图第1页，此课件共12页哦定理定理1 1 图图G G可嵌入球面可嵌入球面图图G G可嵌入平面。可嵌入平面。例例1 Q1 Q3 3是否可平面性？是否可平面性？第2页，此课件共12页哦定义定义2(2(平面图的面平面图的面,边界和度数边界和度数).).设设G G是一个平面图，由是一个平面图，由G G中的边所包围的区域中的边所包围的区域，在区域内既不包含，在区域内既不包含G G的结点，也不包含的结点，也不包含G G的边的边，这样的区域称为，这样的区域称为G G的一个面的一个面。有界区域称为有界区域称为内部面内部面，无界区域称为，无界区域称为外部面外部面。包围面的长度。包围面的长度最短的闭链称

2、为最短的闭链称为该面的边界该面的边界。面的边界的长度。面的边界的长度称为称为该面的度数该面的度数。第3页，此课件共12页哦例例2 2 指出下图所示平面图的面、面的边界及面的度指出下图所示平面图的面、面的边界及面的度数。数。1234567e6e1e2e3e4e5e7e8e10e9f1f4f3f2f5第4页，此课件共12页哦解解:面面f f1 1,其边界其边界1e1e1 15e5e2 24e4e4 43e3e7 72e2e10101,d(f1,d(f1 1)=5.)=5.面面f f2 2,其边界其边界1e1e10102e2e8 87e7e9 91,d(f1,d(f2 2)=3.)=3.面面f f3

3、 3,其边界其边界2e2e7 73e3e6 67e7e8 82,d(f2,d(f3 3)=3.)=3.面面f f4 4,其边界其边界3e3e4 44e4e5 57e7e6 63,d(f3,d(f4 4)=3.)=3.外部面外部面f f5 5,其边界其边界1e1e1 15e5e2 24e4e3 36e6e3 34 e4 e5 57e7e9 91,d(f1,d(f5 5)=6.)=6.第5页，此课件共12页哦定理定理2 2 对任何平面图对任何平面图G G，面的度数之和面的度数之和是是边数的二倍边数的二倍。证明证明:对内部面而言对内部面而言,因为其任何一条非因为其任何一条非割割边同时在两个面中边同时

4、在两个面中,故每增加一条边图的度数必增加故每增加一条边图的度数必增加2.2.对外部面的边界对外部面的边界,若某条边若某条边不同时在两个面中不同时在两个面中,边必为割边边必为割边,由于边界是闭链由于边界是闭链,则该边也则该边也为图的度数贡献为图的度数贡献2.2.从而结论成立从而结论成立.定理定理3 3 设设G G是带是带v v个顶点，个顶点，e e条边，条边，r r个面的连通的平面图个面的连通的平面图，则，则 v-e+r=2v-e+r=2。（欧拉公式）。（欧拉公式）证明证明:(1):(1)当当n=e=1n=e=1时时,如下图如下图,结论显然成立结论显然成立.v=2,e=1,r=1v=1,e=1,

5、r=2第6页，此课件共12页哦(2)下用数学归纳法证明下用数学归纳法证明.假设公式对假设公式对n条边的图成立条边的图成立.设设G有有n+1条边条边.若若G不含圈不含圈,任取任取一点一点x,从结点从结点x开始沿路行走开始沿路行走.因因G不含圈不含圈,所以每次沿一边总所以每次沿一边总能达到一个新结点能达到一个新结点,最后会达到一个度数为最后会达到一个度数为1的结点的结点,不妨设为不妨设为a,在结点在结点a不能再继续前进不能再继续前进.删除结点删除结点a及其关联的边得图及其关联的边得图G,G含有含有n条边条边.由假设公式对由假设公式对G成立成立,而而G比比G多一个结点多一个结点和一条边和一条边,且且

6、G与与G面数相同面数相同,故公式也适合于故公式也适合于G.若若G含有圈含有圈C,设设y是圈是圈C上的一边上的一边,则边则边y一定是两个不同一定是两个不同面的边界的一部分面的边界的一部分.删除边删除边y得图得图G,则则G有有n条边条边.由假设公由假设公式对式对G成立而成立而G比比G多一边和多一面多一边和多一面,G与与G得顶点数相同得顶点数相同.故公式也成立故公式也成立.第7页，此课件共12页哦推论推论1 1 设设G G是带是带v v个顶点，个顶点，e e条边的连通的平面简条边的连通的平面简单图，其中单图，其中v v 3 3，则，则e e 3 3v-6v-6。证明证明:由于由于G G是简单图是简单

7、图,则则G G中无环和无平行边中无环和无平行边.因此因此G G的任何面的度数至少为的任何面的度数至少为3.3.故故2e=2e=d(f)d(f)3r (1)3r (1)其中其中r r为为G G的面数的面数.由欧拉公式由欧拉公式v-e+r=2v-e+r=2所以所以r=2-v+e,r=2-v+e,代入代入(1)(1)中有中有:2e2e 3(3(2-v+e2-v+e)即即e e 3 3v-6v-6。第8页，此课件共12页哦推论推论2 2 设设G G是带是带v v个顶点，个顶点，e e条边的连通的平面简单图，其中条边的连通的平面简单图，其中v v 3 3且且没有长度为没有长度为3 3的圈，则的圈，则e

8、e 2 2v-4v-4。证明证明:因为图因为图G G中没有长度为中没有长度为3 3的圈的圈,从而从而G G的每个面的度数至少的每个面的度数至少为为4.4.因此有因此有2e=2e=d(f)d(f)4r (1)4r (1)其中其中r r为为G G的面数的面数.由欧拉公式由欧拉公式v-e+r=2v-e+r=2所以所以r=2-v+e,r=2-v+e,代入代入(1)(1)中有中有:2e2e 4(4(2-v+e2-v+e)即即e e 2 2v-4v-4。例例3 K3 K5 5和和K K3.33.3都是非平面图。都是非平面图。解解:图图K K5 5有有5 5个顶点个顶点1010条边条边,而而3 3*5-6=

9、9,5-6=9,即即109,109,由由第9页，此课件共12页哦推论推论1 1知知,K,K5 5是非平面图是非平面图.显然显然K K3,33,3没有长度为没有长度为3 3的圈的圈,且有且有6 6个顶点个顶点9 9条边条边,因而因而9292*6-4,6-4,由推论由推论2 2知知K K3,33,3是非平面图是非平面图.推论推论3 3 设设G G是带是带v v个顶点，个顶点，e e条边，条边，r r个面的平面图，则个面的平面图，则 v-v-e+r=1+we+r=1+w。其中。其中w w为为G G的连通分支数。的连通分支数。证明证明:由欧拉公式有由欧拉公式有:v:vi i-e-ei i+r+ri i

10、=2(i=1,2,=2(i=1,2,w),w)从而有从而有 v vi i-e ei i+r ri i=2w=2w又又 v vi i=v,=v,e ei i=e,=e,r ri i=r+(w-1)(=r+(w-1)(外部面被重外部面被重复计算了复计算了w-1w-1次次.).).所以有所以有:V-e+r+(w-1)=2wV-e+r+(w-1)=2w整理即得整理即得:v-e+r=1+w.:v-e+r=1+w.第10页，此课件共12页哦推论推论4 4 设设G G是任意平面简单图，则是任意平面简单图，则（G G）5 5。证明证明:设设G G有有v v个顶点个顶点e e条边条边.若若e e 6,6,结论显

11、然成立结论显然成立;若若e6,e6,假设假设G G的每个顶点的度数的每个顶点的度数 6,6,则由推论则由推论1,1,有有6v 6v 2e 2e 6v-126v-12矛盾矛盾,所以所以（G G）5.5.例例4 4平面上有平面上有n n个顶点，其中任两个点之间的距离至少为个顶点，其中任两个点之间的距离至少为1 1，证明，证明在这在这n n个点中距离恰好为个点中距离恰好为1 1的的点对数至多是的的点对数至多是3n-63n-6。证明证明:首先建立图首先建立图G=,G=,其中其中V V就取平面上给定的就取平面上给定的n n个点个点(位置位置相同相同),),当两个顶点之间的距离为当两个顶点之间的距离为1

12、1时时,两顶点之间用一条直线两顶点之间用一条直线段连接段连接,显然图显然图G G是一个是一个n n阶简单图阶简单图.第11页，此课件共12页哦 由推论由推论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)axby(b)第12页，此课件共12页哦