七孔桥问题及图论

数学中有一个专门的专业，叫图论。说起来这个图论的起源，与一个游戏相关。
以下内容摘自吴军写的《数学之美》。

图论的起源可追溯到大数学家欧拉（Leonhard Euler）。

1736 年欧拉来到德国的哥尼斯堡（Konigsberg，大哲学家康德的故乡，现在是俄罗斯的加里宁格勒），发现当地市民们有一项消遣活动，就是试图将下图中的每座桥恰好走过一遍并回到原出发点，从来没有人成功过。

欧拉证明了这件事是不可能的，并写了一篇论文，一般认为这是图论的开始。

欧拉七桥问题的证明

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

哥尼斯堡七桥的抽象图

对于图中的每一个顶点，它相连的边的数量定义为它的度（Degree)。

定理：如果一个图能够从一个顶点出发，每条边不重复地遍历一遍回到这个顶点，那么每一顶点的度必须为偶数。
证明：假如能够遍历图的每一条边各一次，那么对于每个顶点，需要从某条边进入顶点，同时从另一条边离开这个顶点。进入和离开顶点的次数是相同的，因此每个顶点有多少条进入的边，就有多少条出去的边。

也就是说，每个顶点相连的边的数量是成对出现的，即每个顶点的度都 是偶数。

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