《图论4-6 平面图》由会员分享,可在线阅读,更多相关《图论4-6 平面图(12页珍藏版)》请在金锄头文库上搜索。
1、4-6 平面图,重点:掌握欧拉定理及其证明。,一、平面图1、定义4-6.1 如果无向图G=的所有结点和边可以在一个平面上图示出来,而使各边仅在顶点处相交。无向图G称为平面图,否则称G为非平面图。,有些图形从表面看有几条边是相交的,但是不能就此肯定它不是平面图,例如,下面左图表面看有几条边相交,但如把它画成右图,则可看出它是一个平面图。,有些图形不论怎样改画,除去结点外,总有边相交。故是非平面图。,2、面、边界 定义4-6.2:设G是一连通平面图,由图中的边所包围的区域,在区域内既不包含图的结点,也不包含图的边,这样的区域称为G的一个面,包围该面的诸边所构成的回路称为这个面的边界。面r的边界的长
2、度称为该面的次数,记为deg(r)。,定义4-6.3 设图G=是一连通平面图,由图中各边所界定的区域称为平面图的面(regions)。有界的区域称为有界面,无界的区域称为无界面。界定各面的闭的路径称为面的边界(boundary),面r的边界长度称为面r的度(degree)记为deg (r) ,又称为面r的次数 。,例如图,deg(r1)=3deg(r2)=3deg(r3)=5deg(r4)=4deg(r5)=3,deg(r1)+deg(r2)+deg(r3)+deg(r4)+deg(r5)=18,如边是两个面的分界线,该边在两个面的度数中各记1次。如边不是两个面的分界线(称为割边)则该边在该面
3、的度数中重复记了两次,故定理结论成立。,3.定理4-6.1 设G为一有限平面图,面的次数之和等于其边数的两倍。, 证明思路:任一条边或者是两个面的共同边界(贡献2次),或者是一个面的重复边(贡献2次) ,4、欧拉定理 定理4-6.2(欧拉定理) 设G为一平面连通图,v为其顶点数,e为其边数,r 为其面数,那么欧拉公式成立 v e + r = 2,证明 (1)若G为一个孤立结点,则v=1,e=0,r=1,故 v-e+r=2成立。,(2)若G为一个边,即v=2,e=1,r=1,则 v-e+r=2成立。,(3)设G为k条边时,欧拉公式成立,即 vk-ek+rk=2。考察的情况。,因为在k条边的连通图
4、上增加一条边,使它仍为连通图,只有下述两种情况:,加上一个新结点b,b与图上的一点a相连,此时vk和ek两者都增加1,而面数rk没变,故( vk +1)-( ek +1)+ rk = vk-ek+rk=2。,用一条边连接图上的已知两点,此时ek和rk都增加1,结点数vk没变,故 vk -(ek +1)+(rk +1)=vk-ek+rk=2。,例:已知一个平面图中结点数v=10,每个面均由4条边围成,求该平面图的边数和面数。,解:因每个面的次数均为4,则2e=4r,即e=2r,又v=10,代入欧拉公式v-e+r=2有10-2r+r=2解得r=8,则e=2r=16。,说明:这是简单图是平面图的必要
5、条件。,5.定理4-6.3 设G为一简单连通平面图,其顶点数v3,其边数为e,那么 e3v 6, 证明思路:设G的面数为r,当v=3,e=2时上式成立,若e=3,则每一面的次数不小于3,各面次数之和不小于2e,因此 2e3r, r2e/3 代入欧拉公式: 2=v-e+rv-e+ 2e/3 整理后得: e3v 6 本定理的用途:判定某图是非平面图。,例如:K5中e=10,v=5,3v-6=9,从而e3v-6,所以K5不是平面图。,定理4.6.3的条件不是充分的。如K3,3图满足定理4-6.3的条件(v=6,e=9,3v-6=12,e3v-6成立),但K3,3不是平面图。,证明K3,3图不是平面图。,在K3,3中有6个结点9条边,2v-4=26-4=89,与 2v-4e 矛盾,故 K3,3不是平面图。,证明 假设K3,3图是平面图。,在K3,3中任取三个结点,其中必有两个结点不邻接,故每个面的次数都不小于4,由4r2e,re/2,即 v-e+e/2v-e+r=2, v-e/22, 2v- e 4, 2v-4e。,