九 解迷宫问题的方法二——刘老师的第四次讲座

“上次讲座,我们从哥尼斯堡七桥问题引出了欧拉图的概念,并对怎样的图是欧拉图作出了猜想,最后证明了如下的定理 2:

“一个连通图是欧拉图■这个图所有的顶点都是偶顶点。 “现在我们要利用它来研究游迷宫问题。我们知道,图 9-1(a)表示图

  1. 的迷宫。图 9-1(a)除 A 以外所

{ewc MVIMAGE,MVIMAGE, !16000290_0073_1.bmp}图 9-1

有顶点都是奇顶点,所以它不是欧拉图,不能从入口 A 出发,不重复地走遍迷宫中的每条边再回到 A。其实如果我们进入一个不知道它的平面图的陌生的迷宫,我们也无法判断它的图是否是欧拉图。但是容易想到,任何一个连通图,如果把它的每一条边都变成二重边(图 9-1(b)),那么变化后的图一定是欧拉图,因为它的所有顶点都是偶顶点。

“如果我们能在如图 9-1(b)的图中,从 A 出发按某种规则走出一条欧拉回路,再回到 A,那就意味着我们游图 9-1(a)中的迷宫的时候,每条边恰好走了两次。看来,这是在我们事先不知道迷宫平面图的时候,解决游迷宫问题的最好的办法了。下面我们的任务就是探索出一种从入口 A 进入迷宫,把迷宫中每条边刚好走两次再回到 A 的具体方法来。如果能找到这个方法,就比我们上次讨论的方法一要好多了。”