哥尼斯堡七桥问题与图论
大家公认，图论诞生于七桥问题。

出生于瑞士的伟大数学家欧拉（Leonhard Euler，1707—1783）于1736年发表了论文《与位置几何有关的一个问题的解》，文中提出并解决了七桥问题，为图论的形成奠定了基础。

今天，图论已广泛应用在计算机学科、运筹学、控制论、信息论等学科中，成为对现实世界进行抽象的一个强有力的数学工具。

七桥问题是这样描述的：17世纪的东普鲁士有一座哥尼斯堡城（现在叫加里宁格勒，在波罗的海南岸），城中有一座岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，全城共有七座桥将4个城区连接起来，图1是这条河以及河上的两个岛和七座桥的草图。

于是，产生了一个有趣的数学难题：一个人是否能在一次步行中穿越全部的七座桥后回到起点，且每座桥只经过一次？
为了解决哥尼斯堡七桥问题，欧拉用A、B、C、D表示4个城区，用7条线表示7座桥，将哥尼斯堡七桥问题抽象为一个图模型，如图2所示，从而将哥尼斯堡七桥问题抽象为一个数学问题：求经过图中每条边一次且仅一次的回路，后来人们称之为欧拉回路。

欧拉论证了这样的回路是不存在的，并且将问题进行了一般化处理，即对于任意多的城区和任意多的桥，给出了是否存在欧拉回路的判定规则：
（1）如果通奇数桥的地方多于两个，则不存在欧拉回路；
（2）如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；
（3）如果没有一个地方通奇数桥，则无论从哪里出发，都能找到欧拉回路。