数学专题第三期：七桥问题与欧拉定理
sker114514
·
·
学习·文化课
题目出处
德国有个叫哥尼斯堡的地方，那里有一条河，河中央有两座小岛，有七座桥连接着这两座小岛与河岸。
为了节省游览小岛的时间，有一个人提出了一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。
$1736$ 年，在经过一年的研究之后， $29$ 岁的欧拉提交了《哥尼斯堡七桥》的论文，把它转化成一个几何问题—— 一笔画问题。这也开创了数学的两个新的分支——图论与拓扑学。
# 欧拉的解题思路
欧拉本来想用暴力枚举的方法，把每种可行路径都试一遍，但他一算，每座桥均走一次，那这七座桥所有的走法一共有 $7$ × $6$ × $5$ × $4$ × $3$ × $2$ × $1$ = $5040$ （种）。这么多走法，他当然没法列举，而且如果以后再碰到这种问题，还能一个个试吗？当然不可能。所以，欧拉必须找出一种规律以解决类似的问题。
为了更好地解决这个问题，欧拉将河道省略，把桥画成线，把四块陆地当成四个点，如下图：
通过这样的改变，七桥问题便转化为只用一笔是否能够通过这七条线的问题。若可以画出来，则图形中必有终点和起点，并且起点和终点应该是同一点，由于对称性可知由 $B$ 或 $C$ 为起点得到的效果是一样的，若假设以 $A$ 为起点和终点，则必有一离开线和对应的进入线，若我们定义进入 $A$ 的线的条数为入度，离开线的条数为出度，与 $A$ 有关的线的条数为 $A$ 的度，则 $A$ 的出度和入度是相等的，即 $A$ 的度应该为偶数。即要使得从 $A$ 出发有解则 $A$ 的度数应该为偶数，而实际上 $A$ 的度数是 $5$ 为奇数，于是可知从 $A$ 出发是无解的。同时若从 $B$ 或 $D$ 出发，由于 $B$ 、 $D$ 的度数都是 $3$ ，都是奇数。所以这个七桥问题就是无解了。
# 欧拉定理
欧拉在他的论文中也详细介绍了一个图能被“一笔画”的三条需要满足的条件：
1. 凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图（偶点是指从一个点向外发出的线的条数为偶数）。
2. 凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点为终点（奇点是指从一个点向外发出的线的条数为奇数）。
3. 其他情况的图都不能一笔画出(奇点数除以 $2$ 便可算出此图需几笔画成)。
欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为**欧拉定理**。对于一个连通图，通常把从某结点出发一笔画成所经过的路线叫做**欧拉路**。人们又通常把一笔画成回到出发点的欧拉路叫做**欧拉回路**。具有欧拉回路的图叫做**欧拉图**。
------------
以上就是本期数学专题的全部内容啦！
完结撒花！
By ImNot6Dora