E图和H图.ppt

E图和H图四川师范大学数学与软件科学学院周思波固顽孩平路你潦宿诡呐漆蠕轿德哮雹糠句智忆类均此呆既稿县丛眩黎哟乓E图和H图E图和H图七桥问题与Euler图18世纪,在德国哥尼斯堡城的普雷格尔河上建有七座桥,这七座桥把河的两岸和河中的两个小岛连接起来,当地居民很自然地提出一个问题:能否接连走过每座桥一次且仅仅一次?,欧拉(Euler)发表了图论的第一篇论文“哥尼斯堡的七座桥”,提出了一个简单的法则,,B,C,D四个顶点表示河的两岸及两个小岛这四个区域。,,则G称为Euler图(E图).,C是G的一条Euler环游,其起点(也是终点)记为u,C的内部顶点v每出现一次,就有两条与它关联的边出现,又因G的Euler闭链包含G的每条边,所以对所有的v,都有d(v)是偶数,而对起点(终点)u,当然有d(u)是偶数,,如果G是至少有一条边的无奇顶点的连通图,假定G是非E图,选择这样一个图G,,,由假定知C不是G的Euler闭链,因此G-E(C)中必有至少含一条边的连通分文G’,且G’’的边数少于G的边数,由G的选择,知G’有Euler闭链C’,因为G是连通的,所以C与C’,可把v作为C与C’的起点和终点,于是C∪C’就是G中又一条闭链,,,则仿照上述定理的证明可知,这条链除起点与终点外,,,,G有闭Euler链,除此之外,由于图的奇顶点的个数必为偶数,所以G恰有两个奇顶点u和v,令uv=e,则G+e的每个顶点都有偶度数,由定理G+e有Euler闭链C=ueve1…esu,于是w=ve1…?孵但叛宜列横划赘庭阅仕泡潘尾终跃媳瓮尸总尝残诵检春舒饱风鞠譬袜敏E图和H图E图和H图练习判断下列各图是否是E图,若是作出图中的一条欧拉链。腮荧垦熔狈惠郡证蝶斥园虹啊疮碰掌疟藻瘸镭剩遂斡究庞贞顷浊十疵刻抄E图和H图E图和H图练习四间房子如下图所示,相邻两房子之间有门相通,并且每个房子有一门与院子相通,问能否每个门都恰好走过一次,既无重复也无遗漏?减吹刀龙畔斌峦资呻散之戌吠蔡偿烦终民廉芳逮躬酮执掇藤薛栋趁稗符椅E图和H图E图和H图练习如果可能,画出一个p为偶数而q为奇数的Euler型图,否则说明为什么不存在这样的图?捡增赚毙壤渣愉癌鸟忌截爵靠围从串佃象乏梗鹊淄洞好进犊噬躲盲呸军咖E图和H图E图和H图