Mathematics

哥尼斯堡七桥问题

要求:现在你要找出走遍七座桥的方法。但是必须遵守以下条件: 走过的桥不可再走 可以经过同一陆地 可以以任一陆地为起点 不需回到原点 若能走遍七座桥,请说明方法。若不能,也请给出证明。 其实这就是“一笔画”的问题,意思就是从下笔开始,所画的线要经过每一块陆地,笔画不能出现间断。用图2的方法发现最后也到达不了g桥。读者们也可以多多画一下,尝试一下。最后发现根本不可能走遍七座桥,但是我们要证明出来。因为或许有方法只是我们没有想到而已。 我们考虑将问题简化一下,因为每次使用上图来进行试验以及问题的思考其实是相对麻烦的。这种图形化的“链接方式”称作“图”(Graph)。 在图3中,用白色的圈来表示陆地A、B、C、D,我们成为“顶点”。用顶点之间的连线来表示桥a、b、c、d、e、f、g,我们称其为“边”。 顶点所关联的边数称其为“度数”。 度数为偶数的点称为“偶点”,度数为奇数的点称为“奇点”。接下来顺着图中的边走,在经过的边的端点出打上钩,并减去顶点的度数。我们将此称为“边走边减”。 目前不关心具体是从哪里开始的,经过的路径,只看顺着边走的时候顶点的度数是如何变化的。出发时,起点的度数减1。 途中经过每一个顶点时,该顶点的度数减2,因为经过了“入口边”和“出口边”。 每次经过顶点,顶点的度数都会减2。因此不管经过顶点多少次,经过的顶点的奇偶性不会变,即奇点还是奇点,偶点还是偶点。 到达终点时,该顶点的度数减1。 我们假设如此“完成了一笔画”,那么可能出现一下两种情况。 (1)起点和终点相同的情况    一笔画成,也就意味着“边走边减”的结果是所有顶点的度数变为0(偶数)。为什么?因为如果还存在不为0的顶点,那么也就存在没经过的边。    经过“边走边减”之后,经过的顶点的奇偶性不变。由此我们可知度数变为0(偶数)的经过点,在原图中本身就是偶点。    此外,起点度数减1,终点度数也减1,变为0。然而,起点和终点是同一顶点,所以顶点的度数减2,所以该顶点也成了偶点。    结论,在“起点与终点相同”的一笔画中,图中所有的顶点都是“偶点”。 (2)起点和终点不相同的情况    和(1)的 思路相同,经过的顶点都是偶点,只有起点和终点是奇点。据此,在“起点和终点不同”的一笔画中,图中只有两个“奇点。    至此,可知以下命题是成立的: (如果)“可以画成一笔画” =》“所有顶点都是偶点,或者有2个奇点。” 我们回到哥尼斯堡七桥问题。如果哥尼斯堡的七桥能用一笔画通过的话,应该满足 “ 所有顶点都是偶点,或者有2个奇点 ”。 我们来看看哥尼斯堡七桥(图10)的顶点。如图所示,四个点都是“奇点”。由此证明了在给定条件下不能走遍哥尼斯堡七桥。...

Continue reading...