【添翼思维】哥尼斯堡七桥问题、欧拉和图论

哥尼斯堡，即现在俄罗斯的飞地加里宁格勒州首府加里宁格勒，曾是德国东部的一个城市，一座盛产文化名人的地方。她是德国哲学家康德和数学家希尔伯特的故乡，希尔伯特的好友著名数学家闵可夫斯基成长于此。欧拉是作者心目中最伟大的数学宗师之一，跟欧几里得，阿基米德，牛顿，莱布尼茨，高斯以及黎曼等人一样，乃是人类数学史上不朽的丰碑！但是，在数学世界里，哥尼斯堡却以哥尼斯堡七桥问题而被数学家和计算机科学家视为文化名城。

哥尼斯堡七桥问题是图论中的著名问题。这个问题基于生活。当时东普鲁士哥尼斯堡市区跨普列戈利亚河两岸，河中心有两个小岛。小岛与河的两岸有七条桥连接。有好事者提出一个问题：在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？

欧拉知道了这个有趣的问题。他在1735年提出，并没有方法能圆满解决这个问题。第二年，他发表了论文《哥尼斯堡的七桥》。欧拉把七桥问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点，如下图所示。他把一个实际问题转化成一个抽象问题。他证明了这个抽象问题的解不存在，并提出和解决了一笔画问题。

欧拉论述道：这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数，这样的点称为偶顶点。相对的，连有奇数条线的点称为奇顶点。由于柯尼斯堡七桥问题中存在4个奇顶点，它无法实现符合题意的遍历。因此，欧拉证明了七桥问题没有解。

欧拉这篇论文开启了数学的新学科图论 （graph theory）。图论是现代计算机科学很多问题的基础，也是互联网的理论基础之一。 它为添翼工软的工艺设计技术提供了重要的理论基础。

作者的数学和技术研究工作有四个领域与图论有交集，它们分别是：

1.   Phase-locking on graphs ofcoupled oscillators （耦合振荡器图的锁相）；

2.   The theory of arithmetic graphs(算术图理论);

3.   The theory of D-M graphs（D-M图理论）;

4.   A heuristic algorithm forsubgraph isomorphism problem （子图同构问题的启发式算法）。