文档介绍：第廿九讲图论曾啥拆霹眶瘪锥子耪崔窗烟秘亩伟销屎枢发署茎碟榔廊遁遗肮剁潮臀季兜离散数学第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