哥尼斯堡七桥问题

时间:2024-05-21 11:10:26

哥尼斯堡七桥问题

问题描述

现在你需要找出走遍7座桥的方法,但是,必须遵守以下条件:
1 走过的桥不能再走
2 可以多次经过同一块陆地
3 可以以任一陆地为起点
4 不需要回到起点

简化模型

哥尼斯堡七桥问题
数学家欧拉已经将这个问题作为一笔画问题解决,这就是图论的开山鼻祖。

思考过程

在反复的实验中,我们注意到了:要通过一个顶点,这个顶点必须具有2条边,即“入口边”和“出口边”。1个顶点关联着多条边,但是每通过顶点一次,这个顶点就减去2条边。这就是暗藏玄机之处。

顶点所关联的边数,称之为该顶点的度数。
哥尼斯堡七桥问题

度数为偶数的顶点称之为“偶点”,度数为奇数的点称之为“奇点”。
接下来,顺着图中的边走,在经过的边的端点处打上勾,并且减去顶点的度数。我们将此称为“边走边减”。
哥尼斯堡七桥问题

我们并不关心边具体是从哪里开始的额,通过什么路径,只看顺着边走时的度数是如何变化的。

出发时,起点的顶点度数减1.
哥尼斯堡七桥问题
途中每经过一个顶点时,该顶点的度数减2,因为经过了”入口边”和”出口边”。
哥尼斯堡七桥问题
每次经过顶点,顶点的度数都减2.因此不管经过顶点几次,经过的顶点的奇偶性不变,即偶点还是偶点,奇点还是奇点。
哥尼斯堡七桥问题
最终到达顶点时,该顶点的度数减1.
哥尼斯堡七桥问题
我们假设如此完成了一笔画,那么可能出现以下两种情况:
(1)起点和终点相同的情况
总结起来就是图中的顶点都是偶点

(2)起点和终点不同的情况
图中只有两个奇点

总结

如果哥尼斯堡的七桥能用一笔画通过的话,那么应该满足“所有点都是偶点,或者有2个奇点”
但是在图中,4个顶点都是奇点,由此证明了给定的条件下不能走遍七桥。

欧拉的论断重点在于:不反复试验也能证明不能一笔画成。不用频繁地试走各种路径,只要观察各顶点的度数就可以。

另外,欧拉的证明中蕴含着很重要的思维方法,那就是在观察各个顶点的边数时,着眼点不在“数的本身”,而是数的奇偶性。并不是1条、3条、5条这样分散地思考路径,而是概括为“奇数条”来整体思考。

当我们想要详细地研究事物时,往往容易陷入“想正确把握所有细节”的思维。但是,如奇偶性校验那般,较之“正确地把握”,有时“准确地分类”则更为有效。