第一节平面图演示文稿

第一节平面图演示文稿目前一页\总数十页\编于十七点（优选）第一节平面图目前二页\总数十页\编于十七点定义2(平面图的面,边界和度数).

设G是一个平面图，由G中的边所包围的区域，在区域内既不包含G的结点，也不包含G的边，这样的区域称为G的一个面。有界区域称为内部面，无界区域称为外部面。包围面的长度最短的闭链称为该面的边界。面的边界的长度称为该面的度数。目前三页\总数十页\编于十七点例2指出下图所示平面图的面、面的边界及面的度数。1234567e6e1e2e3e4e5e7e8e10e9f1f4f3f2f5目前四页\总数十页\编于十七点解:面f1,其边界1e15e24e43e72e101,d(f1)=5.

面f2,其边界1e102e87e91,d(f2)=3.

面f3,其边界2e73e67e82,d(f3)=3.

面f4,其边界3e44e57e63,d(f4)=3.

外部面f5,

其边界1e15e24e36e34e57e91,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条边的连通的平面简单图，其中v3，则e3v-6。证明:由于G是简单图,则G中无环和无平行边.因此G的任何面的度数至少为3.故2e=d(f)3r(1)

其中r为G的面数.由欧拉公式v-e+r=2所以r=2-v+e,代入(1)中有:2e3(2-v+e)即e3v-6。目前八页\总数十页\编于十七点推论2设G是带v个顶点，e条边的连通的平面简单图，其中v3且没有长度为3的圈，则e2v-4。证明:因为图G中没有长度为3的圈,从而G的每个面的度数至少为4.因此有2e=d(f)4r(1)其中r为G的面数.由欧拉公式v-e+r=2所以r=2-v+e,代入(1)中有:2e4(2-v+e)即e2v-4。例3K5和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,