六 解迷宫问题方法一的证明

休息后，刘老师继续主持讨论会，她开始介绍解迷宫问题方法一的证明

①。

前面已经说过，要证明方法一是正确的，必须证明以下两点： 1.按照方法一，确能从迷宫入口 A 进去，再回到 A；

2.按照方法一，每条边都能走过至少一次。

要证明第一点是很容易的，因为按方法一第 1 点，我们从 A 进去，又按

方法一的第 2、第 3 点，我们在图中的某顶点没有边需要再走的时候，就按原路返回。按原路返回的意思就是说，原来从 A 怎么走到那里的，就从那里倒过去顺着原路走回到 A，因此按方法一，最后一定又回到 A。

{ewc MVIMAGE,MVIMAGE, !16000290_0048_1.bmp}图 6-1

要证明第二点，我们可以这样想：假如按方法一我们在图中描出了一条路，不妨用粗线表示（图 6-1）：

我们假设图中还有一些边没走过。要是我们能够证明那些没被走过的边中，至少有一条边（如图 6-1 的 DC）和我们已走过的路中的某个顶点（C） 关联，那么按方法一，在返回的路上，必然遇到这个顶点。当我们到达这个顶点的时候，发现这条边未走过，就按方法一第 3 点，这条未走过的边就总会被走到。这样，我们走过的边又至少多了一条。如果这时图中还有一些边未走过，则依同理，我们又能再多走一条。由于图的边数有限，最后所有边都会全部被走过。这样，证明的目的达到了。

按照上面的想法，要证明第 2 点，关键在于应当证明“如果我们在图中走出了一条路，而还有一些边没走过，那么那些没走过的边中至少有一条边和我们已走过的路中的某个顶点关联”。我们把它写成定理 1。

〔定理 1〕假设在一个连通图中，我们已经走了一条路（或回路）p，还有一些图中的边未被走过（即不在 P 中），则一定有一条不在 P 中的边的端点是路 P 的某个顶点。

为了让大家容易理解，我们一边看图 6-1，一边来说定理 1 的证明。 设图 6-1 中的粗线是我们已走过的路 p，其他不在 p 上的边（细线）是

没走过的。我们任取一条未走过的边，例如 MK，当然也可能是 DC 或 GI 等等。我们所取的这条未走过的边有两种可能情况：

  1. 这条边有一个端点是 P 中的顶点（例如 GI 的两个端点就都是 P 的顶点），这时我们的问题就已经解决了；

  2. 这条边的两个端点都不是 P 的顶点（例如 MK），我们从这两个端点中任取一个端点（例如 MK 中的 M）。由已知，图是连通的，所以在 P 中任取一个顶点（例如 G），一定能使这两个点（例如 G 和 M）之间有一条路（例如 p1＝Ge8He10Je12Ke14M）。

由于 G 在 p 中，M 不在 p 中，所以沿路 p1 中的边从 G 走到 M，总会经过至少一条不在 P 中的边（如 e12，e14），那么，沿 p1 从 G 走到 M 遇到的第一条未走过的边（e12），就是我们要找的既不在 P 中（未走过）而又有一个端点（J）在 P 中的边。

① 对这一段证明，如果你感到比较困难，可以跳过去不看。对以后比较深的证明内容都可跳过去不看。

综合（1）和（2），我们就证明了定理 1 是成立的。

有了定理 1，我们确信解迷宫问题的方法一是普遍可行的正确方法。刘老师最后说：“我们现在已经找到解迷宫问题的一个方法了，但这个

方法好不好，大家还可以回去考虑和实践。今天的讨论会就开到这里。”