哥尼斯堡七桥问题

问题背景



18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如左下图）。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。后来大数学家欧拉把它转化成一个几何问题——一笔画问题。



问题解决



在论文中，欧拉将七桥问题抽象出来，把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。并由此得到了如图一样的几何图形（如右上图）。



若我们分别用A、B、C、D四个点表示为哥尼斯堡的四个区域。这样著名的“七桥问题”便转化为是否能够用一笔不重复的画出过此七条线的问题了。



得到的图形中必有终点和起点，并且在此问题中起点和终点应该是同一点，由于对称性可知由B或C为起点得到的效果是一样的。若假设以B为起点和终点，则必有一离开线和对应的进入线（每一次当一个人由一座桥进入一块陆地时，他也将由另一座桥离开此陆地），若我们定义进入B的线的条数为入度，离开线的条数为出度，与B有关的线的条数为B的度，则B的出度和入度是相等的，即B的度应该为偶数。即要使得从B出发有解则B的度数应该为偶数，而实际上B的度数是5为奇数，于是可知从B出发是无解的。同时若从A或D出发，由于A、D的度数分别是3、3，都是奇数，即以之为起点都是无解的。



问题结论



由上述理由可知，对于所抽象出的数学问题是无解的，即“七桥问题”也是无解的。



推论：欧拉回路



由此我们可知要使得一个图形可以一笔画，必须满足如下两个条件：



1. 图形必须是连通的。



2. 图中的“奇点”个数是0或2。



我们也可以依此来检验图形是不是可一笔画出。回头也可以由此来判断“七桥问题”，4个点全是奇点，可知图不能“一笔画出”，也就是能不重复地通过所有七桥。