柯尼斯堡七桥问题

问题的由来

18世纪初在普鲁士柯尼斯堡镇（今俄罗斯加里宁格勒）流传着这样一个问题：该城内一条河，河的两支流绕过一个岛，有七座桥横跨这两支流（如下图所示）。

问一个散步者能否走过每一座桥，而每座桥却只走过一次。

问题的解决

伟大数学家欧拉（Leonhard Euler）在1736年圆满地解决了这个问题，并为此在圣彼得堡科学院发表了图论史上第一篇重要文献。

他把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后遍历所有的线，且每一条线只经过一次，则连了奇数条线的点不得超过3个。而该图的存在4个这样的点。

由此引发的

七桥问题引发了人们对图论的研究，被认为是拓扑学理论基本应用题，对解决最短邮路等问题很有帮助。

七桥问题有时候也会被称为“一笔画”问题，也就是笔不离开纸面，一口气走过全部指定的路径一笔画问题标准的解是：奇顶点的个数只能是0或者2个。

其中的道理很简单。因为要么你的笔会通过一个点，这样就给这个点添加了偶数条边，要么你从这个点出发，或者从这个点终止。这样就有两种情况:

  (1)如果出发点和终止点是同一个点的话，则终止的边和出发边各一条，加起来是偶数其他点都是被通过的点，也是偶数条边，所以没有点连接奇数条边;
  (2)如果出发点和终止点不是同一个点的话，则出发点出了通过它的线之外，还有一条出发的线，这样出发点所连的线为奇数条，同理，终止点所连的线也为奇数条，
这样就有两个奇点。

P.S.由于这个著名的问题把大家到引到柯尼斯堡去尝试，有关当局为了满足游客，在当地兴建了第八座桥，使游客能够一次走遍所有的桥而不用重复路线。