《哥尼斯堡七桥问题与图论.pdf》由会员分享，可在线阅读，更多相关《哥尼斯堡七桥问题与图论.pdf（2页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 1 哥尼斯堡七桥问题与图论 大家公认，图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler，17071783）于 1736年发表了论文与位置几何有关的一个问题的解，文中提出并解决了七桥问题，为图论的形成奠定了基础。今天，图论已广泛应用在计算机学科、运筹学、控制论、信息论等学科中，成为对现实世界进行抽象的一个强有力的数学工具。七桥问题是这样描述的：17 世纪的东普鲁士有一座哥尼斯堡城（现在叫加里宁格勒，在波罗的海南岸），城中有一座岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区 4 个区域，全城共有七座桥将 4 个城区连接起来，图 1 是这条河以
2、及河上的两个岛和七座桥的草图。于是，产生了一个有趣的数学难题：一个人是否能在一次步行中穿越全部的七座桥后回到起点，且每座桥只经过一次？为了解决哥尼斯堡七桥问题，欧拉用 A、B、C、D 表示 4 个城区，用 7 条线表示 7 座桥，将哥尼斯堡七桥问题抽象为一个图模型，如图 2 所示，从而将哥尼斯堡七桥问题抽象为一个数学问题：求经过图中每条边一次且仅一次的回路，后来人们称之为欧拉回路。欧拉论证了这样的回路是不存在的，并且将问题进行了一般化处理，即对于任意多的城区和任意多的桥，给出了是否存在欧拉回路的判定规则：（1）如果通奇数桥的地方多于两个，则不存在欧拉回路；（2）如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；2（3）如果没有一个地方通奇数桥，则无论从哪里出发，都能找到欧拉回路。