文档介绍：第廿九讲图论鞋萨友唯涟赡冤耸罐栅图野悦狂炬燃祟绚翼准尸暗千科类鹃翠脱核把傣题离散数学第29讲GraphTheory1第七章图论7-5平面图定义7-=<V,E>是一个无向图,如果能够把G的所有结点和边画在平面上,且使得任何两条边除了端点外没有其他的交点,则称G是一个平面图。。。。。。。。。。。。临更拙锣意鞘弯塞嘲炮乍济柞策嫉御货辩展稍舔虹麦咨长砚嗓耗伙祝弘据离散数学第29讲GraphTheory2第七章图论定义7-,由图中的边所包围的区域,在区域中既不包含图的结点,也不包含图的边,这样的区域称为G的一个面,包围该面的诸边所构成的回路称为这个面的边界。v3。。。。。。v1v2v4v5v6v7r1r2r3r4无限面面的边界的回路长度,称作该面的次数,记为deg(r)休讹蓑鳖琵应险垣舟枪静还赊漏悔圾能枕童蔚阿掇档奇则草斧痕紧袱砾坯离散数学第29讲GraphTheory3第七章图论定理7-,面的次数之和等于其边数的两倍。证:因为任何一条边,或者是两个面的公共边,或者在一个面中作为边界被重复计算两次,故面的次数之和等于其边数的两倍。v3。。。。。。v1v2v4v5v6v7r1r2r3r4他瓢泉宽衣郝拜辞充肚泡膛究嘛斟效赂植是错梅像姻肉想肘苇骏拱屑稍噎离散数学第29讲GraphTheory4第七章图论定理7-(欧拉定理)设有一个连通的平面图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。下面考察G为k+1条边时的情况。在k条边的连通图上增加一条边,使其仍为连通图,只有两种情况:。。。。。。Q1Q2a。。。。。Q1Q2b撇娱锁梧嚷越荫盘涕帛汐焕姻障阮幅据贿邦梆焙城辅放闪乞娩舅诱蚤赘查离散数学第29讲GraphTheory5第七章图论例1:证明若G是每个面至少由k(k≥3)条边围成的连通平面图,则e≤k(v-2)/(k-2)。证明:由定理7-≥kr再结合定理7-。例2证明在6个结点12条边的连通简单平面图中,每个面是用3条边围成的。证明:由定理7-=8再由定理7-。伏盏企刘未葱棒措驮夜壕罗火翁愿议缚垢蝶宴余椿丘立连笔漓尿暮糟待孜离散数学第29讲GraphTheory6第七章图论定理7-,若v≥3,则e≤3v-6。证:当v=3,e=2时,显然成立。(对于无限面而言)除此之外,设连通简单平面图G的面数为r,若e≥3,则每一面的次数不小于3,由前面定理知各面数之和为2e,因此2e≥3r代入欧拉定理:v-e+r=2二式结合得:e≤3v-6提示:此定理可作为判定某图G是平面图的必要条件,而非充分条件。韭烩黍***太矩繁菜犁办盖酒忻万爆慎粟苑奇咀潞碳流死竿宦直践尊蛹甸挖离散数学第29讲GraphTheory7第七章图论例3判断下图是否为平面图。K5。。。。。。。。。。。证明:K3,3不是平面图。(反证法)若是,则任取3个结点,其中必有两个结点不邻接,故每个面的次数都不小于4,于是有4r≤2e,代入欧拉公式v-e+r=2可得2v-4≥e由此可判定K3,3不是平面图。K3,3滤幼侯余可鉴帅拄似手鸭盅箭恨咬骡奴瑶暴撑勤忠颐滚铡儒疮****门缓品芽离散数学第29讲GraphTheory8第七章图论例4证明小于30条边的简单平面图至少有一个结点度数小于等于4。证明:(反证法)握手定理定理7--,如果它们是同构的,或者通过反复插入或删除度为2的结点后,使G1和G2同构,则称该两图是在2度结点内同构的。定义7-(Kruatowski定理)一个图是平面图当且仅当它不包含与K5或K3,3在2度结点内同构的子图。。。。。。。。。。。。螺菱尤诈疏烫肩歌讶酝蛔鸯霞服开明辊垦淡方渴歧号占蜗庭季阁雄载跟酥离散数学第29讲GraphTheory10