欧拉七桥问题

什么是“欧拉七桥问题”？

柯尼斯堡七桥问题（Seven Bridges of Königsberg）是图论中的著名问题。这个问题是基于一个现实生活中的事例：当时东普鲁士柯尼斯堡（今日俄罗斯加里宁格勒）市区跨普列戈利亚河两岸，河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？ ——维基百科

图1  柯尼斯堡七桥的原始图

---

如何将“欧拉七桥问题抽象成数学问题”？

把每一块连通的陆地作为一个顶点，每一座桥当成图的一边，那么就把柯尼斯堡的七座桥抽象成下面的图：

图2  柯尼斯堡七桥的抽象图

定理：

如果一个图能够从一个顶点出发，每条边不重复地遍历一遍回到这个顶点，那么每个顶点的度（和该顶点相关联的边的条数）必须为偶数。

证明：

假如能够遍历图的每一条边各一次，那么对于每个顶点，需要从某条边进入顶点，同时从另一条边离开这个顶点。进入和离开的次数是相同的，因此每个顶点有多少条进入的边，就有多少条出去的边。也就是说：每个顶点相连的边的数量是成对出现的，即每个顶点的度都是偶数。

结论：

在图2中有多个顶点的度为奇数，因此，这个图无法从一个顶点出发，遍历每条边各一次然后回到这个顶点。