奇偶性校验

要求：现在你要找出走遍七座桥的方法。但是必须遵守以下条件： 走过的桥不可再走 可以经过同一陆地 可以以任一陆地为起点 不需回到原点 若能走遍七座桥，请说明方法。若不能，也请给出证明。 其实这就是“一笔画”的问题，意思就是从下笔开始，所画的线要经过每一块陆地，笔画不能出现间断。用图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...