《中国邮递员问题》.ppt

该【《中国邮递员问题》 】是由【相惜】上传分享，文档一共【36】页，该文档可以免费在线阅读，需要了解更多关于【《中国邮递员问题》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。运筹学之中国邮递员问题昆明理工大学信息工程与自动化学院整理ppt整理ppt七桥问题SevenBridgesProblem〔引点〕18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里,有七座桥将普雷格尔河中两个岛以及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发,恰好通过每座桥一次,再回到起点?(图见P251页,图10-1)整理ppt从七桥问题到一笔画思想欧拉于1736年研究并解决了此问题,他用点表示岛和陆地,两点之间的连线表示连接它们的桥,将河流、小岛和桥简化为一个网络,把七桥问题化成判断连通网络能否一笔画的问题。之后他发表一篇论文,证明了上述走法是不可能的。并且给出了连通网络可一笔画的充要条件这一著名的结论。整理ppt如图可见P251页图10-1〔b〕CDAB因为图中的每个点都只与奇数条相关联,所以不可能一笔画出整理ppt一笔画问题什么是一笔画问题呢?一笔画问题:从某一点开始画画,笔不离纸,各条线路仅画一次,最后回到原来的出发点。整理ppt想一想:bca图1v2v3v1v4图2图1和图2当中哪一个图满足:从图中任何一点出发,途径每条边,最终还能回到出发点?由此试想一下:一个图应该满足什么条件才能到达上面要求呢?整理ppt一笔画问题〔中国邮路问题根底〕但凡能一笔画出的图,奇点的个数最多有两个。始点与终点重合的一笔画问题,奇点的个数必是0。在一个多重边的连通图中,从某个顶点出发,经过不同的线路,又回到原出发点,这样的线路必是欧拉图,即能一笔画出的图必是欧拉图。整理ppt定理1:连通的多重图G是欧拉图,当且仅当G中无奇点。定理2:任何一个图中的奇点个数必为偶数。推论:连通的多重图有欧拉链,当且仅当图中有两个奇点。整理ppt什么是欧拉链?给定一个连通多重图G,假设存在一条链,过每边一次,那么称这条链为欧拉链。那什么又事欧拉圈呢?假设存在一个简单圈,过每边一次,且仅一次,那么称为欧拉圈。一个图假设有欧拉圈就可以称之为欧拉图整理ppt