迷宫中的数学

前　　　　言

如果你要到一个大岩洞里去探险，该怎样走才能走遍岩洞的每个地方再安全地出来？如果你在地道里迷了路，如何自寻出路？读了这本小册子，不仅将得到这两个问题的满意答案，而且还可以学到一些图论的基本知识和探索问题的基本方法。

迷宫中的数学

一　　小探险家一游迷宫

我们的故事发生在一座风景秀丽的滨海城市。这个市的青少年乐园里，新近落成了一座奇巧的建筑物——迷宫。几天时间，吸引了很多很多的青少年朋友。凡是游过迷宫的人，无不感到兴趣盎然。那些在迷宫里迷了路，吃够了“绕圈子”、“碰壁”的苦头，最后拖着酸软的双腿走出迷宫的人，更是津津乐道，准备重游。迷宫落成的消息，很快惊动了我们这本小书的主人公之一——陈虎。

陈虎确实生得虎头虎脑，身体胖得像个一号电池。他正在念初中三年级，同学们都叫他小虎子。他有很强的好奇心，爱看冒险小说，打算将来做个探险家，只是他的性情比较急躁，行动莽撞。迷宫落成的消息使他兴奋异常，他马上去约同班的好友林文和黄杰一起去“探险”一番。

林文和黄杰的性格比较文静。林文喜爱文学，黄杰却对数学特别感兴趣。他们对迷宫的兴趣显然不如陈虎大，但是经不起好朋友绘影绘声的宣传，终于同意星期天下午一道去游迷宫。

这是一个风和日丽的日子。三个小探险家来到了那座奇妙的建筑物前面。那是一个边长约３０米的露天正方形建筑物，大门的扁额上写着“迷宫”二字。进出的游人不少，小虎子一下子就想闯进去，想不到衣角却被黄杰拉住了。

“哎！哎！哎！看看说明再进去！”

原来黄杰一眼看见了墙上贴有“游宫说明”。这份说明实在跟公园的其他说明大不一样，现抄录于下：

游宫说明

一、游迷宫是一种益智的数学游戏，敬请游客多动脑筋，十二岁以下儿童如无年长者带领，谢绝游宫；

二、迷宫中心的标志是一尊半人半牛的希腊神像米诺陶，并备有休息处；

三、每个岔路口都有开关一只，如果迷路时需要问路，可掀开开关，将有一张图纸详细指示你所在的位置和继续前进的方法，看完请即关闭开关，图纸自行消失；

四、游客如需要，可领粉笔一支，以备游宫时使用。

迷宫管理处

我们的三个小探险家实在不明白第四条说明的意思，于是他们决定不予理睬，开始走入进口。一进迷宫，首先见到的是两个精致小巧的拱门，一个上方写着“引人入胜”，一个上方写着“渐入佳境”。三个小探险家犹豫了：该从哪个门进去呢？小虎子早就跃跃欲试，他提议道：“既然一道门能‘引人入胜’，一道门可以‘渐入佳境’，可能都是可以走的。咱们来个兵分两路，一路去‘入胜’，一路走‘佳境’，比赛谁先到迷宫中心，你们看如何？”这个富有挑战性的建议，马上得到其他两个人的一致赞同。他们商定陈虎从“入胜”进去，林文和黄杰去探寻“佳境”。

他们探险的结果如何，我们等一下再说，现在先向读者介绍一下这座迷宫的结构。为了便于说明，我们把它的平面图画在下面（图１—１）。

原来这座迷宫除了入口处有两个标有“引人入胜”和“渐入佳境”的拱门外，里面都以装饰相同的墙壁隔成许多弯弯曲曲的走道。迷宫的设计师为了迷惑游人，不仅在每个岔路口都造有拱门，而且明明走不通的绝路顶端，也造了外形完全一样的假拱门，乍一看去，使人分不清真假。为了后面说明方便，我们把“渐入佳境”的门记为甲，把“引人入胜”的门记为乙，并把每个岔路口和绝路端点都标上英文字母，Ｍ处是迷宫中心。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿０００６＿１．ｂｍｐ｝图１－１

当然，我们的这三个小探险家是没有见过这张平面图的。

且说小虎子闯入“引人入胜”的拱门（图１－１中的乙），顺道走到了Ｋ。他想，既然要往迷宫中心走，看来要向右拐，但是当他走到Ｌ后，发现上当了，原来Ｌ是一个假门。碰壁之后，只好退回来。以后他从Ｋ改道走到Ｇ，看到Ｆ处有个拱门，就连着穿过Ｇ和Ｆ，顺道走到Ｈ。经过这么几转，小虎子开始晕头转向，心里发慌了。他把迷宫中心的方向搞反了，穿过Ｈ走到了Ｊ。这下子又碰了壁，于是倒退回来，经过Ｈ一直走到Ｆ。这时的小虎子已经急得满头大汗了。幸好，正当他狼狈不堪的时候，看见他的两个好朋友走过来了。

原来他们两人进了“渐入佳境”（图１－１甲）的门，一直向中心进发，想不到竟拐了几个弯才走到Ｅ，更糟糕的是到了Ｅ以后，方向搞不清了。他们糊里糊涂走到Ｄ，碰了壁，退到Ｃ，穿过Ｃ从拱门甲出来，转过身一看，坏了！居然还是“渐入佳境”！他们知道这是未到中心先绕了一个圈子。以后他们又从原路进去，走到Ｅ，正在往Ｆ走的时候，看见小虎子在向他们招手哩！

当他们互相报告了碰壁的经过后，这三个难兄难弟哈哈大笑起来。他们决定启动开关问路，按照图纸的指示，终于到达了迷宫中心Ｍ。在这里，他们看到了一座小巧玲珑的假山，假山上有一尊牛头人身的怪物，看来这就是米诺陶了。他们在这里的水泥椅上休息、谈笑，最后寻路出去。天哪！怎么走出去又是一道难题！但是，我可以告诉读者们，他们最终都走了曲折的道路出来了。至于有没有再打开开关，那就不得而知了。

在回家的路上，他们虽然有些疲劳，但还是十分兴奋地议论着：这座迷宫确实是一个很奥妙的谜，既迷人又有趣。到底怎样自由进出迷宫呢？这是大家共同产生的问题。小虎子主张设法搞一张迷宫的平面图来，这样就可以按图游宫了。可是黄杰却不以为然，他说：“既然游宫说明中说游迷宫是一个益智的数学游戏，也许这里要用到什么数学知识，才能解决呢。”林文还补充了一个问题，那就是，迷宫中放一个半人半牛的怪物是怎么回事？他们决定把这些问题带回去请教他们的数学老师。

原来这座迷宫除了入口处有两个标有“引人入胜”和“渐入佳境”的拱门外，里面都以装饰相同的墙壁隔成许多弯弯曲曲的走道。迷宫的设计师为了迷惑游人，不仅在每个岔路口都造有拱门，而且明明走不通的绝路顶端，也造了外形完全一样的假拱门，乍一看去，使人分不清真假。为了后面说明方便，我们把“渐入佳境”的门记为甲，把“引人入胜”的门记为乙，并把每个岔路口和绝路端点都标上英文字母，Ｍ处是迷宫中心。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿０００６＿１．ｂｍｐ｝图１－１

当然，我们的这三个小探险家是没有见过这张平面图的。

且说小虎子闯入“引人入胜”的拱门（图１－１中的乙），顺道走到了Ｋ。他想，既然要往迷宫中心走，看来要向右拐，但是当他走到Ｌ后，发现上当了，原来Ｌ是一个假门。碰壁之后，只好退回来。以后他从Ｋ改道走到Ｇ，看到Ｆ处有个拱门，就连着穿过Ｇ和Ｆ，顺道走到Ｈ。经过这么几转，小虎子开始晕头转向，心里发慌了。他把迷宫中心的方向搞反了，穿过Ｈ走到了Ｊ。这下子又碰了壁，于是倒退回来，经过Ｈ一直走到Ｆ。这时的小虎子已经急得满头大汗了。幸好，正当他狼狈不堪的时候，看见他的两个好朋友走过来了。

原来他们两人进了“渐入佳境”（图１－１甲）的门，一直向中心进发，想不到竟拐了几个弯才走到Ｅ，更糟糕的是到了Ｅ以后，方向搞不清了。他们糊里糊涂走到Ｄ，碰了壁，退到Ｃ，穿过Ｃ从拱门甲出来，转过身一看，坏了！居然还是“渐入佳境”！他们知道这是未到中心先绕了一个圈子。以后他们又从原路进去，走到Ｅ，正在往Ｆ走的时候，看见小虎子在向他们招手哩！

当他们互相报告了碰壁的经过后，这三个难兄难弟哈哈大笑起来。他们决定启动开关问路，按照图纸的指示，终于到达了迷宫中心Ｍ。在这里，他们看到了一座小巧玲珑的假山，假山上有一尊牛头人身的怪物，看来这就是米诺陶了。他们在这里的水泥椅上休息、谈笑，最后寻路出去。天哪！怎么走出去又是一道难题！但是，我可以告诉读者们，他们最终都走了曲折的道路出来了。至于有没有再打开开关，那就不得而知了。

在回家的路上，他们虽然有些疲劳，但还是十分兴奋地议论着：这座迷宫确实是一个很奥妙的谜，既迷人又有趣。到底怎样自由进出迷宫呢？这是大家共同产生的问题。小虎子主张设法搞一张迷宫的平面图来，这样就可以按图游宫了。可是黄杰却不以为然，他说：“既然游宫说明中说游迷宫是一个益智的数学游戏，也许这里要用到什么数学知识，才能解决呢。”林文还补充了一个问题，那就是，迷宫中放一个半人半牛的怪物是怎么回事？他们决定把这些问题带回去请教他们的数学老师。

二　　神奇的迷宫——刘老师的第一次讲座

他们的数学老师姓刘。当她听了这三位小探险家的“探险”故事和问题以后，高兴地不住点头，并赞扬他们肯动脑筋提问题的好学精神。她说：“迷宫问题是一个很有趣的数学游戏，而且游迷宫的思想和方法还有些实际应用，比如，用现代电子计算机解题的一种搜索法就应用了游迷宫的思想；如果将来你们要到一个新发现的岩洞里去考察，或者在地道里迷了路，就要用到游迷宫的方法。如何寻找游迷宫的路线，确实能用数学知识来解决，可是这些知识既不是几何，也不是代数和三角，通常不在中学数学课本里介绍，它的名称叫‘图论’，是数学中的一个分支。但是，你们不必担心，只要使用其中很初步的一些知识就能解决游迷宫问题。如果你们有兴趣，我可以通俗地介绍给大家。”

黄杰一听，高兴得几乎跳起来，他说：“刘老师，那就请您在数学爱好者协会里做几次讲座吧！”

刘老师欣然答应了下来。

游迷宫问题的专题讲座，吸引了很多同学，我们的三位小主人公当然也参加了。下面是刘老师的第一次讲座。题目是：

神奇的迷宫

“我先给大家讲一个古希腊的神话传说。

“古希腊的克里特岛王米诺斯的王后生了一个半人半牛的怪物，取名米诺陶。皇后为了保护这个怪物的安全，请希腊最有本领的建筑师代达罗斯造了一座著名的迷宫。迷宫里有数以百计的狭窄、曲折、幽深的道路和使人眼花缭乱的阶梯以及很多小房间。不熟悉路径的人一旦走进迷宫，就会因迷失方向而走不出来。迷宫造成后，王后就把米诺陶藏在这座迷宫里。这个怪物靠吃人肉为生，它不仅吃在迷宫里迷路的人，而且米诺斯王还强迫雅典人每九年进贡七个童男、七个童女送到迷宫里给它吞食。这件事给雅典人民造成了深重的灾难。当米诺斯王派使臣第三次到雅典索取贡品的时候，年轻的雅典王子提修斯决心为民除害，自告奋勇和其他十三名童男童女一起去克里特岛。雅典王虽然很伤心，却阻挡不住提修斯的决心，提修斯一行终于出发了。当他被带去见米诺斯王的时候，引起了克里特岛王美丽、聪明的公主阿里阿德尼的爱慕，她偷偷地送给提修斯一个线球，并教他把线球的一端紧紧地拴在迷宫的入口处，然后放着线走进迷宫。她还给提修斯一把魔剑，用来杀死怪物。提修斯得到公主的帮助，把童男童女带进迷宫，找到怪物，经过一番激烈的搏斗，终于用魔剑把它杀死，然后顺着线路，把童男童女安全带出迷宫，为雅典人民做了一件大好事。

“克里特岛迷宫的故事脍炙人口，一直为人们所传颂。一九○○年，英国地质学家兼考古学家阿瑟・伊文思在这个岛的三米深的地层下，发现了一座面积达二万四千平方米的宫殿遗址，共有一千二百到一千五百个房间，据说这就是米诺斯迷宫的遗址。

“上面说的是古希腊关于迷宫的一个古代神话传说。在现实世界中，确实有一种叫做迷宫的建筑物。迷宫建筑是建筑学中的一种学问，据说外国至今还有一座建于一六九○年的迷宫，图２－１是它的平面图。

“传说古罗马的埃德萨城也有一座迷宫，它建在一个巨大的山洞里，里面不仅有走道、房间，而且还有迷惑人的阶梯，看上去以为是往上走的，走一段后却发现是往下去的。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００１３＿１．ｂｍｐ｝

“所谓迷宫，通常是指包括许多被墙壁所围的曲折的道路、绝路（有的还连着一些小房间）所组成的建筑物。青少年乐园新落成的那座建筑物，就是一座迷宫，它的中心有一尊牛头人身的怪物，就取自提修斯的故事。不熟悉路径的人进入迷宫，很容易迷路，绕了半天还走不出来。

“在我国的古典小说里，也有类似迷宫的记载。《三国演义》中有一段描述东吴大将陆逊陷入诸葛亮的八阵图的故事：有一天，陆逊在进军途中，到了一个叫渔腹浦的地方。看到诸葛亮过去布下的一个石阵，只见它四面八方都有门户，陆逊以为这没什么奥妙，闯入石阵观看，只见怪石嵯峨〔ｃｕóé〕，横沙立土重叠如墙。一时间风声阵阵，天色渐暗，当他急着要往回走的时候，却一直找不到出路，后来幸好一个老人引他出来。这个神奇的石阵看来就是一座迷宫。

“你们一定都看过《水浒》。实际上，‘三打祝家庄’里所描写的‘盘陀路’也是一种迷宫。要进入祝家庄只有通过盘陀路，而这种盘陀路是‘容易入得来，只是出不去’的。第一次攻打祝家庄的梁山泊好汉吃尽了盘陀路的苦头。他们‘走了一遭又转到这里’，弄得不少好汉被活捉，幸亏石秀侦察得盘陀路的走法，才把兵马带了出去。

“我们再举一个现代的例子。大家看过电影《地道战》，那里的地道，实际上也是神奇的地下迷宫，在抗日战争中，它起了很大作用。实际上，现代的地下人防工事，也是一座座神奇的迷宫。

“前几天，我们班上有几位同学到青少年乐园的迷宫里‘探险’一番，回来后向我提出了一个能不能用数学方法找出游迷宫路线的问题。这个问题提得很好，但是他们提的问题还不够明确，我想把它说得更明确一点，即：

“假设从迷宫的每个地方，可以走到任何一个地方，问如何从迷宫入口进去，游遍迷宫的每一条通道至少一次，再从迷宫的入口出来？我们以后就简称这个问题为游迷宫问题。

“游迷宫问题不仅是一个游戏，而且也有实用价值。当我们发现一个新的岩洞，需要进去考察，这个岩洞就可能是一座迷宫，设计考察路线就要用到游迷宫的知识；一个大型展览馆，也可以设计成一座迷宫，参观路线需要设计得使每个观众恰好经过每件展品一次。这些都要用到游迷宫的知识。

“关于这个问题的条件，还需要补充几句。有的同学可能在儿童杂志的数学游戏栏里见过游迷宫的游戏。你可能会想到，如果手中有一张迷宫平面图，那么仔细观察一下就能从图中找到一条所需要的路线，按找出的路线走就很容易了，何必用到数学知识呢？

“的确是这样的，如果有了平面图，就很好办了。但是，如果你要到一个新发现的山洞里去探险，那是什么平面图也没有的。我们的条件就是要在没有平面图的情况下来研究游迷宫问题。黄杰等几个同学已经试过了，在没有见到平面图的情况下，进入迷宫，到处都是装饰一样的墙壁，拐几道弯就迷失了方向。看来，如果没有一套办法，是很难游遍迷宫再出来的。”

刘老师讲到这里停了一下，问大家是否把我们要讨论的问题弄清楚了？大家回答都清楚了。刘老师让大家休息一会儿，然后再初步议论一下如何来

解决这个问题。

三　　林文的怪论

刘老师的讲座一开头就把同学们带进了古今中外神秘莫测的迷宫世界里，引起了同学们的极大兴趣，以致在休息的时候这些故事还萦回在他们的脑际。他们三三两两地议论着，男同学们崇拜提修斯的勇敢无畏，女同学们却更赞佩阿里阿德尼的聪明机智。更有不少同学想到青少年乐园的迷宫里实践一下，所以我们的三位小主人公就忙得不亦乐乎，因为同学们知道他们游过迷宫，都要他们介绍经验哩！

小虎子本来就直言快语，更拗（ｎｉù）不过同学们的请求，于是向大家介绍了青少年乐园的迷宫和他们三个人游迷宫的经过。最后，他说了一句话：“我们差点碰扁了鼻子。”这话引起了一阵哄堂大笑。

笑声伴随着铃声，同学们又回到了教室。刘老师等大家静下来以后，开始提出问题：

“刚才我们介绍了游迷宫问题，接下去我们要考虑如何来解这个问题，关于这方面，大家有些什么想法没有？”

不少同学举手要求发言，小虎子也是其中的一个。

“好！陈虎同学，谈谈你的看法。”

“我想我们能否也像提修斯一样，带一个线团去游迷宫。”

“你怎么利用这一团线团呢？”刘老师进一步问。

“我们也把它的一端拴在门口，然后放着线直冲进去。”陈虎的话逗得大家都笑了起来。

刘老师对这个回答是不够满意的。她感到陈虎考虑问题太粗糙。于是她请陈虎坐下，并且说：

“陈虎同学的思考太简单化。请不要忘记我们的目标是游遍迷宫的每个地方，如何靠线团的帮助，使我们能走遍迷宫的每个地方，是需要仔细考虑的问题。”

这时，林文要求发言，得到刘老师的同意后，他说：

“我认为提修斯带一个线球好像不能解决游迷宫问题。提修斯的线球只能保证他按原路走出迷宫，但是要走遍迷宫的每个地方就有困难了。那一天我们三个人去游迷宫的时候，我和黄杰从‘渐入佳境’的门进去，陈虎从‘引人入胜’的门进去，大家都没找到米诺陶就相遇了，可见迷宫中有绕圈子的路。如果提修斯也遇上这种路，他岂不是也在迷宫里老绕圈子。这样，他可能找不到米诺陶就只好顺着线走出来了。所以，希腊神话中所说的提修斯找到怪物并把它杀死，我有点怀疑，这也许缺乏科学根据。”

这真是一通怪论！林文发言后，教室里顿时活跃起来。有的同学原先认为带个线球可以解决问题的，现在在重新思索；有的同学不大同意林文的观点，却一时说不清理由。刘老师对林文的看法感到意外，她略微思索了一下，就找到了问题的症结所在。虽然她发现林文的想法是不对的，但是，她为有这样思想活跃的学生感到高兴。她感到，有必要让学生们多想想这个问题，来学会判断这种想法是否正确，于是准备结束这次讲座。

“现在请大家静一静。刚才林文的发言，既有实践基础，又有一定的推理，还敢对古希腊的神话传说提出质疑，这种精神是很好的。古人说过，‘学贵知疑，小疑则小进，大疑则大进’，敢于提出疑问，疑问解决了，知识就长进了。在考虑这个问题的时候，关键是引路线的作用。引路线除了可以指

示走出迷宫的路线外，还有没有别的作用？这个问题大家应当好好想一想。

“现在除了图２－１的迷宫平面图外，我再给大家一个青少年乐园的迷宫平面图（见图１－１），并且建议大家自己设计一些简单的迷宫，针对这些特例，进行钻研。然后，再回答：如果你是提修斯，身上带有一团足够长的线球，事先又没有见过平面图，你能否走遍迷宫的每条通道（这样当然就找到了那个怪物），再从原路出来？如果能，该怎么走？如果不能，原因是什么？以后我们再来讨论。

“最后顺便提一下，古希腊神话传说是世界文学宝库的财富之一，今天我们看到，理解文学作品，有时也需要有一定的数学知识。准备将来当文学家的同学们，同样也要学好数学啊！”

刘老师的一席话说得大家都乐了。

四　　什么叫做图？——刘老师的第二次讲座

“上次讲座，我给大家介绍了两个迷宫的平面图（图１－１，图２－１），并且请你们研究了我们提出的游迷宫问题。不少同学告诉我，看了迷宫的平面图使人眼花缭乱，很不好研究。确实是这样的。今天我要给大家介绍一个工具，它叫做‘图’。利用‘图’的知识，我们能把迷宫问题转化为一个‘图’的问题，也就是说，把一个实际问题化成一个数学问题。”

什么是图？

“大家可能会说：‘图’是什么还用介绍吗？迷宫的平面图不就是一个‘图’吗？《三毛流浪记》一整本漫画不也都是‘图’吗？错了，我们这里所说的‘图’指数学的一个分支——‘图论’中的专有名词。它跟迷宫的平面图、函数的图象和图画的图是不同的。让我们先看一些例子。

【例１】假设有５个人，分别记作Ａ、Ｂ、Ｃ、Ｄ和Ｅ。在这５个人中，设

Ａ、Ｂ两人互相认识；

Ｂ、Ｃ两人互相认识；

Ａ、Ｃ两人互相认识；

Ｂ、Ｄ两人互相认识；

Ｃ、Ｅ两人互相认识。

“我们可以用一个几何图形表示上面提到的５个人以及他们的‘认识’关系：每一个人用一个小圆圈表示；如果有两个人互相认识，就把表示这两个人的小圆圈用一条线段连起来，那么这５个人和他们之间的相互认识关系就可以表示成图４－１了。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００２３＿１．ｂｍｐ｝图４－１

“如图４－１所画的图形就叫做一个‘图’。组成‘图’的小圆圈Ａ、Ｂ、Ｃ、Ｄ、Ｅ叫做图的顶点。联结顶点的那些线段叫做图的边。如果ＡＢ是图的一条边，我们说顶点Ａ和顶点Ｂ相邻，边ＡＢ与顶点Ａ和Ｂ关联，顶点Ａ和Ｂ是边ＡＢ的端点。

“从上面的例子中我们看到，在理解‘图’这个概念的时候，应当注意：１．图的顶点的位置可以随便画。

２．图的边可以画成直线段，也可以画成曲线段，并且画长画短都没有关系。关键的是，一个图中有几个顶点（有几个人），哪些顶点间有边相连（哪些人互相认识）。

３．图的两条边可能在非顶点的地方相交，这时候它们的交点不是图的顶点。如图４－１中，顶点只有５个，应该把边ＢＤ想象为跨过边ＡＣ和ＣＥ。所以，画一个‘图’的时候，顶点一定要用小圆圈表示，以免和两条边的不是顶点的交点相混淆。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００２４＿１．ｂｍｐ｝

“这样，我们也可以把图４－１画成图４－２，它同样表示例１中的５个人和他们之间的认识关系。

【例２】设有一个表示篮球队循环赛的图，如图４－３所示，它的一个顶点表示一个篮球队。如果两个篮球队已经比赛过了，就在图４－３表示这两个篮球队的顶点间连一条边。你们能不能说说看，图４－３中表示几个篮球队？

哪两个篮球队间已经进行过比赛？哪些篮球队间还没有进行过比赛？”

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００２５＿１．ｂｍｐ｝

同学们七嘴八舌地回答，刘老师都听见了，她说：“对的！图４－３中有６个篮球队Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ。其中，Ａ、Ｂ；Ａ、Ｃ；Ａ、Ｆ；Ｂ、Ｃ；Ｂ、Ｅ；Ｂ、Ｆ；Ｃ、Ｄ；Ｃ、Ｅ；Ｄ、Ｅ；Ｅ、Ｆ间都比赛过。而Ａ、Ｄ；Ａ、Ｅ；Ｂ、Ｄ；Ｃ、Ｆ；Ｄ、Ｆ间还没有比赛过。

“下面再看一个例子：

【例３】用一个顶点表示一个市（县），两个市（县）间如有直达公路相连，就把这两个顶图４－４点用一条线段连起来。那么图４－４所表示的交通图也是一个图。

“从上面三个例子看出，一个图就是由一些顶点和这些顶点之间的一些边组成的图形。我们以后所讨论的图中的顶点数和边数都是有限个的，这种图也叫做有限图。一个图的顶点可以表示一个人、一个球队或一个城市，当然也可以表示其他事物。而边呢？它可以表示顶点所表示的事物间的某种关系。例如用顶点表示城市，用边表示城市间有公路相通的关系等等。

“由于顶点可以表示很多东西，边可以表示这些东西间的一种关系，所以我们就可以把图的知识应用于研究多种事物和它们各自的关系。例如我们要研究的迷宫，现在就可以用图来表示了。

“在游迷宫问题中，我们关心的是可以从哪个岔路口（或碰壁的绝点）走到哪个岔路口（或绝点）。因此，我们可以把迷宫中的每个岔路口和绝点用一个顶点来表示，如果两个岔路口（绝点）有一条通道相通，就在这两个顶点间连一条边。这样我们就能用一个图来表示一个迷宫了。下面我用一个简单的迷宫作例子来说明这种表示方法（图４－５）。

“设有一个迷宫（图４－５（ａ）），我们先把所有岔路口和绝点标上英文字母（图４－５（ｂ）），再把有通道的顶点用边连起来（图４－５（ｃ）），这样，就得到迷宫的一个图（图４－５（ｄ）），把它画得更顺眼一些，就得到图４－５（ｅ）。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００２７＿１．ｂｍｐ｝

“现在请你们不要看黑板，自己在笔记本上把图１－１和图２－１的迷宫用图表示出来。”

这时，大家都动起手来，刘老师也在黑板上画出图１－１和图２－１两个迷宫相应的“图”（图４－６（ａ）和（ｂ））。

同学们把两个迷宫的平面图用“图”表示后，发现像图２－１那样复杂的迷宫，用图来表示（图４－６（ｂ））竟是那样简单，感到十分惊讶。大家开始对图的作用有了一点体会。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００２８＿１．ｂｍｐ｝图４－６

刘老师接着说：“现在我们的游迷宫问题，就变成了诸如在图４－６所表示的图中，从顶点Ａ出发，走遍图中每条边至少一次，再回到Ａ应当怎么走的问题了。”

图的一些名词？

为了以后讨论问题的时候说话简洁方便，需要介绍一些跟图有关的名词。

１．重边

如果我们有一个图（图４－７）表示Ａ、Ｂ、Ｃ三个排球队的比赛情况。两个队间赛过一场，就在表示这两队的顶点之间连一条边，赛过二场，连二条边……赛过几场，就连几条边。假设Ａ、Ｂ间赛过两场，Ａ、Ｃ间赛过五场，而Ｂ、Ｃ间刚刚赛了一场，那么上面的比赛情况就表示成图４－７所示的图。

这时，我们称图４－７中顶点Ａ、Ｂ间有二重边，Ａ、Ｃ间有五重边。其他的重边情况仿这个规定命名。

２．简单图

今后我们常用大写英文字母表示图中的顶点，用小写字母ｅ加上足码记边。图４－８（ａ）、（ｂ）、（ｃ）都表示一个图。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００２９＿１．ｂｍｐ｝

注意到图４－８（ａ）中边ｅ３是两个端点重合在一起的边，这种边叫做环。｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００３０＿１．ｂｍｐ｝

如果一个图既无环，又无二重和二重以上的重边，这种图叫做简单图。在图４－８中，（ａ）、（ｂ）不是简单图，（ｃ）是简单图；在图４－６中图４－８（ａ）、（ｂ）都是简单图。

３．路

在图４－９所示的图中，如果我们从Ａ出发，沿边ｅ１走到Ｂ，再从Ｂ沿边ｅ９走到Ｅ，从Ｅ又沿ｅ４走到Ｄ。我们就说这是一条从Ａ到Ｄ的路（图４－１０），记作

Ｐ＝Ａｅ１Ｂｅ９Ｅｅ４Ｄ。

在一个简单图中，路也可以只用顶点来记。图４－９是简单图，所以刚才这条路可记为

Ｐ＝ＡＢＥＤ。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００３１＿１．ｂｍｐ｝图４－９图４－１０

实际上，这里“路”的概念跟我们平常走路的路的概念是很类似的。在一条路中，顶点和边都允许重复经过。例如下述的ｐ１和ｐ２都是图４－９所表示的图中的路：

Ｐ１＝Ａｅ１Ｂｅ８Ｆｅ５Ｅｅ９Ｂｅ２Ｃ

这条路经过顶点Ｂ两次，即在路ｐ１中顶点Ｂ出现两次。

ｐ２＝Ｇｅ１１Ａｅ１Ｂｅ８Ｆｅ６Ａｅ１Ｂｅ２Ｃ。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００３１＿２．ｂｍｐ｝

这条路经过顶点Ａ、Ｂ各两次，也经过边ｅ１两次（见图４－１１（ａ）和图４－１１（ｂ））。

４．回路

如果一条路的起点和终点重合，这条路就叫做一条回路。下面写出的ｐ１、ｐ２、ｐ３都是图４－９中所示的图的回路。为了容易看清楚，我们分别再画在图４－１２中。

ｐ１＝Ａｅ６Ｆｅ８Ｂｅ１Ａ（图４－１２（ａ））；

Ｐ２＝Ａｅ７Ｃｅ３Ｄｅ４Ｅｅ１０Ｃｅ２Ｂｅ１Ａ（图４－１２（ｂ））；

Ｐ３＝Ａｅ６Ｆｅ８Ｂｅ９Ｅｅ５Ｆｅ８Ｂｅ１Ａ（图４－１２（ｃ））。

５．连通图

设Ａ、Ｂ是图中的两个顶点。如果在Ａ、Ｂ间有一条路，我们称Ａ、Ｂ两个顶点在这个图中是连通的。

如果一个图中任意两个顶点都是连通的，那么我们称这个图是连通图。换句话说，如果一个图是连通图，那么从图中随便一个顶点出发，都可以经过某一条路走到任意的一个顶点去。

我们看到，图４－６中表示迷宫的两个图都是连通图。要是这两个图不是连通图，那么我们从Ａ进去，就无法走遍迷宫的每条边，从而迷宫问题无解。所以今后在讨论迷宫问题时，我们总假设它的图是连通图。

如果表示一个迷宫的图中有回路，将表明游迷宫的人有可能一直绕着回路走而兜圈子。图４－６中的两个图都有回路，进入这两个迷宫的人，都有可能迷路。

刘老师介绍的这些图的名词，大家都感到很直观，很容易理解。刘老师接着说：“有了图的概念，你们去研究游迷宫问题就方便多了。现在我们假设怪物米诺陶就住在图２－１的迷宫的某处，请你们回去研究一下，提修斯带着一个线球能不能找到这个怪物并从迷宫入口出来？如果能找到，他该怎么走？下一次我们举行一次讨论会来讨论这个问题。要是你们有兴趣的话，可以做几个练习，用以加深对图这一新概念的理解。”说着，刘老师留下了几道练习题。

练习一

１．一中初三有Ａ、Ｂ、Ｃ三个班；二中初三也有三个班Ａ′、Ｂ′、Ｃ′。两校初三年级联合举办一次篮球友谊赛，规定每校的一个班级代表队要和另一个学校的三个班级代表队各赛一次。如果友谊赛已结束，试用一个图表示这次友谊赛中，哪些队和哪些队进行过比赛。

２．下图中顶点Ａ、Ｂ、Ｃ分别表示三个工人；Ａ′、Ｂ′、Ｃ′、Ｄ′分别表示四项不同的工种。如果工人Ａ能干工种Ｂ′，则在Ａ、Ｂ′间连一条边，其余类推。试通过图指出，各工人能干一些什么工种？

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００３４＿１．ｂｍｐ｝

３．下图中各顶点代表一种电器元件。如果Ａ、Ｂ两元件间必需用导线接通，则在Ａ、Ｂ间连一条边。试通过图指出这个电器系统有几个元件？哪些元件间必须用导线接通？

４．以上各题中，哪些图是连通图？哪些图不是连通图？

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００３５＿１．ｂｍｐ｝

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００３５＿２．ｂｍｐ｝

５．试把下列迷宫用图表示出来。

（２）

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００３６＿１．ｂｍｐ｝

五　　提修斯怎样找到怪物米诺陶？

——解迷宫问题的方法一

按照刘老师的建议，这次数学爱好者协会的活动以讨论会的形式进行。讨论的题目是：

提修斯怎样找到怪物米诺陶？

黄杰上次听了林文的发言，本来就不太同意他的看法，但是讲不出个道理来。经过刘老师的启发，加上有了图的工具，他回去后认真地研究了图４－６（ｂ）的图和自己编的一些简单的连通图，一边试验，一边总结规图５－１律，终于想出了办法。他举手要求第一个发言。得到刘老师的同意后，他先在黑板上画了一个表示图２－１迷宫的图（图５－１），并把顶点和边标上符号。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００３８＿１．ｂｍｐ｝

他的发言要点如下：

１．由于不知道怪物米诺陶藏在迷宫的什么地方，所以提修斯要想找到它，必须想出一个能走遍图５－１每条边至少一次的办法才行。

２．引路线的作用，不仅可引导提修斯按照原路走出迷宫，而且可以指出哪些边走过了（这些边上布有引路线），哪些边还没走过（这些边上没有引路线）。

上次林文同学的发言中忽略了引路线的第二个作用，才使他怀疑提修斯能找到米诺陶。其实只要注意到引路线的第二个作用，提修斯一定能找到米诺陶（当然要假设米诺陶不在迷宫里跟提修斯捉迷藏。这个假设是合理的，因为当时米诺陶并不知道提修斯要去杀它）。提修斯可以这样走：进迷宫的门后，不断寻找没走过的边继续走，直到没有这种边的时候为止。这样，他就把图５－１的所有边都至少走过一遍了，然后再按原路走出来。

黄杰说：“根据上面的想法，我在图４－６的两个图和其他一些连通图上都反复试过，找到了一种游迷宫的办法，其步骤是：

１．从入口Ａ任选一条边走到一个新顶点。

２．当到达一个顶点Ｘ的时候，如果Ｘ与一些未走过的边相关联，就任选一条未走过的边走到另一个顶点Ｙ；如果到达顶点Ｘ的时候，所有和Ｘ关联的边都已走过了，那就按原路返回。

３．在返回的途中，还可能遇到有的顶点关联一些未走过的边，这时，从这些边中任选一条，继续按步骤２的办法走。如果从某点返回到Ａ的途中，没有发现任何一个和顶点（包括Ａ）有关联又未走过的边，就可从Ａ出来了。

“返回途中，是有可能遇到有的顶点关联一些未走过的边的。例如在图５－１中，我们从Ａ出发，沿ｅ２走到Ｃ，再沿ｅ４走到Ｅ，从Ｅ走到Ｇ，以后一直往前走。当我们返回的时候，就在顶点Ｅ遇到ｅ６还没走过，到达顶点Ｃ的时候，就会发现ｅ３还没走过。

“我按上面说的办法，试过好多连通图，不管是图４－６中的（ａ）或（ｂ），或者是其他连通图，都能走遍图中所有的边再从Ａ出去。”

接着他举出两个例子来说明这一方法。第一个例子，使用一个比较简单的连通图，第二个例子，就用图５－１的图。在这两个例子中，都假设Ａ是迷

宫入口。

【例１】在图５－２中按上述方法解迷宫问题：

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００４１＿１．ｂｍｐ｝

解：（１）从Ａ出发，沿ｅ１走到Ｂ；由于Ｂ关联两条图５－５未走过的边，按步骤２可任选一条，例如沿ｅ２走到Ｃ；从Ｃ沿ｅ５走到Ｅ；Ｅ关联未走过的边ｅ４、ｅ６，按步骤２从中任选一条，如沿ｅ６走到Ｆ；同样道理，沿ｅ８走到Ｈ（图５－３）。

（２）在顶点Ｈ，没有关联未走过的边，按步骤２沿原路返回。沿ｅ８返回的时候，途经Ｆ，发现ｅ７未走过。按步骤３，沿ｅ７走到Ｇ（图５－４）。

（３）在顶点Ｇ，没有关联未走过的边，按步骤２，顺原路返回，即走下面的路：

Ｇｅ７Ｆｅ８Ｈｅ８Ｆｅ６Ｅｅ（图５－５）。

（４）到Ｅ后，发现与Ｅ关联的边ｅ４还没走过，于是按步骤３，沿ｅ４走到Ｄ，再沿ｅ３走到Ｂ（图５－６）。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００４２＿１．ｂｍｐ｝图５－６

（５）走到Ｂ后，发现跟Ｂ关联的所有边都已走过了，按步骤２，顺原路返回，即走下面的路：

Ｂｅ３Ｄｅ４Ｅｅ６Ｆｅ８Ｈｅ８Ｆｅ７Ｇｅ７Ｆｅ８Ｈｅ８Ｆｅ６Ｅｅ５Ｃｅ２Ｂｅ１Ａ。

在这次返回过程中，没有发现和任何一个顶点（包括顶点Ａ）有关联未走过的边，于是我们从Ａ出来。

上述走法，就是从Ａ进去，走遍图中每条边至少一次，再从Ａ出来的一种走法。

【例２】在图５－１中按上述方法解迷宫问题。

解：（１）从Ａ进去，有两条边ｅ１、ｅ２可走，我们从中任选一条边走，例如选ｅ１，接下去，仿例１的分析，我们可以走出如下的一条路（图５－７）：

Ａｅ１Ｂｅ１Ａｅ２Ｃｅ４Ｅｅ６Ｆｅ６Ｅｅ５Ｇｅ８Ｈｅ１０Ｊｅ１１Ｉｅ７Ｇ。

（２）到Ｇ后，由于和Ｇ关联的所有边都走过了，于是按原路返回：从Ｇ沿ｅ７走到Ｉ。这时，发现和Ｉ关联的ｅ９还没走过，于是从Ｉ沿ｅ９走到Ｈ，由于和Ｈ关联的所有边都走过了，于是按原路返回：

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００４３＿１．ｂｍｐ｝图５－７

Ｈｅ９Ｉｅ７Ｇｅ７Ｉｅ１１Ｊ。

（３）在Ｊ点，发现边ｅ１２还没走过，于是可按下法走：

Ｊｅ１２Ｋｅ１４Ｍｅ１４Ｋ。

（４）在顶点Ｋ发现ｅ１３还没走过，于是从Ｋ经ｅ１３。到Ｌ。

（５）在顶点Ｌ，由于和Ｌ关联的边都已走过，于是按原路返回。这次可以顺原路线一直返回到Ｃ，然后经ｅ３到Ｄ。

（６）同理，到Ｄ后，按原路线返回。这次返回到Ａ的途中，不会遇到关联未走过边的顶点，所以能一直返回到Ａ，并从Ａ出来。

同学们认真地听了黄杰介绍的办法后，都按这个办法在笔记本上试验，尽管走的路线不一样，但最终确实都走遍图中的每一边并且从Ａ出来。

一个新的问题产生了，有的同学提出：黄杰总结的方法对图５－１和图５－２

是可行的，对其他连通图是否也一定可行？怎么证明这一点？对这个问题，黄杰一时也答复不出来。

刘老师意识到，这个新问题的提出，说明同学们的思维往更深的层次发展了，这是一个十分可喜的现象。但是要对这一方法作一般证明，可能是同学们力所不及的。于是她决定亲自出马。

她首先肯定了黄杰的发言。她说，黄杰同学从实验入手，从特例中探索走法，总结规律，从而提出了一种解迷宫问题的方法。这个方法，如果用游迷宫的普通语言可以叙述如下：

游迷宫的方法一：

１．进入迷宫后，可以任选一条通道往前走。

２．碰壁就返回。

３．到达一个叉路口，观察是否有还没走过的通道，如果有，就任选一条往前走；如果没有，就顺原路返回到下一个叉路口，重复２和３。

４．由原路返回迷宫入口处的时候，跟入口相连的各通道都已走过了，就从入口处出来。这时，迷宫里的每条通道都至少走过一次了。

这方法不仅对图５－１和图５－２等特殊的图可行，而且我们可以证明对任一连通图都可行，即

１．按照这个方法，的确能从Ａ进去，再回到Ａ。

２．按照这个方法，从Ａ出来的时候，每条边都已被走过至少一次。她说：“如果我们证明了这二点，那么方法一就成为一个正确的一般方法了。

“如果上面这二点还没有证明，那么方法一还只能说是一个从实验、归纳得出的猜想。实验—归纳—猜想—证明，这是我们探索问题的一种常用方法，今后我们还要通过具体例子，再说明这种探索问题的方法。

“我们休息十分钟，然后我来介绍方法一的证明。下面是两个练习题，有兴趣的同学回去后可以试一试。”

练　习　二

１．试按游迷宫方法一，找出青少年乐园迷宫的一条游迷宫路线。

２．试按游迷宫方法一，各找出练习一第五题中两个迷宫的一条游迷宫路线。

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

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

前面已经说过，要证明方法一是正确的，必须证明以下两点：

１．按照方法一，确能从迷宫入口Ａ进去，再回到Ａ；

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

要证明第一点是很容易的，因为按方法一第１点，我们从Ａ进去，又按方法一的第２、第３点，我们在图中的某顶点没有边需要再走的时候，就按原路返回。按原路返回的意思就是说，原来从Ａ怎么走到那里的，就从那里倒过去顺着原路走回到Ａ，因此按方法一，最后一定又回到Ａ。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００４８＿１．ｂｍｐ｝图６－１

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

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

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

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

为了让大家容易理解，我们一边看图６－１，一边来说定理１的证明。设图６－１中的粗线是我们已走过的路ｐ，其他不在ｐ上的边（细线）是没走过的。我们任取一条未走过的边，例如ＭＫ，当然也可能是ＤＣ或ＧＩ等等。我们所取的这条未走过的边有两种可能情况：

（１）这条边有一个端点是Ｐ中的顶点（例如ＧＩ的两个端点就都是Ｐ的顶点），这时我们的问题就已经解决了；

（２）这条边的两个端点都不是Ｐ的顶点（例如ＭＫ），我们从这两个端点中任取一个端点（例如ＭＫ中的Ｍ）。由已知，图是连通的，所以在Ｐ中任取一个顶点（例如Ｇ），一定能使这两个点（例如Ｇ和Ｍ）之间有一条路（例如ｐ１＝Ｇｅ８Ｈｅ１０Ｊｅ１２Ｋｅ１４Ｍ）。

由于Ｇ在ｐ中，Ｍ不在ｐ中，所以沿路ｐ１中的边从Ｇ走到Ｍ，总会经过至少一条不在Ｐ中的边（如ｅ１２，ｅ１４），那么，沿ｐ１从Ｇ走到Ｍ遇到的第一条未走过的边（ｅ１２），就是我们要找的既不在Ｐ中（未走过）而又有一个端点（Ｊ）在Ｐ中的边。① 对这一段证明，如果你感到比较困难，可以跳过去不看。对以后比较深的证明内容都可跳过去不看。

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

有了定理１，我们确信解迷宫问题的方法一是普遍可行的正确方法。刘老师最后说：“我们现在已经找到解迷宫问题的一个方法了，但这个方法好不好，大家还可以回去考虑和实践。今天的讨论会就开到这里。”

七　　小探险家再游迷宫

有了解迷宫问题的方法一，小虎子重游迷宫的劲头来了。这次黄杰也很积极，因为他也想实践一下他提出的游迷宫办法。于是三个好朋友又凑在一起，商量重游迷宫的计划。

黄杰自告奋勇要准备一团线球。他笑着对小虎子说：“去年风筝线是你准备的，这次的线球由我来准备吧！”

林文摇摇头说：“今非昔比，这一团线得好几百米呢！我们是不是一定要像提修斯一样带个线团去游迷宫呢？记得格林童话中有这样一个故事：亨舍尔和格莱特兄妹二人的继母把他们领到森林里，想遗弃他们。聪明的亨舍尔预先知道继母的阴谋，在去森林的前一天晚上，口袋里装了许多小圆石，第二天他一路走一路把小圆石丢在路上。以后就顺着这些小圆石找到了家。这些小圆石的作用也就是引路线的作用，我们是不是也想个办法来‘改革’一下引路线呢？”

“好主意！”小虎子脱口而出，“我看到的探险小说里的主人公也有用一种作路标的办法标明路线的。”

三个人你一言我一语讨论引路线的改革。

小虎子早就筹划重游迷宫，也考虑到如何解决引路线问题，林文的建议对他启发很大。他联想到上次看到的游宫说明里有一条说可以领取粉笔一支，不禁恍然大悟，经过进一步考虑，终于想出了一个代替线团的办法。他说：“记得上次游宫说明中有一条说可以领取粉笔一支，我又记起迷宫中每堵墙的两头都嵌有一块黑板。迷宫的设计师显然已经替我们考虑过可以用粉笔在墙上作记号。所以，我们可从出发的墙上画一个箭头，编上号，到达岔路口的墙上也画一支箭头并连续编号，这就表明我们从哪里开始走，到达哪里，再往哪里继续走。这些箭头，我想可以代替引路线的作用了。”

小虎子提出的这一改革办法，得到大家一致的赞同。他们先在表示青少年乐园迷宫的图上用小箭头试画了一小段路（图７－１），感到完全可行。于是他们又约定星期日下午再次游迷宫。

这次三个小探险家已是心中有数。他们不慌不忙地领了一支粉笔，进入迷宫。小虎子建议从“引人入胜”门进去。于是他们在ＡＫ墙上画了一个箭头编为１号。以后往前走到Ｋ，到达Ｋ的时候，他们在这堵墙的另一端画了第二个箭头，标上２号（图７－２）。现在按方法一有两条路可走，他们继续走向Ｌ，并在ＫＬ墙上画了第三个箭头，标上３。就这样，一直接方法一走，一边走，一边画箭头、编号。在图７－２中我们画出了他们实际路线的一部分。箭头编到第４０号的时候，虽然到了入口Ａ，但因不是按原来由Ａ出发的路（标有１号箭头的ＡＫ）返回Ａ，所以他们没从Ａ走出去，而是返回Ｂ，这样，箭头继续编到第６４号。接下去按方法一，他们又应往回走。往回走的时候，正好在每个顶点上都没有未走过的边。因此，他们一直顺着这６４个箭头的相反方向一个个走下去，一边走，一边仍继续编号，一直编到第１２８号，正好对上１号箭头。这说明他们的确是按原路返回了Ａ。这时他们看到在入口处的每堵墙上都已有了箭头，说明所有跟入口相关联的通道都已经走过了。因此，他们确信已游遍了迷宫的每条通道，高兴地走出迷宫。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００５４＿１．ｂｍｐ｝图７－１

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００５５＿１．ｂｍｐ｝

这次游迷宫，虽然不像上次迷路那样紧张，但是却也走得很累。他们发现有的边要走４次、８次，重复的路走得太多了，这也许是这个方法的一个大毛病吧。因此他们都在想：能不能有一种少走冤枉路的办法呢？

他们把实践的情况和问题向刘老师作了汇报。刘老师夸奖他们用粉笔画筋头代替线团的“技术革新”，同时同意他们关于方法一缺点的看法。她说：“重复路走得太多，确实是这方法的最大缺点，你们游迷宫的图有１５条边，一条边走过一次要编２个号码，你们编了１２８个号，说明每条边平均走４次以上。这不是个好办法。我们还有一个每条边刚好只需走２次的办法。这个方法跟欧拉图有关，欧拉图又跟著名的哥尼斯堡七桥问题的故事有关……”

“什么是欧拉图？”

“什么是哥尼斯堡七桥问题？”

“新方法该怎样走？”

大家迫不及待地问。

“别急，下一次讲座，我就准备向你们介绍哥尼斯堡七桥问题和欧拉图的有关知识。哥尼斯堡七桥问题还很有趣味呢！”

大家听了刘老师有条不紊的讲座计划，非常满意地离开了。

八　　哥尼斯堡七桥问题和欧拉图——刘老师的第三次讲座

“上次我们已经讨论了一种游迷宫的方法，但是许多同学都发现这办法不太好，因为走的重复路太多。我准备给大家再介绍一种方法，用这种方法游迷宫，其中的每条边刚好来回走两次。为了介绍这个方法，我们需要有欧拉图的知识。现在我先给你们讲个故事。”

哥尼斯堡七桥问题

“十八世纪时，东普鲁士有个城市叫哥尼斯堡，它就是原来苏联的加里宁格勒。这个城市有一条河叫普雷格尔河，它穿过这个城市，河中有两个小岛，这四块陆地间有七座桥相连（图８－１）。当地居民喜欢在那里散步。久而久之有人提出了这样一个问题：是否能设计一条散步路线，使得一个人从家里（四块陆地中某块的某处）出发，走过每座桥恰好一次，然后回到原来出发的地方？

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００５８＿１．ｂｍｐ｝图８－１

“很多人对这个问题感到兴趣，试了好多次都没有成功。到底有没有这样的散步路线呢？当时谁也回答不出来。最后这个问题传到当时的大数学家欧拉那里，他研究了这个问题，并在一七三六年发表了《哥尼斯堡的七座桥》的论文。这篇论文，后人认为是《图论》的第一篇论文。

“现在我们来看看，应当怎样来研究这个问题。

“我们先把图８－１中的四块陆地分别记为Ａ、Ｂ、Ｃ和Ｄ。我们关心的是哪些陆地间有桥相通，有几座桥相通，至于陆地Ａ、Ｂ、Ｃ、Ｄ有多大，桥有多长都是无关紧要的。因此我们能把Ａ、Ｂ、Ｃ、Ｄ都各看成一个顶点，Ａ跟Ｂ有两座桥相连，图８－２（ａ）就在Ａ、Ｂ间连两条边（图８－２（ａ）），其他仿此处理，我们就把图８－１的地图表示成为一个图（图８－２（ｂ））。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００５９＿１．ｂｍｐ｝

“这样，设计哥尼斯堡七桥散步路线的问题，就转化为图８－２（ｂ）的图能否从任一顶点出发，不重复地一笔画完这个图，再回到原出发顶点的问题了。这个问题以后简称一笔画问题。

“一笔画的游戏，大家小时候可能都做过，现在我们用图论的名词，把它的意思说清楚。

“如图８－３，这个图能从顶点Ａ出发，不重复地一笔画完（即从Ａ出发再回到Ａ）。我们可以这样画：

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００６０＿１．ｂｍｐ｝图８－３

“从Ａ经ｅ１到Ｂ，经ｅ２到Ｃ，经ｅ３到Ｄ，经ｅ４到Ｂ，经ｅ５到Ｆ，经ｅ６到Ｄ，经ｅ７到Ｅ，经ｅ８到Ｆ，最后经ｅ９回到Ａ。按照图论的名词，上面说的实际上是一条回路：

ｐ＝Ａｅ１Ｂｅ２Ｃｅ３Ｄｅ４Ｂｅ５Ｆｅ６Ｄｅ７Ｅｅ８Ｆｅ９Ａ，

这条回路有两条性质：

（１）图中的每条边都在Ｐ中出现；

（２）图中的每条边都只在Ｐ中出现一次。

“为了纪念欧拉，后人称具有上述两条性质的路叫做欧拉路，而具有上

述两条性质的回路叫做欧拉回路。如果一个图有一条欧拉回路，就称这个图为欧拉图。

“上面我们说的是：一个图如能从任意一个顶点出发，不重复地一笔画完，再回到出发点，那么这个图就是欧拉图。反之，如果一个图是欧拉图，也就是说，它存在一条欧拉回路，那么从图中任意一个顶点出发，沿这条回路都能不重复地一笔画完这个图，再回到原出发点。

“因此，说‘一个图是欧拉图’和说‘一个图能从任一顶点出发不重复地一笔画完这个图，再回到原出发点’，这两种说法是完全一样的。

“现在我们提出一个问题：给你一个图（例如图８—２（ｂ）、图８—３）你怎么知道它是否欧拉图？解迷宫问题的另一方法，就跟这个问题有关。”

怎么知道一个图是否是欧拉图？

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００６１＿１．ｂｍｐ｝

“让我们先动手做一些试验。请你用笔画画试试，看看图８—４中的哪些图是欧拉图，哪些图不是欧拉图？请你边做试验，边想想其中的道理。”

同学们好像参加智力竞赛一样，纷纷在笔记本上画了起来。小虎子很快发现（ａ）、（ｃ）不是欧拉图，（ｂ）、（ｄ）、（ｆ）是欧拉图。但对（ｅ），他画来画去，总找不出一条欧拉回路来，但是又不敢断定它不是欧拉图。偏巧刘老师提问了他。

“陈虎，你的试验结果怎样？”刘老师问。

陈虎忐忑不安地站起来答道：

“图（ｂ）、（ｄ）、（ｆ）是欧拉图，因为我们可以通过一笔画找到一条欧拉回路。”说着他到黑板上画出了这三

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００６２＿１．ｂｍｐ｝图８—５

个图的欧拉回路（图８—５）。

“另外，（ａ）不是欧拉图，这是因为它没有回路；（ｃ）也不是欧拉图，因为我们如果从顶点Ａ出发走到Ｂ（图８—６），那么要回到Ａ，必然要重复走ＢＡ，因此不存在不走重复边的回路，即它没有欧拉回路，所以它不是欧拉图。至于图（ｅ），我还判断不了它是否是欧拉图。”

“你刚才说的，实际上包含着一般的思考方法。”刘老师在启发小虎子，“要肯定一个图是欧拉图，必须找到一条欧拉回路，如（ｂ）、（ｄ）、（ｆ）。如果要否定一个图是欧拉图，只需找到一个顶点，说明从它出发，不可能不重复地一笔画完这个图，再回到这个顶点，如你刚才举的图（ｃ）中的顶点Ａ。这个思考方法是很正确的。现在你再按这个思考方法观察图（ｅ）中的顶点Ａ（图８—７）。”

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００６３＿１．ｂｍｐ｝

小虎子从刘老师的提示中想到，从图８—７中的Ａ出发，一定不能不重复地一笔画完这个图，再回到Ａ。这是因为Ａ和三条边关联，从Ａ沿一条边出去，从另一条边回到Ａ，再从Ａ沿第三条边出去，最后就不能不重复地走这三条边中之一，再回到Ａ了。

“我想到了，图（ｅ）也不是欧拉图。”小虎子把上面的想法说了出来。刘老师点点头。然后又问：“你现在从（ｂ）、（ｄ）、（ｆ）是欧拉图和（ａ）、（ｃ）、（ｅ）不是欧拉图，能不能总结出一个图是欧拉图和非欧拉图

的本质原因是什么吗？”

小虎子是很聪明的，他略一思索就说：

“哦！我知道了！不是欧拉图的图，一定有一个顶点关联奇数条边，这样，从这顶点出发要回到这个顶点，不重复走一条边是办不到的。从是欧拉图的图（ｂ）、（ｄ）、（ｆ）来看，它们都没有这样的顶点，这也许就是欧拉图和非欧拉图的一条重要的本质区别。”

平常比较不善于观察总结的小虎子，今天能找到这两种图的主要特点，刘老师十分高兴。她请小虎子回到座位，并且说：

“刚才陈虎同学已从几个特例的试验，总结出欧拉图和非欧拉图的一条本质区别，他的看法是对的。在图８—４中，（ａ）、（ｃ）、（ｅ）都至少有一个顶点关联奇数条边，这种图不是欧拉图。在（ａ）、（ｃ）、（ｅ）中添了一些边，变成（ｂ）（ｄ）（ｆ），这三个图中各个顶点关联的边数都是偶数条，就都成了欧拉图。但是还要注意，非连通图一定不是欧拉图。下面准备把我们刚才的探索结果总结一下。为了说话方便起见，我们引入两个名词：

“奇顶点：图中的一个顶点，如果关联奇数条边，管这顶点叫奇顶点。“偶顶点：图中的一个顶点，如果关联偶数条边，管这顶点叫偶顶点。“现在通过探索，我们能提出如下猜想：

“一个连通图是欧拉图■图中所有顶点都是偶顶点。

“为什么只能说是猜想呢？这是因为上面的结果只是从几个特例归纳得到的，还没经过一般证明。当我们作了一般证明之后，上面的猜想就成为一个定理了。”

关于欧拉图猜想的证明

“一个连通图是欧拉图■图中所有顶点都是偶顶点。

“我们先证明如果一个图是欧拉图，那么它的所有顶点都是偶顶点。“这点证明很简单。如果一个图是欧拉图，那么从图中任一顶点出发，能不重复地一笔画回到这一点。这是一条欧拉回路，这条回路进出图中的每个顶点都是偶数次，并且进出的边都是不同的。所以，图中的每一个顶点都是偶顶点。

“现在再来证明，如果一个连通图的所有顶点都是偶顶点，那么这个图一定是欧拉图。

“证明的方法是：对给定的所有顶点都是偶顶点的连通图，具体找出一条欧拉回路来。这条回路找出来了，就证明这个图是欧拉图了。

“为了使大家容易理解，我结合一个具体的图来讲。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００６６＿１．ｂｍｐ｝

“假设我们有一个连通图，它的所有顶点都是偶顶点（例如图８—８）。我们任取一个顶点记作ＤＡ。从Ａ出发，如图８—８下走出一条边不重复的路：从Ａ沿任一边走到另一顶点，记作Ｂ。因Ｂ是偶顶点，必定还有一条和Ｂ关联的边还没走过，我们从这条边走到Ｃ。同理，由于Ｃ也是偶顶点，所以和Ｃ关联的边中也一定还有一条未走过的边，我们沿这条边走到另一顶点Ｄ。仿此做下去，由于经过一个顶点的时候，进出的边数成双，所以这条路只要到达一个不是Ａ的顶点，就一定还有一条和这顶点关联的未走过的边，我们可以从这条边出去。因为图中的边数是有限的，我们每次所走的边又应是不同

的，所以这条路不能无限止地走下去，而必须在某一顶点停止。这停止的顶点不能是Ａ以外的顶点，因为对Ａ以外的顶点，路线经过它时有一条进去的边，由于它是偶顶点，必然还有一条边未走过，从而可从这条边走出去。可见这条路必须在顶点Ａ停止。即我们将走出一条回路，不妨把它记作Ｐ（在图８—８中，ｐ＝ＡＢＣＤＢＥＦＡ）。

“假如Ｐ已走遍图中的所有边，而且因为我们走的边都是先前没走过的，可见这些边都是不同的。这样Ｐ就是一条欧拉回路，从而我们证明了这个图是欧拉图。

“假如图中还有一些边没被Ｐ走到。由于图是连通的，从第六章定理１知道，Ｐ中有某个顶点（例如图８—８中的Ｅ），关联某条未走过的边。由于Ｅ是偶顶点，所以和Ｅ关联的未走过的边的数目一定仍是偶数条。同理，在图中任一顶点关联的未走过的边都是偶数条。这样，从Ｅ出发，正像从Ａ出发一样，又可找到一条回路Ｐ′，它走过图中一些不同的未走过的边再回到Ｅ（见图８—９，在这图里，ｐ′＝ＥＧＨＥ）。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００６８＿１．ｂｍｐ｝

“现在我们可从Ａ出发，沿Ｐ的一部分先走到Ｅ（如图８—９为ＡＢＣＤＢＥ），到了Ｅ后，沿ｐ′走回Ｅ（ＥＧＨＥ），然后继续走完Ｐ剩下的一部分回到Ａ（ＥＦＡ）。这样，由Ｐ和ｐ′合起来的回路ｑ就比Ｐ走过更多的边了（图８－９中ｑ＝ＡＢＣＤＢＥＧＨＥＦＡ）。如果ｑ走遍整个图，它就是一个欧拉回路，我们也就证明了给定的图是欧拉图。如果ｑ还没走遍全图，我们又能仿照上面的办法把ｑ再扩大。由于图的边数有限，扩大有限次后，一定能找到一条回路，它走遍了整个图的边，而且由于每次走的时候，都是走未走过的Ｇ边，所以这条回路中的边都不相同。可见最后这条回路是一条欧图８－９拉回路。这也就证明了所给的图是欧拉图。

“这样，我们就得到了一个定理：

〔定理２〕一个连通图是欧拉图■这个图所有的顶点都是偶顶点。

“回顾我们探索怎样的一个图是欧拉图的过程，我们再一次看到如何通过特例的实验，归纳总结规律，提出猜想，最后再给以证明的过程。这种探索问题的办法是很有用的。今后大家在学习中应当学会使用这种办法。

“应用定理２，我们很容易判别一个图是否欧拉图。这只要看看所给的图中是否有奇顶点就可以了。现在我们回到哥尼斯堡七桥问题上来。在这个问题中，能否设计一条散步路线从陆地的某处出发，走遍每座桥恰好一次再回到原出发点，相当于问图８－２（ｂ）是否欧拉图。由于这个图中有４个奇顶点，所以它不是欧拉图，可见这样的散步路线是设计不出来的。这也就是欧拉那篇论文的答案。

“定理２有许多实际应用。下次讲座我将介绍如何利用定理２来研究游迷宫问题，探索一个比方法一少走冤枉路的方法。今天的讲座就到这里为止。”

听完这次讲座，大家都感到收获很大。因为有些同学过去玩过一笔画游戏，以前大家老是一个图一个图去试，不懂得去探索规律，现在有了刘老师介绍的定理２，随便拿一个图就能很快判别它是否能一笔画回到原出发点了，而且还知道怎样去画它。此外，大家还从这件事得到很大的教育，学习了实验——归纳——猜想——证明的探索问题的方法。从这里，大家更觉得刘老师循循善诱，既教给大家知识，又教给大家研究问题的方法，他们对刘

老师更加爱戴了。下面是刘老师留下的练习。

练习三

１．下列各图，哪些图能从任一顶点出发，走遍图中每条边恰好一次再回到原出发点？

２．一个至少有两个顶点的连通图，假如要从顶点Ａ出发，走遍图中的每条边恰好一次到达另一顶点Ｂ（这种从Ａ到Ｂ所走过的路即欧拉路），这个图各顶点关联的边数应有什么特征？请你作出猜想并加以证明。

（１）｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００７０＿１．ｂｍｐ｝

（２）｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００７１＿１．ｂｍｐ｝

（３）｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００７１＿２．ｂｍｐ｝

３．在哥尼斯堡七桥问题中，请你添一座桥，使得能从一个小岛出发，走过每座桥恰好一次到达另一小岛。

４．下图表示一个十五座桥的问题。图中的英文字母表示陆地。问：（１）能否从某地出发，走过每座桥恰好一次再回到该地？

（２）能否从某地出发，走过每座桥恰好一次而终止于另一地？

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００７１＿１．ｂｍｐ｝

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

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

“一个连通图是欧拉图■这个图所有的顶点都是偶顶点。

“现在我们要利用它来研究游迷宫问题。我们知道，图９－１（ａ）表示图２－１的迷宫。图９－１（ａ）除Ａ以外所

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００７３＿１．ｂｍｐ｝图９－１

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

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

解迷宫问题方法二的猜想

“我们还是从对具体的、特殊的迷宫作实验分析入手，然后加以归纳，猜想它的一般走法规则，最后给以证明。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００７４＿１．ｂｍｐ｝图９—２

“我们先以一个比较简单的连通图为例来进行分析，这个图如图９－２所示，Ａ表示迷宫入口。

“１．在图９－２中，从Ａ进入迷宫后，先走哪条边呢？因为进入迷宫后，如有好几条和Ａ关联的边可走，这些边对我们来说，地位都是完全平等的，哪一条也不特殊，所以我们可猜想，可以任意选一条边走。

“２．假设我们从Ａ沿ｅ２走到Ｃ，那么回来的时候，就应当从Ｃ沿ｅ２走到Ａ。这样，在边ｅ２上刚好走了两个相反的方向。由此我们猜想，对其他边来说，每条边刚好走两次，可能也应要求是走两个不同的方向。

“３．当我们从Ａ沿ｅ２走到Ｃ后，类似１的分析，照理可在ｅ３、ｅ４和ＣＡ中任选一边走，但是ＣＡ的方向有点特殊性：ｅ３和ｅ４的两个方向都没有走过，而ｅ２的ＡＣ方向已经走过了。在什么样的情况下，才允许我们沿ＣＡ的方向走回Ａ呢？这是应当考虑的。显然，我们应当要求除了Ｃ到Ａ的方向外，所有和Ｃ关联的边的两个方向都走完了，才能从Ｃ回到Ａ。否则，如果和Ｃ关联的某条边的某方向（例如ＣＥ）尚未走过，我们就从Ｃ走到Ａ，那么为了再走和Ｃ关联的那条边（ＣＥ），还需要从Ａ再走到Ｃ，这样，ｅ２就不止走两次了。由此我们又猜想，当从Ａ到ｃ后，应在ｅ３和ｅ４中任选一条边走，而不应当沿ＣＡ走回Ａ。一般地，我们可作如下猜想：当从某个顶点Ｘ第一次走到一个新顶点Ｙ时，只在和Ｙ关联的所有边的两个方向都走过了，才最后走从Ｙ到Ｘ

的方向回到Ｘ。这条猜想很重要，因为如果按这条办法做，当我们从一个顶点往回走的时候，能保证跟这顶点关联的所有边都已走过两次了。

“４．按上面三条猜想，我们已能一直往前走了。如果我们走回到Ａ的时候，能否就出去呢？还不能，因为ｅ１还没走过。所以在一般情况下，当到达进口处的时候，还要看看和进口关联的所有边的两个不同方向是否都已走过了，如果都已走过了，才可以走出来。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００７６＿１．ｂｍｐ｝

“要实践上面几条游迷宫的猜想，必须有一种方法，能标记哪条边的哪个方向已经走过了，以及当游到一个新顶点的时候，是从什么地方来的。在实践游迷宫方法一的时候，陈虎等几个同学已经想出一种画箭头的办法，用它标记从哪个顶点到达哪个顶点，这是一个好办法，现在我们也可以用。当我们从Ａ沿ｅ２往Ｃ走的时候，在Ａ处，沿ｅ２画一个箭头；到达Ｃ时，也在ｅ２旁画一个箭头。因为顶点Ｃ第一次走到，ＣＡ的方向应当留待和Ｃ关联的其他边的两个方向都走过了才走。所以到达Ｃ的箭头应有特别标记，我们约定使用双箭头（如图９—３）。

“现在我们有了走法的猜想和标记方法，就可以用一些图试试看。在试的过程中，如发现有考虑不周到的地方，再修改补充。如果你动手试一试，就会发现上面的猜想是可以达到预定目的的。这样，我们就把这些猜想整理成几条规则，然后再设法证明这些规则的正确性。”

解迷宫问题方法二的规则（猜想）：

１．每一条边应走两个不同方向，如果一条边的两个方向都走过了，就不再走了；

２．从一个顶点Ｘ第一次走到一个新的顶点Ｙ，只在和Ｙ关联的其他所有边的两个方向都走过了，才最后从Ｙ到Ｘ的方向走回来；

３．从入口Ａ可任选一条边走，以后凡是到达一个顶点的时候，可以从没走过的任意一条边走，如果没有这种没走过的边时，可以选择一条只走过一次的边，按相反方向走。当然，根据第２条，第一次到达这个顶点的边的相反方向应该最后走。

４．当到达迷宫入口Ａ的时候，如果和Ａ关联的所有边的两个方向都走过了，就可以从Ａ出去了。

“现在我们先举例说明我们的走法规则，最后才给以证明。先看图９－２的图。

“在顶点Ａ，有两条和Ａ关联的边未走，按规则３，可任选一条，例如选ｅ２，沿ＡＣ方向从Ａ走到Ｃ。我们在Ａ旁沿ＡＣ方向画一箭头，到达Ｃ的时候，也画一箭头。因为我们第一次到达Ｃ，所以这一箭头应画成双箭头（图９—４）。

“在顶点Ｃ，又有两条和Ｃ关联的边未走。按规则３，可任选一条，例如选ＣＤ，跟前面一样作箭头（图９—５）。

“在顶点Ｄ，没有未走过的边，所以按ＣＤ的相反方向走回到Ｃ（图９—６（ａ））。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００７８＿１．ｂｍｐ｝图９—４图９—５

“实际上，顶点Ｄ是迷宫中碰壁的绝点。这在实际游迷宫的时候是很容易辨认的。对于绝点，必然要回头，所以在实际游迷宫的时候，绝点Ｄ旁的两个箭头可以不必画出（见图９—６（ｂ）），但在Ｃ旁的两个箭头要画出，

它表明从顶点Ｃ往Ｄ的两个方向都已走过，而下次不必再走了。以后遇到绝点，我们都同样处理。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００７９＿１．ｂｍｐ｝图９—６

“从Ｄ回到Ｃ后，由规则２不能走ＣＡ，而应走ＣＥ到Ｅ，下面假设从Ｅ到Ｆ到Ｇ再走到Ｅ（图９—７）。由于从Ｇ到Ｅ是第二次到Ｅ，所以这个箭头不必画成双箭头。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００７９＿１．ｂｍｐ｝图９—７

“现在在顶点Ｅ，由于和Ｅ关联的三条边都画有一个箭头，说明都走过一次了，已经没有一个方向都未走过的边。因此，按规则３，选择一条走过一次的边按相反方向走。按规则２，不能走ＥＣ的方向回来；按规则１，不能再走ＥＦ的方向。于是只能从ＥＧ走回到Ｇ。到达Ｇ后，由于还有一条边两个方向都没走过，所以由Ｇ走到Ｈ（图９—８）。Ｈ是绝点，返回Ｇ，由于ＧＥ的两个方向都走过了，ＧＨ两个方向也都走过了，由规则２，我们沿跟第一次到达Ｇ的方向的相反方向ＧＦ返回。下面依同理，从Ｆ到Ｅ到Ｃ到Ａ。在Ａ处，由于发现ＡＢ还没走过，所以不能就从Ａ出去，而应从Ａ到Ｂ，再从Ｂ返回Ａ。这时，跟Ａ关联的ＡＣ和ＡＢ边的两个方向都已经走过了，才从Ａ出来。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００８１＿２．ｂｍｐ｝

“从图９—８我们看到，迷宫中的每条通路，确实两

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００８１＿１．ｂｍｐ｝图９—９

个不同方向都刚好走过了。”

接着，刘老师让同学们在笔记本上用方法二画出图９—１（ａ）的游迷宫路线，下面就是小虎子作出的一条游迷宫路线：

ＡＢＡＣＥＧＨＪＩＧＩＨＩＪＫＬＫＭＫＪＨＧＥＦＥＣＤＣＡ（见图９—９）。

在同学们掌握了游迷宫方法二规则的基础上，刘老师开始讲解方法二的证明。

解迷宫问题方法二的证明

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

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

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

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

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

（１）当我们停止在Ａ时，按规则３，和Ａ关联的每条边都按出去的方向走过了。否则，我们还应继续走而不能停止。

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

（３）按规则１，如果一条边按两个相反方向走过了就不再走了，所以跟Ａ关联的每条边，刚好走过两个相反方向而不会多走。

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

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

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

十　　小探险家三游迷宫

在“五四”青年节的下午，小虎子的班级到青少年乐园举行纪念活动。在自由活动时间里，我们的三个小探险家第三次游了迷宫。这次他们仍和第一次一样，商定兵分两路，小虎子从“引人入胜”门进去，林文和黄杰从“渐入佳境”门进去，约定在门口会师。下图（图１０—１）是小虎子的游宫路线。

他是这样走的：

ＡＫＬＫＧＦＨＧＩＧＨＭＨＪＨＦＥＢＣＤＣＥＣＢＡＢＥＦＧＫＡ。

林文和黄杰的走法如图１０—２。

他们的走法是：

ＡＢＣＥＢＥＦＧＫＡＫＬＫＧＩＧＨＪＨＦＨＭＨＧＦＥＣＤＣＢＡ。

在门口会师的时候，他们完全满意了，回忆起第一次游迷宫时的狼狈情景，禁不住哈哈大笑起来。｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００８６＿１．ｂｍｐ｝

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００８７＿１．ｂｍｐ｝图１０—２

练　习　四

１．试用解迷宫问题的方法二，各找出练习一第５题中两个迷宫的一条游宫路线。

２．有一座迷宫如下页图所示，Ａ是入口，Ｘ是出口，迷宫的图是连通的。（１）能否用解迷宫问题的方法二，找到一条从Ａ到Ｘ的路线，如能，请你找出一条来；

（２）如果有一个人在Ｙ处迷了路，问他能否用解迷宫问题的方法二找到出路？如能，请你帮他找一找。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００８８＿１．ｂｍｐ｝

十一　　各有所获

班上最新一期的《学习园地》出版了。我们三位小主人公的学习心得体会都被选入。

下面这一段是摘自小虎子的心得体会：

“通过这段时间参加数学爱好者协会游迷宫问题的讲座活动，使我学到了游迷宫的两个方法。将来要是真的到一个迷宫似的山洞里去探险的时候，再也不会像第一次游迷宫时那么糊里糊涂地乱闯了，当然也不会像提修斯那样，带着一大团线球进去。从这里，我体会到学习数学的重要性。通过正确的数学思考方法的训练，能使人思考问题周密细致，此外，应用数学知识还能帮助我们找到解决问题的最好办法。现在一想起第一次游迷宫的情景，我就感到惭愧。看来，做任何一件事，都应当先好好想想，周密地考虑一下怎样做才行，否则就不可能做好。这对我不太爱动脑筋、莽莽撞撞的坏习惯来说，是一个很好的教训……”

下面这一段引自林文的心得体会：

“最使我想不到的是，文学作品中也包含着数学知识。《水浒》我看过不只一遍，就没有想到盘陀路就是一座迷宫。《三国演义》是囫囵吞枣地看了一遍，更没注意到八阵图是怎么回事。现在重读这些章回，不仅倍觉亲切，而且理解也更深了一层。最近，我从图书馆找到了一本《希腊古代的神话传说》的小说，其中确实有刘老师所说的提修斯的故事，我起初还怀疑提修斯是否会找不到那个怪物呢！我对文学很有兴趣，有时甚至想将来当个文学家，可是对数学却兴趣不浓，学习也不太用功，开始有了偏科的倾向。通过这段讲座活动，看来即使立志将来要当文学家，也必须努力学好数学。通过这段活动，我感到数学还是很有趣味的。另一方面，刘老师是教数学的，可她的文学知识多么丰富，故事说得多么引人入胜！因此，看来将来要学理工的，也要学好语文。总之，中学阶段是一个多么重要的全面打基础阶段啊！”

最后这一段是黄杰心得体会的一部分：

“我原以为数学就是几何、代数、三角和现在只是听说而还没有学到的解析几何、微积分。这段时间参加游迷宫问题的数学爱好者协会活动，使我开阔了眼界，增长了知识，不仅学会了游迷宫的具体方法，而且还学习了一些有趣的图论知识。刘老师还在讲座中结合具体问题，介绍了从一些特例着手，实验归纳一般规律，提出猜想并进而加以证明的探索问题的方法。我感到这套办法很好，对我很有启发，以前没有认真注意，今后在学习中应当有意识地运用，以加强自己探究问题的能力。所以这次活动，真是收获不少……”

亲爱的读者，你们读了这本书有些什么体会呢？

十二　　未结束的结束语

刘老师看了同学们自己办的学习园地上的文章后，在迷宫问题专题讲座的最后一次活动上，对这段活动作了小结。她回顾了所介绍的知识和探索问题的方法，并对同学们的心得体会作了评述。最后，她还说了下面这段似乎并未结束的结束语：

“在我们介绍游迷宫问题的同时，已经讲了图论的一些知识。这些知识是很初步的，因为实际上只介绍了几个最基本的概念和欧拉图的知识。尽管如此，我们已经看到图论知识在研究某些实际问题中的重要作用了。例如，一个眼花缭乱的迷宫用图表示之后就容易研究多了。

“我们所介绍的欧拉图知识，虽然是从一个古老的数学游戏中提出的，但是它却有一些实际应用。例如我们利用它导出了比解迷宫问题方法一好的方法二。假如将来你们要到一个大岩洞里去考察，只要有照明设备，带上粉笔就可以按方法二进洞考察了。如果以后你们要负责设计一个展览会，你可以把它设计成一座迷宫，把展品摆在通道的两旁，而引导观众参观的路线就按方法二设计，这样，观众们对每件展品刚好可参观一次。

“欧拉图的知识不仅用在解决迷宫问题上，而且还可以用来解决其他生产实际问题。山东师范大学的管梅谷教授在一九六○年为邮递员叔叔设计了一种最优的投递路线，在解决这个问题的时候也用到了欧拉图的知识。现在我把它简单介绍一下：

“假设有个邮递员要从邮局出发，走遍他所负责的街区的每条街道至少一次去投递邮件，然后再返回邮局，问应当怎样设计他的路线，才能使所走的路最短？

“如图１２－１中，邮局在Ａ处。我们把邮局和街道岔口、拐角都看成图的顶点，联结两个顶点的街道，当成图的边。那么图１２—１就是一个各边带有长度（长度注在边旁）的图。如果这个图的所有顶点都是偶顶点，按照前面的定理２，我们能找到一条欧拉回路，邮递员只要按这条回路走，就一定是最短的路线了。但是，图１２－１中有１８个顶点是奇顶点，所以它不是欧拉图。这样，邮递员要从Ａ出发走遍这个图的各条边再回到Ａ，一定要重图１２－１复走一些边才行。图论的知识进一步告诉我们：在一个图中如有奇顶点，其个数一定是偶数，即可配成双。这样，我们可把所有奇顶点一对对配好，并沿着图中的边连结起来，使有的边变成重边，那么新得的图（如图１２－２）就没有奇顶点了，它就可以从Ａ出发，再一笔画回到Ａ。

“在图１２－２中，变成二重边的那些边，就是邮递员必须重复走的街道。容易看出，怎样把一对对奇顶点连起来的办法不止一种，不同的连法，所重复的边不一定图１２—２一样长，而重复边的总长就是邮递员走重复路的长。那么到底应当如何把奇顶点一对对连起来，才能使邮递员重复走的路总长最短，是解决这个问题的关键。管梅谷教授提出并证明了一种办法，解决了这个问题。这个问题很著名，现在外国的图论学者都把它叫做‘中国邮递员问题’。

“应用中国邮递员问题的知识，不仅能设计邮递员叔叔的最优路线，而且还能设计最优的城市街道洒水车的巡回路线以及自动扫街车的巡回路线。欧拉图的知识能在这些实际问题中得到应用，你大概没想到吧！

“欧拉图仅仅是图论中讨论的问题之一。在图论中还讨论许多在国民经

济中有重要应用的知识。我们举两个例子：

“‘最短（长）路问题’，这个问题是研究如何在每条边都附有长度的一个图中（如图１２－１），找出任意两个顶点间的最短路（或最长路）。在设计一个费用最省的石油（自来水、煤气）管道路线或制定运费最省的物资运输计划的时候就要用到这种知识。此外，如果我们要完成一项工程，往往要做许多事，而每件事之间又有先后次序和完成时间，我们可以把每件事情用一条有方向的边表示，这样，一项工程就能用一个边带有方向的图来表示。这时最短（长）路的知识就能用来帮助我们制订最快完成工程的计划。解放军叔叔还用这些知识来制订作战计划呢！

“‘平面性问题’。这个问题是研究怎样的图能画在一个平面上，使每条边除顶点外不再相交。无线电工程师设计了一个新的电视机线路图后，就要用这方面知识考虑它能不能在一个平面上制成印刷电路板。

“此外，电子计算机科学中也用到许多图论知识。

“图论的知识不仅很有用，而且它研究的一些问题还很有趣味。前面介绍的哥尼斯堡七桥问题和一笔画问题就是很好的例子。我这里再举一个有趣的问题——哈密尔顿周游世界问题。

“一八五九年英国数学家哈密尔顿发明了一种游戏。他在图１２－３的２０个顶点上，标上世界各大城市的名字。游戏者从某个城市（顶点）出发，沿图中的边寻找经过每个城市（顶点）一次且只一次再回到原出发城市的路线。这种路线，后人称为哈密尔顿回路。

“一般地说，哈密尔顿回路是经过图中每个顶点恰好一次的一条回路。如果一个图有一条哈密尔顿回路，这个图就叫做哈密尔顿图。由于图１２－３中的粗线

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿００９８＿１．ｂｍｐ｝图１２—３

是一个哈密尔顿回路，所以图１２－３就是一个哈密尔顿图。

“哈密尔顿周游世界问题是：任给一个图，怎样判断它是否是哈密尔顿图？

“这个问题和一笔画问题有惊人的类似处。一笔画问题是要判断任一个图是否有欧拉回路，而哈密尔顿周游世界问题是要判断任一个图是否有哈密尔顿回路。应该注意的是，欧拉回路是经过图中每条边恰好一次的回路，而哈密尔顿回路是经过图中每个顶点恰好一次的回路。由于这一点不同，导致两个类似问题有完全不同的难度。利用定理２可以轻而易举地判断一个图是否是欧拉图，但是哈密尔顿周游世界问题研究了一百多年至今还没解决。由于图论中有很多悬而未决的问题都跟哈密尔顿周游世界问题的解决有关系，所以目前还有许多数学家正在努力攻克这个问题。

“总而言之，游迷宫问题我们介绍完了，但是图论中还有许多在国民经济中有重要应用的知识，以及许多有趣的但还没解决的问题，有待将来有志于图论学习的同学去进一步学习和研究。”

在一阵热烈的掌声中，刘老师结束了她的讲话。

练习解答

练习一

１．

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿０１００＿１．ｂｍｐ｝

２．Ａ能干工种Ａ′、Ｂ′、Ｄ′；

Ｂ能干工种Ａ′、Ｂ′、Ｄ′；

Ｃ能干工种Ｃ′。

３．有五个元件；元件Ａ、Ｂ；Ａ、Ｃ；Ａ、Ｅ；

Ａ、Ｄ；Ｂ、Ｅ；Ｂ、Ｃ；

Ｃ、Ｄ；Ｃ、Ｅ必须用导线接通。

４．第１、３题的图是连通图；第２题的图不是连通图。

５．（１）

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿０１０１＿１．ｂｍｐ｝

（２）

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿０１０１＿２．ｂｍｐ｝

练　习　二

１．见“小探险家再游迷宫”。

２．游迷宫的路线如下：

（１）ＡＧＨＧＣＭＩＭＪＭＣＤＥＤＦＤＣＡＢ，然后再按原线路返回Ａ：ＢＡＣＤＦＤＥＤＣＭＪＭＩＭＣＧＨＧＡ。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿０１０２＿１．ｂｍｐ｝

（２）ＡＣＤＣＥＦＥＧＡＨＡＢＡＨＡＧＩＪＩＭＩＫＩ，然后再按上述路线的相反方向返回Ａ：ＩＫＩＭＩＪＩＧＡＨＡＢＡＨＡＧＥＦＥＣＤＣＡ。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿０１０２＿２．ｂｍｐ｝

练　习　三

１．（１）、（２）能；

（３）不能。

２．〔分析〕从Ａ出发后不回到Ａ，可见顶点Ａ应是奇顶点。同理顶点Ｂ也应是奇顶点。图中其余各顶点都是有一条边进去，再从另一条不同的边出来，所以都应是偶顶点。

〔猜想〕一个至少有两个顶点的连通图有欧拉路■图中恰有两个奇顶点。

〔证明〕

（１）若一个至少有两个顶点的连通图有欧拉路，则由〔分析〕中所说的道理，图中恰有两个奇顶点；

（２）若一个连通图恰有两个奇顶点Ａ、Ｂ，我们在Ａ、Ｂ间人为地添加一条边ＡＢ，则所得的新图无奇顶点。按定理２，知它有一条欧拉回路Ｐ，且Ｐ中含有这条增添的边ＡＢ。今在Ｐ中把边ＡＢ抹去后，便是一条从Ａ到Ｂ的欧拉路。

这样，上述猜想便成为一个定理。

３．如图，在Ａ、Ｃ间造一座桥，则它相应的图中，Ａ、Ｃ为偶顶点，Ｂ、Ｄ为奇顶点。由第２题知，可从Ｂ（或Ｄ）走遍每座桥恰好一次到达Ｄ（或Ｂ）。

４．十五座桥问题所对应的图如下：

在这个图中，顶点Ｄ、Ｅ为奇顶点，其余各顶点为偶顶点，所以：

（１）由定理２，不能从某地出发走遍每一座桥恰好一次，再回到该地。（２）由第２题，可以从Ｄ（或Ｅ）出发，走遍每一座桥恰好一次，终止于Ｅ（或Ｄ）。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿０１０４＿１．ｂｍｐ｝

练　习　四

１．下面是它们的一种走法：

（１）ＡＢＡＣＤＦＤＥＤＣＭＪＭＩＭＣＧＨＧＡＧＣＡ。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿０１０５＿１．ｂｍｐ｝

（２）ＡＣＤＣＥＧＡＨＡＢＡＧＩＭＩＫＩＪＩＧＥＦＥＣＡ。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿０１０５＿２．ｂｍｐ｝

２．本题迷宫相应的图如下，它是一个连通图。解迷宫问题的方法二，实际上能从一个连通图的任意一个顶点走到所有的顶点，所以用解迷宫问题的方法二，可从Ａ走到Ｘ，也可从迷路的Ｙ处走到入口Ａ或出口Ｘ，从这两个地方出去。

（１）

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿０１０６＿１．ｂｍｐ｝

（２）所走路线是：ＡＤＹＤＢＣＢＦＧＦＸ。

所走路线是：ＹＤＥＤＢＣＢＦＧＦＸ。

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿０１０６＿２．ｂｍｐ｝

当然，他也可能从入口Ａ出去，例如：

｛ｅｗｃ　ＭＶＩＭＡＧＥ，ＭＶＩＭＡＧＥ，　！１６０００２９０＿０１０６＿３．ｂｍｐ｝

所走路线是：ＹＤＢＡ。