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图