解迷宫问题方法二的证明

现在我们来证明上述规则的正确性，为此我们必须证明以下两点： 1.按我们的走法规则，从 A 出发，最后一定停止在 A；

2.当我们停止在 A 时，每一条边的两个不同方向都刚好走过一次。

我们先证明第一点。因为由规则 1，每一条边都有两个不同的方向可走， 并且每条边的每个方向恰好走一次。因此每一个顶点进出的次数都要一样多。那么对于 A 以外的顶点，有进去的方向必有出去的方向，结果不会停止在这些顶点上；而对 A 来说，我们是从 A 出发的，因为从 A 出去的次数跟进入 A 的次数要相等，所以最后必须回到 A 而停止。

现在来证明第二点：当我们停止在 A 时，每一条边的两个不同方向都刚好走过一次。

  1. 先证明当我们停止在 A 时，和 A 关联的所有边的两个方向刚好都走过一次。

  1. 当我们停止在 A 时，按规则 3，和 A 关联的每条边都按出去的方向走过了。否则，我们还应继续走而不能停止。

  2. 由于顶点 A 和其他顶点一样，自 A 出去的次数必须跟进入 A 的次数一样，所以和 A 关联的所有边跟出去的方向相反的方向也已走过了。

  3. 按规则 1，如果一条边按两个相反方向走过了就不再走了，所以跟A 关联的每条边，刚好走过两个相反方向而不会多走。

  1. 现在证明，当我们停止在 A 时，和其他顶点关联的所有边也都按两个相反方向，刚好走过一次。

假设我们沿 AB 第一次到达顶点 B。当我们停止在 A 时，上面已经证明了AB 的两个相反方向我们都已走过了。也就是说从 B 返回 A 的方向也已走过了。我们注意到，沿着 AB 的方向第一次到达顶点 B 的时候，我们在 B 处标有双箭号；而 BA 正是这个双箭号的相反方向。在规则 2 中，我们曾约定，只有当和 B 关联的其他所有边的两个方向都走过了才能走 BA。现在既然我们已经走了 BA，就意味着和 B 关联的所有边的两个方向都已走过了，而且由规则 1， 这些边的两个方向都恰好走过一次。现在我们考察由 B 出发第一次到达的顶点 C。按同样的推理，和顶点 C 关联的所有边的两个相反方向也恰好走过一次。仿此一直推下去，因为图是连通的，顶点数有限，我们就能一步步推得和所有顶点关联的一切边，都按两个不同方向刚好走过一次。这样，我们就证得了方法二的正确性。所以，规则 1 到 4 就是我们解迷宫问题的方法二， 而不再只是猜想了。

刘老师最后风趣地说：“今天我们介绍的解迷宫问题的方法二，应该说还是纸上谈兵，你们不妨再到青少年乐园中去实践一番。”她接着说：“关于游迷宫问题的讨论，我们就准备到此为止。通过这几次数学爱好者协会的活动，你们有什么心得体会，如果有时间的话，可以总结一下，在下一期班上的学习园地里交流。”