东普鲁士(现俄罗斯)的Königsberg地区被河流分割成四个地区,四个地区之间由七座桥连接。一个人能否在一次散步中不重复地走过全部七座桥呢?1736年数学家欧拉对“Königsberg七桥问题”进行了研究。他将每个地区抽象成一个点,每座桥抽象成点与点之间的一条边,构造了Königsberg七桥问题简化图,并将问题转化为图论中的数学问题:从图的一点出发,是否存在经过每条边一次的路径存在?欧拉从图的简化出发,完全解析地证明了不存在一条路径能够一次遍历Königsberg地区的七座桥。如果要使一个图形可以一笔画,必须满足图形是连通的且图中的奇点数个数是0或2,而七桥问题中4个点都是奇点,因此不可能一笔画。欧拉对Königsberg七桥问题的抽象和论证开创了数学中图论的研究,也揭示了网络结构和网络性质密切相关的特点。
图 1 Königsberg七桥问题[1]。(a) Königsberg的四个地区和七座桥的示意图;(b) Königsberg七桥问题的简化图表示。
参考文献
[1] Hopkins B, Wilson R J. The truth about Königsberg[J]. The College Mathematics Journal, 2004, 35(3): 198-207.