前 言


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

一 小探险家一游迷宫


　　我们的故事发生在一座风景秀丽的滨海城市。这个市的青少年乐园里， 新近落成了一座奇巧的建筑物——迷宫。几天时间，吸引了很多很多的青少 年朋友。凡是游过迷宫的人，无不感到兴趣盎然。那些在迷宫里迷了路，吃 够了“绕圈子”、“碰壁”的苦头，最后拖着酸软的双腿走出迷宫的人，更 是津津乐道，准备重游。迷宫落成的消息，很快惊动了我们这本小书的主人 公之一——陈虎。
　　陈虎确实生得虎头虎脑，身体胖得像个一号电池。他正在念初中三年级， 同学们都叫他小虎子。他有很强的好奇心，爱看冒险小说，打算将来做个探 险家，只是他的性情比较急躁，行动莽撞。迷宫落成的消息使他兴奋异常， 他马上去约同班的好友林文和黄杰一起去“探险”一番。
　　林文和黄杰的性格比较文静。林文喜爱文学，黄杰却对数学特别感兴趣。 他们对迷宫的兴趣显然不如陈虎大，但是经不起好朋友绘影绘声的宣传，终 于同意星期天下午一道去游迷宫。
　　这是一个风和日丽的日子。三个小探险家来到了那座奇妙的建筑物前 面。那是一个边长约 30 米的露天正方形建筑物，大门的扁额上写着“迷宫” 二字。进出的游人不少，小虎子一下子就想闯进去，想不到衣角却被黄杰拉 住了。
“哎！哎！哎！看看说明再进去！”
　　原来黄杰一眼看见了墙上贴有“游宫说明”。这份说明实在跟公园的其 他说明大不一样，现抄录于下：
游宫说明 一、游迷宫是一种益智的数学游戏，敬请游客多动脑筋，十二岁以下儿
童如无年长者带领，谢绝游宫；
　　二、迷宫中心的标志是一尊半人半牛的希腊神像米诺陶，并备有休息处； 三、每个岔路口都有开关一只，如果迷路时需要问路，可掀开开关，将 有一张图纸详细指示你所在的位置和继续前进的方法，看完请即关闭开关，
图纸自行消失；
四、游客如需要，可领粉笔一支，以备游宫时使用。
迷宫管理处


　　我们的三个小探险家实在不明白第四条说明的意思，于是他们决定不予 理睬，开始走入进口。一进迷宫，首先见到的是两个精致小巧的拱门，一个 上方写着“引人入胜”，一个上方写着“渐入佳境”。三个小探险家犹豫了： 该从哪个门进去呢？小虎子早就跃跃欲试，他提议道：“既然一道门能‘引 人入胜’，一道门可以‘渐入佳境’，可能都是可以走的。咱们来个兵分两 路，一路去‘入胜’，一路走‘佳境’，比赛谁先到迷宫中心，你们看如何？” 这个富有挑战性的建议，马上得到其他两个人的一致赞同。他们商定陈虎从 “入胜”进去，林文和黄杰去探寻“佳境”。
　　他们探险的结果如何，我们等一下再说，现在先向读者介绍一下这座迷 宫的结构。为了便于说明，我们把它的平面图画在下面（图 1—1）。
　　
　　原来这座迷宫除了入口处有两个标有“引人入胜”和“渐入佳境”的拱 门外，里面都以装饰相同的墙壁隔成许多弯弯曲曲的走道。迷宫的设计师为 了迷惑游人，不仅在每个岔路口都造有拱门，而且明明走不通的绝路顶端， 也造了外形完全一样的假拱门，乍一看去，使人分不清真假。为了后面说明 方便，我们把“渐入佳境”的门记为甲，把“引人入胜”的门记为乙，并把 每个岔路口和绝路端点都标上英文字母，M 处是迷宫中心。
{ewc MVIMAGE,MVIMAGE, !16000290_0006_1.bmp}图 1-1 当然，我们的这三个小探险家是没有见过这张平面图的。 且说小虎子闯入“引人入胜”的拱门（图 1-1 中的乙），顺道走到了 K。
他想，既然要往迷宫中心走，看来要向右拐，但是当他走到 L 后，发现上当 了，原来 L 是一个假门。碰壁之后，只好退回来。以后他从 K 改道走到 G， 看到 F 处有个拱门，就连着穿过 G 和 F，顺道走到 H。经过这么几转，小虎子 开始晕头转向，心里发慌了。他把迷宫中心的方向搞反了，穿过 H 走到了 J。 这下子又碰了壁，于是倒退回来，经过 H 一直走到 F。这时的小虎子已经急 得满头大汗了。幸好，正当他狼狈不堪的时候，看见他的两个好朋友走过来
了。
　　原来他们两人进了“渐入佳境”（图 1-1 甲）的门，一直向中心进发， 想不到竟拐了几个弯才走到 E，更糟糕的是到了 E 以后，方向搞不清了。他 们糊里糊涂走到 D，碰了壁，退到 C，穿过 C 从拱门甲出来，转过身一看，坏 了！居然还是“渐入佳境”！他们知道这是未到中心先绕了一个圈子。以后 他们又从原路进去，走到 E，正在往 F 走的时候，看见小虎子在向他们招手 哩！
当他们互相报告了碰壁的经过后，这三个难兄难弟哈哈大笑起来。他们
决定启动开关问路，按照图纸的指示，终于到达了迷宫中心 M。在这里，他 们看到了一座小巧玲珑的假山，假山上有一尊牛头人身的怪物，看来这就是 米诺陶了。他们在这里的水泥椅上休息、谈笑，最后寻路出去。天哪！怎么 走出去又是一道难题！但是，我可以告诉读者们，他们最终都走了曲折的道 路出来了。至于有没有再打开开关，那就不得而知了。
在回家的路上，他们虽然有些疲劳，但还是十分兴奋地议论着：这座迷
宫确实是一个很奥妙的谜，既迷人又有趣。到底怎样自由进出迷宫呢？这是 大家共同产生的问题。小虎子主张设法搞一张迷宫的平面图来，这样就可以 按图游宫了。可是黄杰却不以为然，他说：“既然游宫说明中说游迷宫是一 个益智的数学游戏，也许这里要用到什么数学知识，才能解决呢。”林文还 补充了一个问题，那就是，迷宫中放一个半人半牛的怪物是怎么回事？他们 决定把这些问题带回去请教他们的数学老师。

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


　　他们的数学老师姓刘。当她听了这三位小探险家的“探险”故事和问题 以后，高兴地不住点头，并赞扬他们肯动脑筋提问题的好学精神。她说：“迷 宫问题是一个很有趣的数学游戏，而且游迷宫的思想和方法还有些实际应 用，比如，用现代电子计算机解题的一种搜索法就应用了游迷宫的思想；如 果将来你们要到一个新发现的岩洞里去考察，或者在地道里迷了路，就要用 到游迷宫的方法。如何寻找游迷宫的路线，确实能用数学知识来解决，可是 这些知识既不是几何，也不是代数和三角，通常不在中学数学课本里介绍， 它的名称叫‘图论’，是数学中的一个分支。但是，你们不必担心，只要使 用其中很初步的一些知识就能解决游迷宫问题。如果你们有兴趣，我可以通 俗地介绍给大家。”
　　黄杰一听，高兴得几乎跳起来，他说：“刘老师，那就请您在数学爱好 者协会里做几次讲座吧！”
刘老师欣然答应了下来。 游迷宫问题的专题讲座，吸引了很多同学，我们的三位小主人公当然也
参加了。下面是刘老师的第一次讲座。题目是：
　　　　　　　　　　　　神奇的迷宫 “我先给大家讲一个古希腊的神话传说。
　　“古希腊的克里特岛王米诺斯的王后生了一个半人半牛的怪物，取名米 诺陶。皇后为了保护这个怪物的安全，请希腊最有本领的建筑师代达罗斯造 了一座著名的迷宫。迷宫里有数以百计的狭窄、曲折、幽深的道路和使人眼 花缭乱的阶梯以及很多小房间。不熟悉路径的人一旦走进迷宫，就会因迷失 方向而走不出来。迷宫造成后，王后就把米诺陶藏在这座迷宫里。这个怪物 靠吃人肉为生，它不仅吃在迷宫里迷路的人，而且米诺斯王还强迫雅典人每 九年进贡七个童男、七个童女送到迷宫里给它吞食。这件事给雅典人民造成 了深重的灾难。当米诺斯王派使臣第三次到雅典索取贡品的时候，年轻的雅 典王子提修斯决心为民除害，自告奋勇和其他十三名童男童女一起去克里特 岛。雅典王虽然很伤心，却阻挡不住提修斯的决心，提修斯一行终于出发了。 当他被带去见米诺斯王的时候，引起了克里特岛王美丽、聪明的公主阿里阿 德尼的爱慕，她偷偷地送给提修斯一个线球，并教他把线球的一端紧紧地拴 在迷宫的入口处，然后放着线走进迷宫。她还给提修斯一把魔剑，用来杀死 怪物。提修斯得到公主的帮助，把童男童女带进迷宫，找到怪物，经过一番 激烈的搏斗，终于用魔剑把它杀死，然后顺着线路，把童男童女安全带出迷 宫，为雅典人民做了一件大好事。
　　“克里特岛迷宫的故事脍炙人口，一直为人们所传颂。一九○○年，英 国地质学家兼考古学家阿瑟·伊文思在这个岛的三米深的地层下，发现了一 座面积达二万四千平方米的宫殿遗址，共有一千二百到一千五百个房间，据 说这就是米诺斯迷宫的遗址。
　　“上面说的是古希腊关于迷宫的一个古代神话传说。在现实世界中，确 实有一种叫做迷宫的建筑物。迷宫建筑是建筑学中的一种学问，据说外国至 今还有一座建于一六九○年的迷宫，图 2-1 是它的平面图。
　　
　　“传说古罗马的埃德萨城也有一座迷宫，它建在一个巨大的山洞里，里 面不仅有走道、房间，而且还有迷惑人的阶梯，看上去以为是往上走的，走 一段后却发现是往下去的。
{ewc MVIMAGE,MVIMAGE, !16000290_0013_1.bmp} “所谓迷宫，通常是指包括许多被墙壁所围的曲折的道路、绝路（有的
还连着一些小房间）所组成的建筑物。青少年乐园新落成的那座建筑物，就 是一座迷宫，它的中心有一尊牛头人身的怪物，就取自提修斯的故事。不熟 悉路径的人进入迷宫，很容易迷路，绕了半天还走不出来。
　　“在我国的古典小说里，也有类似迷宫的记载。《三国演义》中有一段 描述东吴大将陆逊陷入诸葛亮的八阵图的故事：有一天，陆逊在进军途中， 到了一个叫渔腹浦的地方。看到诸葛亮过去布下的一个石阵，只见它四面八 方都有门户，陆逊以为这没什么奥妙，闯入石阵观看，只见怪石嵯峨〔cuóé〕， 横沙立土重叠如墙。一时间风声阵阵，天色渐暗，当他急着要往回走的时候， 却一直找不到出路，后来幸好一个老人引他出来。这个神奇的石阵看来就是 一座迷宫。
　　“你们一定都看过《水浒》。实际上，‘三打祝家庄’里所描写的‘盘 陀路’也是一种迷宫。要进入祝家庄只有通过盘陀路，而这种盘陀路是‘容 易入得来，只是出不去’的。第一次攻打祝家庄的梁山泊好汉吃尽了盘陀路 的苦头。他们‘走了一遭又转到这里’，弄得不少好汉被活捉，幸亏石秀侦 察得盘陀路的走法，才把兵马带了出去。
“我们再举一个现代的例子。大家看过电影《地道战》，那里的地道，
实际上也是神奇的地下迷宫，在抗日战争中，它起了很大作用。实际上，现 代的地下人防工事，也是一座座神奇的迷宫。
“前几天，我们班上有几位同学到青少年乐园的迷宫里‘探险’一番，
回来后向我提出了一个能不能用数学方法找出游迷宫路线的问题。这个问题 提得很好，但是他们提的问题还不够明确，我想把它说得更明确一点，即： “假设从迷宫的每个地方，可以走到任何一个地方，问如何从迷宫入口 进去，游遍迷宫的每一条通道至少一次，再从迷宫的入口出来？我们以后就
简称这个问题为游迷宫问题。
　　“游迷宫问题不仅是一个游戏，而且也有实用价值。当我们发现一个新 的岩洞，需要进去考察，这个岩洞就可能是一座迷宫，设计考察路线就要用 到游迷宫的知识；一个大型展览馆，也可以设计成一座迷宫，参观路线需要 设计得使每个观众恰好经过每件展品一次。这些都要用到游迷宫的知识。
　　“关于这个问题的条件，还需要补充几句。有的同学可能在儿童杂志的 数学游戏栏里见过游迷宫的游戏。你可能会想到，如果手中有一张迷宫平面 图，那么仔细观察一下就能从图中找到一条所需要的路线，按找出的路线走 就很容易了，何必用到数学知识呢？
　　“的确是这样的，如果有了平面图，就很好办了。但是，如果你要到一 个新发现的山洞里去探险，那是什么平面图也没有的。我们的条件就是要在 没有平面图的情况下来研究游迷宫问题。黄杰等几个同学已经试过了，在没 有见到平面图的情况下，进入迷宫，到处都是装饰一样的墙壁，拐几道弯就 迷失了方向。看来，如果没有一套办法，是很难游遍迷宫再出来的。”
　　刘老师讲到这里停了一下，问大家是否把我们要讨论的问题弄清楚了？ 大家回答都清楚了。刘老师让大家休息一会儿，然后再初步议论一下如何来
　　
解决这个问题。

三 林文的怪论


　　刘老师的讲座一开头就把同学们带进了古今中外神秘莫测的迷宫世界 里，引起了同学们的极大兴趣，以致在休息的时候这些故事还萦回在他们的 脑际。他们三三两两地议论着，男同学们崇拜提修斯的勇敢无畏，女同学们 却更赞佩阿里阿德尼的聪明机智。更有不少同学想到青少年乐园的迷宫里实 践一下，所以我们的三位小主人公就忙得不亦乐乎，因为同学们知道他们游 过迷宫，都要他们介绍经验哩！
　　小虎子本来就直言快语，更拗（niù）不过同学们的请求，于是向大家介 绍了青少年乐园的迷宫和他们三个人游迷宫的经过。最后，他说了一句话：“我 们差点碰扁了鼻子。”这话引起了一阵哄堂大笑。
　　笑声伴随着铃声，同学们又回到了教室。刘老师等大家静下来以后，开 始提出问题：
　　“刚才我们介绍了游迷宫问题，接下去我们要考虑如何来解这个问题， 关于这方面，大家有些什么想法没有？”
不少同学举手要求发言，小虎子也是其中的一个。 “好！陈虎同学，谈谈你的看法。” “我想我们能否也像提修斯一样，带一个线团去游迷宫。” “你怎么利用这一团线团呢？”刘老师进一步问。 “我们也把它的一端拴在门口，然后放着线直冲进去。”陈虎的话逗得
大家都笑了起来。
　　刘老师对这个回答是不够满意的。她感到陈虎考虑问题太粗糙。于是她 请陈虎坐下，并且说：
“陈虎同学的思考太简单化。请不要忘记我们的目标是游遍迷宫的每个
地方，如何靠线团的帮助，使我们能走遍迷宫的每个地方，是需要仔细考虑 的问题。”
这时，林文要求发言，得到刘老师的同意后，他说：
　　“我认为提修斯带一个线球好像不能解决游迷宫问题。提修斯的线球只 能保证他按原路走出迷宫，但是要走遍迷宫的每个地方就有困难了。那一天 我们三个人去游迷宫的时候，我和黄杰从‘渐入佳境’的门进去，陈虎从‘引 人入胜’的门进去，大家都没找到米诺陶就相遇了，可见迷宫中有绕圈子的 路。如果提修斯也遇上这种路，他岂不是也在迷宫里老绕圈子。这样，他可 能找不到米诺陶就只好顺着线走出来了。所以，希腊神话中所说的提修斯找 到怪物并把它杀死，我有点怀疑，这也许缺乏科学根据。”
　　这真是一通怪论！林文发言后，教室里顿时活跃起来。有的同学原先认 为带个线球可以解决问题的，现在在重新思索；有的同学不大同意林文的观 点，却一时说不清理由。刘老师对林文的看法感到意外，她略微思索了一下， 就找到了问题的症结所在。虽然她发现林文的想法是不对的，但是，她为有 这样思想活跃的学生感到高兴。她感到，有必要让学生们多想想这个问题， 来学会判断这种想法是否正确，于是准备结束这次讲座。
　　“现在请大家静一静。刚才林文的发言，既有实践基础，又有一定的推 理，还敢对古希腊的神话传说提出质疑，这种精神是很好的。古人说过，‘学 贵知疑，小疑则小进，大疑则大进’，敢于提出疑问，疑问解决了，知识就 长进了。在考虑这个问题的时候，关键是引路线的作用。引路线除了可以指
　　
示走出迷宫的路线外，还有没有别的作用？这个问题大家应当好好想一想。 “现在除了图 2-1 的迷宫平面图外，我再给大家一个青少年乐园的迷宫 平面图（见图 1-1），并且建议大家自己设计一些简单的迷宫，针对这些特 例，进行钻研。然后，再回答：如果你是提修斯，身上带有一团足够长的线 球，事先又没有见过平面图，你能否走遍迷宫的每条通道（这样当然就找到 了那个怪物），再从原路出来？如果能，该怎么走？如果不能，原因是什么？
以后我们再来讨论。 “最后顺便提一下，古希腊神话传说是世界文学宝库的财富之一，今天
我们看到，理解文学作品，有时也需要有一定的数学知识。准备将来当文学 家的同学们，同样也要学好数学啊！”
刘老师的一席话说得大家都乐了。

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


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

什么是图？

“大家可能会说：‘图’是什么还用介绍吗？迷宫的平面图不就是一个
‘图’吗？《三毛流浪记》一整本漫画不也都是‘图’吗？错了，我们这里 所说的‘图’指数学的一个分支——‘图论’中的专有名词。它跟迷宫的平 面图、函数的图象和图画的图是不同的。让我们先看一些例子。
【例 1】假设有 5 个人，分别记作 A、B、C、D 和 E。在这 5 个人中，设 A、B 两人互相认识；
B、C 两人互相认识； A、C 两人互相认识； B、D 两人互相认识； C、E 两人互相认识。
“我们可以用一个几何图形表示上面提到的 5 个人以及他们的‘认识’
关系：每一个人用一个小圆圈表示；如果有两个人互相认识，就把表示这两 个人的小圆圈用一条线段连起来，那么这 5 个人和他们之间的相互认识关系 就可以表示成图 4-1 了。
{ewc MVIMAGE,MVIMAGE, !16000290_0023_1.bmp}图 4-1
　　“如图 4-1 所画的图形就叫做一个‘图’。组成‘图’的小圆圈 A、B、 C、D、E 叫做图的顶点。联结顶点的那些线段叫做图的边。如果 AB 是图的一 条边，我们说顶点 A 和顶点 B 相邻，边 AB 与顶点 A 和 B 关联，顶点 A 和 B 是边 AB 的端点。
“从上面的例子中我们看到，在理解‘图’这个概念的时候，应当注意：
1.图的顶点的位置可以随便画。
　　2.图的边可以画成直线段，也可以画成曲线段，并且画长画短都没有关 系。关键的是，一个图中有几个顶点（有几个人），哪些顶点间有边相连（哪 些人互相认识）。
　　3.图的两条边可能在非顶点的地方相交，这时候它们的交点不是图的顶 点。如图 4-1 中，顶点只有 5 个，应该把边 BD 想象为跨过边 AC 和 CE。所以， 画一个‘图’的时候，顶点一定要用小圆圈表示，以免和两条边的不是顶点 的交点相混淆。
{ewc MVIMAGE,MVIMAGE, !16000290_0024_1.bmp} “这样，我们也可以把图 4-1 画成图 4-2，它同样表示例 1 中的 5 个人
和他们之间的认识关系。
　　【例 2】设有一个表示篮球队循环赛的图，如图 4-3 所示，它的一个顶 点表示一个篮球队。如果两个篮球队已经比赛过了，就在图 4-3 表示这两个 篮球队的顶点间连一条边。你们能不能说说看，图 4-3 中表示几个篮球队？
　　
哪两个篮球队间已经进行过比赛？哪些篮球队间还没有进行过比赛？”
{ewc MVIMAGE,MVIMAGE, !16000290_0025_1.bmp} 同学们七嘴八舌地回答，刘老师都听见了，她说：“对的！图 4-3 中有
6 个篮球队 A、B、C、D、E、F。其中，A、B；A、C；A、F；B、C；B、E；B、 F；C、D；C、E；D、E；E、F 间都比赛过。而 A、D；A、E；B、D；C、F；D、
F 间还没有比赛过。 “下面再看一个例子：
　　【例 3】用一个顶点表示一个市（县），两个市（县）间如有直达公路 相连，就把这两个顶图 4-4 点用一条线段连起来。那么图 4-4 所表示的交通 图也是一个图。
　　“从上面三个例子看出，一个图就是由一些顶点和这些顶点之间的一些 边组成的图形。我们以后所讨论的图中的顶点数和边数都是有限个的，这种 图也叫做有限图。一个图的顶点可以表示一个人、一个球队或一个城市，当 然也可以表示其他事物。而边呢？它可以表示顶点所表示的事物间的某种关 系。例如用顶点表示城市，用边表示城市间有公路相通的关系等等。
　　“由于顶点可以表示很多东西，边可以表示这些东西间的一种关系，所 以我们就可以把图的知识应用于研究多种事物和它们各自的关系。例如我们 要研究的迷宫，现在就可以用图来表示了。
“在游迷宫问题中，我们关心的是可以从哪个岔路口（或碰壁的绝点）
走到哪个岔路口（或绝点）。因此，我们可以把迷宫中的每个岔路口和绝点 用一个顶点来表示，如果两个岔路口（绝点）有一条通道相通，就在这两个 顶点间连一条边。这样我们就能用一个图来表示一个迷宫了。下面我用一个 简单的迷宫作例子来说明这种表示方法（图 4-5）。
“设有一个迷宫（图 4-5（a）），我们先把所有岔路口和绝点标上英文
字母（图 4-5（b）），再把有通道的顶点用边连起来（图 4-5（c）），这样， 就得到迷宫的一个图（图 4-5（d）），把它画得更顺眼一些，就得到图 4-5
（e）。
{ewc MVIMAGE,MVIMAGE, !16000290_0027_1.bmp} “现在请你们不要看黑板，自己在笔记本上把图 1-1 和图 2-1 的迷宫用
图表示出来。”
　　这时，大家都动起手来，刘老师也在黑板上画出图 1-1 和图 2-1 两个迷 宫相应的“图”（图 4-6（a）和（b））。
同学们把两个迷宫的平面图用“图”表示后，发现像图 2-1 那样复杂的
迷宫，用图来表示（图 4-6（b））竟是那样简单，感到十分惊讶。大家开始 对图的作用有了一点体会。
{ewc MVIMAGE,MVIMAGE, !16000290_0028_1.bmp}图 4-6 刘老师接着说：“现在我们的游迷宫问题，就变成了诸如在图 4-6 所表
示的图中，从顶点 A 出发，走遍图中每条边至少一次，再回到 A 应当怎么走 的问题了。”

图的一些名词？


　　为了以后讨论问题的时候说话简洁方便，需要介绍一些跟图有关的名 词。
　　
1.重边
　　如果我们有一个图（图 4-7）表示 A、B、C 三个排球队的比赛情况。两 个队间赛过一场，就在表示这两队的顶点之间连一条边，赛过二场，连二条 边??赛过几场，就连几条边。假设 A、B 间赛过两场，A、C 间赛过五场，
而 B、C 间刚刚赛了一场，那么上面的比赛情况就表示成图 4-7 所示的图。 这时，我们称图 4-7 中顶点 A、B 间有二重边，A、C 间有五重边。其他
的重边情况仿这个规定命名。
2.简单图
　　今后我们常用大写英文字母表示图中的顶点，用小写字母 e 加上足码记 边。图 4-8（a）、（b）、（c）都表示一个图。
{ewc MVIMAGE,MVIMAGE, !16000290_0029_1.bmp}
注意到图 4-8（a）中边 e3 是两个端点重合在一起的边，这种边叫做环。
{ewc MVIMAGE,MVIMAGE, !16000290_0030_1.bmp} 如果一个图既无环，又无二重和二重以上的重边，这种图叫做简单图。
在图 4-8 中，（a）、（b）不是简单图，（c）是简单图；在图 4-6 中图 4-8
（a）、（b）都是简单图。
3.路
在图 4-9 所示的图中，如果我们从 A 出发，沿边 e1 走到 B，再从 B 沿边
e9 走到 E，从 E 又沿 e4 走到 D。我们就说这是一条从 A 到 D 的路（图 4-10），
记作
P＝Ae1Be9Ee4D。
　　在一个简单图中，路也可以只用顶点来记。图 4-9 是简单图，所以刚才 这条路可记为
P＝ABED。
{ewc MVIMAGE,MVIMAGE, !16000290_0031_1.bmp}图 4-9 图 4-10 实际上，这里“路”的概念跟我们平常走路的路的概念是很类似的。 在一条路中，顶点和边都允许重复经过。例如下述的 p1 和 p2 都是图 4-9
所表示的图中的路：
P1＝Ae1Be8Fe5Ee9Be2C
这条路经过顶点 B 两次，即在路 p1 中顶点 B 出现两次。
p2＝Ge11Ae1Be8Fe6Ae1Be2C。
{ewc MVIMAGE,MVIMAGE, !16000290_0031_2.bmp}
这条路经过顶点 A、B 各两次，也经过边 e1 两次（见图 4-11（a）和图
4-11（b））。
4.回路
如果一条路的起点和终点重合，这条路就叫做一条回路。下面写出的 p1、
p2、p3 都是图 4-9 中所示的图的回路。为了容易看清楚，我们分别再画在图
4-12 中。
p1＝Ae6Fe8Be1A（图 4-12（a））；
P2＝Ae7Ce3De4Ee10Ce2Be1A（图 4-12（b））；
P3＝Ae6Fe8Be9Ee5Fe8Be1A（图 4-12（c））。
5.连通图

　　设 A、B 是图中的两个顶点。如果在 A、B 间有一条路，我们称 A、B 两个 顶点在这个图中是连通的。
如果一个图中任意两个顶点都是连通的，那么我们称这个图是连通图。 换句话说，如果一个图是连通图，那么从图中随便一个顶点出发，都可
以经过某一条路走到任意的一个顶点去。
　　我们看到，图 4-6 中表示迷宫的两个图都是连通图。要是这两个图不是 连通图，那么我们从 A 进去，就无法走遍迷宫的每条边，从而迷宫问题无解。 所以今后在讨论迷宫问题时，我们总假设它的图是连通图。
　　如果表示一个迷宫的图中有回路，将表明游迷宫的人有可能一直绕着回 路走而兜圈子。图 4-6 中的两个图都有回路，进入这两个迷宫的人，都有可 能迷路。
　　刘老师介绍的这些图的名词，大家都感到很直观，很容易理解。刘老师 接着说：“有了图的概念，你们去研究游迷宫问题就方便多了。现在我们假 设怪物米诺陶就住在图 2-1 的迷宫的某处，请你们回去研究一下，提修斯带 着一个线球能不能找到这个怪物并从迷宫入口出来？如果能找到，他该怎么 走？下一次我们举行一次讨论会来讨论这个问题。要是你们有兴趣的话，可 以做几个练习，用以加深对图这一新概念的理解。”说着，刘老师留下了几 道练习题。



练习一


　　1.一中初三有 A、B、C 三个班；二中初三也有三个班 A′、B′、C′。 两校初三年级联合举办一次篮球友谊赛，规定每校的一个班级代表队要和另 一个学校的三个班级代表队各赛一次。如果友谊赛已结束，试用一个图表示 这次友谊赛中，哪些队和哪些队进行过比赛。
2.下图中顶点 A、B、C 分别表示三个工人；A′、B′、C′、D′分别表
示四项不同的工种。如果工人 A 能干工种 B′，则在 A、B′间连一条边，其 余类推。试通过图指出，各工人能干一些什么工种？
{ewc MVIMAGE,MVIMAGE, !16000290_0034_1.bmp}
　　3.下图中各顶点代表一种电器元件。如果 A、B 两元件间必需用导线接 通，则在 A、B 间连一条边。试通过图指出这个电器系统有几个元件？哪些元 件间必须用导线接通？
4.以上各题中，哪些图是连通图？哪些图不是连通图？
{ewc MVIMAGE,MVIMAGE, !16000290_0035_1.bmp}
{ewc MVIMAGE,MVIMAGE, !16000290_0035_2.bmp}
5.试把下列迷宫用图表示出来。
（2）
{ewc MVIMAGE,MVIMAGE, !16000290_0036_1.bmp}

五 提修斯怎样找到怪物米诺陶？
——解迷宫问题的方法一


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

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


　　黄杰上次听了林文的发言，本来就不太同意他的看法，但是讲不出个道 理来。经过刘老师的启发，加上有了图的工具，他回去后认真地研究了图 4-6
（b）的图和自己编的一些简单的连通图，一边试验，一边总结规图 5-1 律， 终于想出了办法。他举手要求第一个发言。得到刘老师的同意后，他先在黑 板上画了一个表示图 2-1 迷宫的图（图 5-1），并把顶点和边标上符号。
{ewc MVIMAGE,MVIMAGE, !16000290_0038_1.bmp} 他的发言要点如下：
　　1.由于不知道怪物米诺陶藏在迷宫的什么地方，所以提修斯要想找到 它，必须想出一个能走遍图 5-1 每条边至少一次的办法才行。
2.引路线的作用，不仅可引导提修斯按照原路走出迷宫，而且可以指出
哪些边走过了（这些边上布有引路线），哪些边还没走过（这些边上没有引 路线）。
上次林文同学的发言中忽略了引路线的第二个作用，才使他怀疑提修斯
能找到米诺陶。其实只要注意到引路线的第二个作用，提修斯一定能找到米 诺陶（当然要假设米诺陶不在迷宫里跟提修斯捉迷藏。这个假设是合理的， 因为当时米诺陶并不知道提修斯要去杀它）。提修斯可以这样走：进迷宫的 门后，不断寻找没走过的边继续走，直到没有这种边的时候为止。这样，他 就把图 5-1 的所有边都至少走过一遍了，然后再按原路走出来。
黄杰说：“根据上面的想法，我在图 4-6 的两个图和其他一些连通图上
都反复试过，找到了一种游迷宫的办法，其步骤是：
1.从入口 A 任选一条边走到一个新顶点。
　　2.当到达一个顶点 X 的时候，如果 X 与一些未走过的边相关联，就任选 一条未走过的边走到另一个顶点 Y；如果到达顶点 X 的时候，所有和 X 关联 的边都已走过了，那就按原路返回。
3.在返回的途中，还可能遇到有的顶点关联一些未走过的边，这时，从
这些边中任选一条，继续按步骤 2 的办法走。如果从某点返回到 A 的途中， 没有发现任何一个和顶点（包括 A）有关联又未走过的边，就可从 A 出来了。 “返回途中，是有可能遇到有的顶点关联一些未走过的边的。例如在图
5-1 中，我们从 A 出发，沿 e2 走到 C，再沿 e4 走到 E，从 E 走到 G，以后一直
往前走。当我们返回的时候，就在顶点 E 遇到 e6 还没走过，到达顶点 C 的时
候，就会发现 e3 还没走过。
　　“我按上面说的办法，试过好多连通图，不管是图 4-6 中的（a）或（b）， 或者是其他连通图，都能走遍图中所有的边再从 A 出去。”
　　接着他举出两个例子来说明这一方法。第一个例子，使用一个比较简单 的连通图，第二个例子，就用图 5-1 的图。在这两个例子中，都假设 A 是迷
　　
宫入口。
【例 1】在图 5-2 中按上述方法解迷宫问题：
{ewc MVIMAGE,MVIMAGE, !16000290_0041_1.bmp}
解：（1）从 A 出发，沿 e1 走到 B；由于 B 关联两条图 5-5 未走过的边，
按步骤 2 可任选一条，例如沿 e2 走到 C；从 C 沿 e5 走到 E；E 关联未走过的
边 e4、e6，按步骤 2 从中任选一条，如沿 e6 走到 F；同样道理，沿 e8 走到 H
（图 5-3）。
（2）在顶点 H，没有关联未走过的边，按步骤 2 沿原路返回。沿 e8 返回
的时候，途经 F，发现 e7 未走过。按步骤 3，沿 e7 走到 G（图 5-4）。
　　（3）在顶点 G，没有关联未走过的边，按步骤 2，顺原路返回，即走下 面的路：
Ge7Fe8He8Fe6Ee（图 5-5）。
（4）到 E 后，发现与 E 关联的边 e4 还没走过，于是按步骤 3，沿 e4 走
到 D，再沿 e3 走到 B（图 5-6）。
{ewc MVIMAGE,MVIMAGE, !16000290_0042_1.bmp}图 5-6
　　（5）走到 B 后，发现跟 B 关联的所有边都已走过了，按步骤 2，顺原路 返回，即走下面的路：
Be3De4Ee6Fe8He8Fe7Ge7Fe8He8Fe6Ee5Ce2Be1A。
　　在这次返回过程中，没有发现和任何一个顶点（包括顶点 A）有关联未 走过的边，于是我们从 A 出来。
上述走法，就是从 A 进去，走遍图中每条边至少一次，再从 A 出来的一
种走法。
【例 2】在图 5-1 中按上述方法解迷宫问题。
解：（1）从 A 进去，有两条边 e1、e2 可走，我们从中任选一条边走，
例如选 e1，接下去，仿例 1 的分析，我们可以走出如下的一条路（图 5-7）：
Ae1Be1Ae2Ce4Ee6Fe6Ee5Ge8He10Je11Ie7G。
（2）到 G 后，由于和 G 关联的所有边都走过了，于是按原路返回：从 G
沿 e7 走到 I。这时，发现和 I 关联的 e9 还没走过，于是从 I 沿 e9 走到 H，由
于和 H 关联的所有边都走过了，于是按原路返回：
{ewc MVIMAGE,MVIMAGE, !16000290_0043_1.bmp}图 5-7
He9Ie7Ge7Ie11J。
（3）在 J 点，发现边 e12 还没走过，于是可按下法走：
Je12Ke14Me14K。
（4）在顶点 K 发现 e13 还没走过，于是从 K 经 e13。到 L。
　　（5）在顶点 L，由于和 L 关联的边都已走过，于是按原路返回。这次可 以顺原路线一直返回到 C，然后经 e3 到 D。
　　（6）同理，到 D 后，按原路线返回。这次返回到 A 的途中，不会遇到关 联未走过边的顶点，所以能一直返回到 A，并从 A 出来。
　　同学们认真地听了黄杰介绍的办法后，都按这个办法在笔记本上试验， 尽管走的路线不一样，但最终确实都走遍图中的每一边并且从 A 出来。
一个新的问题产生了，有的同学提出：黄杰总结的方法对图 5-1 和图 5-2

是可行的，对其他连通图是否也一定可行？怎么证明这一点？对这个问题， 黄杰一时也答复不出来。
　　刘老师意识到，这个新问题的提出，说明同学们的思维往更深的层次发 展了，这是一个十分可喜的现象。但是要对这一方法作一般证明，可能是同 学们力所不及的。于是她决定亲自出马。
　　她首先肯定了黄杰的发言。她说，黄杰同学从实验入手，从特例中探索 走法，总结规律，从而提出了一种解迷宫问题的方法。这个方法，如果用游 迷宫的普通语言可以叙述如下：
游迷宫的方法一：
1.进入迷宫后，可以任选一条通道往前走。
2.碰壁就返回。
　　3.到达一个叉路口，观察是否有还没走过的通道，如果有，就任选一条 往前走；如果没有，就顺原路返回到下一个叉路口，重复 2 和 3。
　　4.由原路返回迷宫入口处的时候，跟入口相连的各通道都已走过了，就 从入口处出来。这时，迷宫里的每条通道都至少走过一次了。
　　这方法不仅对图 5-1 和图 5-2 等特殊的图可行，而且我们可以证明对任 一连通图都可行，即
1.按照这个方法，的确能从 A 进去，再回到 A。
2.按照这个方法，从 A 出来的时候，每条边都已被走过至少一次。 她说：“如果我们证明了这二点，那么方法一就成为一个正确的一般方
法了。
　　“如果上面这二点还没有证明，那么方法一还只能说是一个从实验、归 纳得出的猜想。实验—归纳—猜想—证明，这是我们探索问题的一种常用方 法，今后我们还要通过具体例子，再说明这种探索问题的方法。
“我们休息十分钟，然后我来介绍方法一的证明。下面是两个练习题，
有兴趣的同学回去后可以试一试。”

练 习 二

1.试按游迷宫方法一，找出青少年乐园迷宫的一条游迷宫路线。
　　2.试按游迷宫方法一，各找出练习一第五题中两个迷宫的一条游迷宫路 线。
　　
六 解迷宫问题方法一的证明


休息后，刘老师继续主持讨论会，她开始介绍解迷宫问题方法一的证明
①。
前面已经说过，要证明方法一是正确的，必须证明以下两点：
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，我们确信解迷宫问题的方法一是普遍可行的正确方法。 刘老师最后说：“我们现在已经找到解迷宫问题的一个方法了，但这个
方法好不好，大家还可以回去考虑和实践。今天的讨论会就开到这里。”

七 小探险家再游迷宫


　　有了解迷宫问题的方法一，小虎子重游迷宫的劲头来了。这次黄杰也很 积极，因为他也想实践一下他提出的游迷宫办法。于是三个好朋友又凑在一 起，商量重游迷宫的计划。
　　黄杰自告奋勇要准备一团线球。他笑着对小虎子说：“去年风筝线是你 准备的，这次的线球由我来准备吧！”
　　林文摇摇头说：“今非昔比，这一团线得好几百米呢！我们是不是一定 要像提修斯一样带个线团去游迷宫呢？记得格林童话中有这样一个故事：亨 舍尔和格莱特兄妹二人的继母把他们领到森林里，想遗弃他们。聪明的亨舍 尔预先知道继母的阴谋，在去森林的前一天晚上，口袋里装了许多小圆石， 第二天他一路走一路把小圆石丢在路上。以后就顺着这些小圆石找到了家。 这些小圆石的作用也就是引路线的作用，我们是不是也想个办法来‘改革’ 一下引路线呢？”
　　“好主意！”小虎子脱口而出，“我看到的探险小说里的主人公也有用 一种作路标的办法标明路线的。”
三个人你一言我一语讨论引路线的改革。 小虎子早就筹划重游迷宫，也考虑到如何解决引路线问题，林文的建议
对他启发很大。他联想到上次看到的游宫说明里有一条说可以领取粉笔一
支，不禁恍然大悟，经过进一步考虑，终于想出了一个代替线团的办法。他 说：“记得上次游宫说明中有一条说可以领取粉笔一支，我又记起迷宫中每 堵墙的两头都嵌有一块黑板。迷宫的设计师显然已经替我们考虑过可以用粉 笔在墙上作记号。所以，我们可从出发的墙上画一个箭头，编上号，到达岔 路口的墙上也画一支箭头并连续编号，这就表明我们从哪里开始走，到达哪 里，再往哪里继续走。这些箭头，我想可以代替引路线的作用了。”
小虎子提出的这一改革办法，得到大家一致的赞同。他们先在表示青少
年乐园迷宫的图上用小箭头试画了一小段路（图 7-1），感到完全可行。于 是他们又约定星期日下午再次游迷宫。
这次三个小探险家已是心中有数。他们不慌不忙地领了一支粉笔，进入
迷宫。小虎子建议从“引人入胜”门进去。于是他们在 AK 墙上画了一个箭头 编为 1 号。以后往前走到 K，到达 K 的时候，他们在这堵墙的另一端画了第 二个箭头，标上 2 号（图 7-2）。现在按方法一有两条路可走，他们继续走
向 L，并在 KL 墙上画了第三个箭头，标上 3。就这样，一直接方法一走，一
边走，一边画箭头、编号。在图 7-2 中我们画出了他们实际路线的一部分。 箭头编到第 40 号的时候，虽然到了入口 A，但因不是按原来由 A 出发的路（标
有 1 号箭头的 AK）返回 A，所以他们没从 A 走出去，而是返回 B，这样，箭 头继续编到第 64 号。接下去按方法一，他们又应往回走。往回走的时候，正 好在每个顶点上都没有未走过的边。因此，他们一直顺着这 64 个箭头的相反 方向一个个走下去，一边走，一边仍继续编号，一直编到第 128 号，正好对
上 1 号箭头。这说明他们的确是按原路返回了 A。这时他们看到在入口处的 每堵墙上都已有了箭头，说明所有跟入口相关联的通道都已经走过了。因此， 他们确信已游遍了迷宫的每条通道，高兴地走出迷宫。
{ewc MVIMAGE,MVIMAGE, !16000290_0054_1.bmp}图 7-1
{ewc MVIMAGE,MVIMAGE, !16000290_0055_1.bmp}

　　这次游迷宫，虽然不像上次迷路那样紧张，但是却也走得很累。他们发 现有的边要走 4 次、8 次，重复的路走得太多了，这也许是这个方法的一个 大毛病吧。因此他们都在想：能不能有一种少走冤枉路的办法呢？
　　他们把实践的情况和问题向刘老师作了汇报。刘老师夸奖他们用粉笔画 筋头代替线团的“技术革新”，同时同意他们关于方法一缺点的看法。她说： “重复路走得太多，确实是这方法的最大缺点，你们游迷宫的图有 15 条边， 一条边走过一次要编 2 个号码，你们编了 128 个号，说明每条边平均走 4 次 以上。这不是个好办法。我们还有一个每条边刚好只需走 2 次的办法。这个 方法跟欧拉图有关，欧拉图又跟著名的哥尼斯堡七桥问题的故事有关??”
“什么是欧拉图？” “什么是哥尼斯堡七桥问题？” “新方法该怎样走？” 大家迫不及待地问。
　　“别急，下一次讲座，我就准备向你们介绍哥尼斯堡七桥问题和欧拉图 的有关知识。哥尼斯堡七桥问题还很有趣味呢！”
大家听了刘老师有条不紊的讲座计划，非常满意地离开了。

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


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

哥尼斯堡七桥问题


　　“十八世纪时，东普鲁士有个城市叫哥尼斯堡，它就是原来苏联的加里 宁格勒。这个城市有一条河叫普雷格尔河，它穿过这个城市，河中有两个小 岛，这四块陆地间有七座桥相连（图 8-1）。当地居民喜欢在那里散步。久 而久之有人提出了这样一个问题：是否能设计一条散步路线，使得一个人从 家里（四块陆地中某块的某处）出发，走过每座桥恰好一次，然后回到原来 出发的地方？
{ewc MVIMAGE,MVIMAGE, !16000290_0058_1.bmp}图 8-1 “很多人对这个问题感到兴趣，试了好多次都没有成功。到底有没有这
样的散步路线呢？当时谁也回答不出来。最后这个问题传到当时的大数学家
欧拉那里，他研究了这个问题，并在一七三六年发表了《哥尼斯堡的七座桥》 的论文。这篇论文，后人认为是《图论》的第一篇论文。 “现在我们来看看，应当怎样来研究这个问题。
“我们先把图 8-1 中的四块陆地分别记为 A、B、C 和 D。我们关心的是
哪些陆地间有桥相通，有几座桥相通，至于陆地 A、B、C、D 有多大，桥有多 长都是无关紧要的。因此我们能把 A、B、C、D 都各看成一个顶点，A 跟 B 有 两座桥相连，图 8-2（a）就在 A、B 间连两条边（图 8-2（a）），其他仿此 处理，我们就把图 8-1 的地图表示成为一个图（图 8-2（b））。
{ewc MVIMAGE,MVIMAGE, !16000290_0059_1.bmp}
　　“这样，设计哥尼斯堡七桥散步路线的问题，就转化为图 8-2（b）的图 能否从任一顶点出发，不重复地一笔画完这个图，再回到原出发顶点的问题 了。这个问题以后简称一笔画问题。
“一笔画的游戏，大家小时候可能都做过，现在我们用图论的名词，把
它的意思说清楚。
　　“如图 8-3，这个图能从顶点 A 出发，不重复地一笔画完（即从 A 出发 再回到 A）。我们可以这样画：
{ewc MVIMAGE,MVIMAGE, !16000290_0060_1.bmp}图 8-3
“从 A 经 e1 到 B，经 e2 到 C，经 e3 到 D，经 e4 到 B，经 e5 到 F，经 e6 到
D，经 e7 到 E，经 e8 到 F，最后经 e9 回到 A。按照图论的名词，上面说的实际
上是一条回路：
p＝Ae1Be2Ce3De4Be5Fe6De7Ee8Fe9A，
这条回路有两条性质：
（1）图中的每条边都在 P 中出现；
（2）图中的每条边都只在 P 中出现一次。 “为了纪念欧拉，后人称具有上述两条性质的路叫做欧拉路，而具有上

述两条性质的回路叫做欧拉回路。如果一个图有一条欧拉回路，就称这个图 为欧拉图。
　　“上面我们说的是：一个图如能从任意一个顶点出发，不重复地一笔画 完，再回到出发点，那么这个图就是欧拉图。反之，如果一个图是欧拉图， 也就是说，它存在一条欧拉回路，那么从图中任意一个顶点出发，沿这条回 路都能不重复地一笔画完这个图，再回到原出发点。
　　“因此，说‘一个图是欧拉图’和说‘一个图能从任一顶点出发不重复 地一笔画完这个图，再回到原出发点’，这两种说法是完全一样的。
　　“现在我们提出一个问题：给你一个图（例如图 8—2（b）、图 8—3） 你怎么知道它是否欧拉图？解迷宫问题的另一方法，就跟这个问题有关。”

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


{ewc MVIMAGE,MVIMAGE, !16000290_0061_1.bmp} “让我们先动手做一些试验。请你用笔画画试试，看看图 8—4 中的哪些
图是欧拉图，哪些图不是欧拉图？请你边做试验，边想想其中的道理。” 同学们好像参加智力竞赛一样，纷纷在笔记本上画了起来。小虎子很快
发现（a）、（c）不是欧拉图，（b）、（d）、（f）是欧拉图。但对（e），
他画来画去，总找不出一条欧拉回路来，但是又不敢断定它不是欧拉图。偏 巧刘老师提问了他。
“陈虎，你的试验结果怎样？”刘老师问。
陈虎忐忑不安地站起来答道： “图（b）、（d）、（f）是欧拉图，因为我们可以通过一笔画找到一条
欧拉回路。”说着他到黑板上画出了这三
　　{ewc MVIMAGE,MVIMAGE, !16000290_0062_1.bmp}图 8—5 个图的欧拉回路（图 8—5）。
“另外，（a）不是欧拉图，这是因为它没有回路；（c）也不是欧拉图，
因为我们如果从顶点 A 出发走到 B（图 8—6），那么要回到 A，必然要重复
走 BA，因此不存在不走重复边的回路，即它没有欧拉回路，所以它不是欧拉 图。至于图（e），我还判断不了它是否是欧拉图。”
“你刚才说的，实际上包含着一般的思考方法。”刘老师在启发小虎子，
“要肯定一个图是欧拉图，必须找到一条欧拉回路，如（b）、（d）、（f）。 如果要否定一个图是欧拉图，只需找到一个顶点，说明从它出发，不可能不 重复地一笔画完这个图，再回到这个顶点，如你刚才举的图（c）中的顶点 A。 这个思考方法是很正确的。现在你再按这个思考方法观察图（e）中的顶点 A
（图 8—7）。”
{ewc MVIMAGE,MVIMAGE, !16000290_0063_1.bmp} 小虎子从刘老师的提示中想到，从图 8—7 中的 A 出发，一定不能不重复
地一笔画完这个图，再回到 A。这是因为 A 和三条边关联，从 A 沿一条边出 去，从另一条边回到 A，再从 A 沿第三条边出去，最后就不能不重复地走这 三条边中之一，再回到 A 了。
“我想到了，图（e）也不是欧拉图。”小虎子把上面的想法说了出来。 刘老师点点头。然后又问：“你现在从（b）、（d）、（f）是欧拉图和
（a）、（c）、（e）不是欧拉图，能不能总结出一个图是欧拉图和非欧拉图

的本质原因是什么吗？” 小虎子是很聪明的，他略一思索就说：
　　“哦！我知道了！不是欧拉图的图，一定有一个顶点关联奇数条边，这 样，从这顶点出发要回到这个顶点，不重复走一条边是办不到的。从是欧拉 图的图（b）、（d）、（f）来看，它们都没有这样的顶点，这也许就是欧拉 图和非欧拉图的一条重要的本质区别。”
　　平常比较不善于观察总结的小虎子，今天能找到这两种图的主要特点， 刘老师十分高兴。她请小虎子回到座位，并且说：
　　“刚才陈虎同学已从几个特例的试验，总结出欧拉图和非欧拉图的一条 本质区别，他的看法是对的。在图 8—4 中，（a）、（c）、（e）都至少有 一个顶点关联奇数条边，这种图不是欧拉图。在（a）、（c）、（e）中添了 一些边，变成（b）（d）（f），这三个图中各个顶点关联的边数都是偶数条， 就都成了欧拉图。但是还要注意，非连通图一定不是欧拉图。下面准备把我 们刚才的探索结果总结一下。为了说话方便起见，我们引入两个名词：
“奇顶点：图中的一个顶点，如果关联奇数条边，管这顶点叫奇顶点。 “偶顶点：图中的一个顶点，如果关联偶数条边，管这顶点叫偶顶点。 “现在通过探索，我们能提出如下猜想： “一个连通图是欧拉图■图中所有顶点都是偶顶点。 “为什么只能说是猜想呢？这是因为上面的结果只是从几个特例归纳得
到的，还没经过一般证明。当我们作了一般证明之后，上面的猜想就成为一
个定理了。”

关于欧拉图猜想的证明


“一个连通图是欧拉图■图中所有顶点都是偶顶点。 “我们先证明如果一个图是欧拉图，那么它的所有顶点都是偶顶点。 “这点证明很简单。如果一个图是欧拉图，那么从图中任一顶点出发， 能不重复地一笔画回到这一点。这是一条欧拉回路，这条回路进出图中的每 个顶点都是偶数次，并且进出的边都是不同的。所以，图中的每一个顶点都
是偶顶点。
　　“现在再来证明，如果一个连通图的所有顶点都是偶顶点，那么这个图 一定是欧拉图。
“证明的方法是：对给定的所有顶点都是偶顶点的连通图，具体找出一
条欧拉回路来。这条回路找出来了，就证明这个图是欧拉图了。 “为了使大家容易理解，我结合一个具体的图来讲。
{ewc MVIMAGE,MVIMAGE, !16000290_0066_1.bmp} “假设我们有一个连通图，它的所有顶点都是偶顶点（例如图 8—8）。
我们任取一个顶点记作 DA。从 A 出发，如图 8—8 下走出一条边不重复的路：
从 A 沿任一边走到另一顶点，记作 B。因 B 是偶顶点，必定还有一条和 B 关 联的边还没走过，我们从这条边走到 C。同理，由于 C 也是偶顶点，所以和 C 关联的边中也一定还有一条未走过的边，我们沿这条边走到另一顶点 D。仿 此做下去，由于经过一个顶点的时候，进出的边数成双，所以这条路只要到 达一个不是 A 的顶点，就一定还有一条和这顶点关联的未走过的边，我们可 以从这条边出去。因为图中的边数是有限的，我们每次所走的边又应是不同

的，所以这条路不能无限止地走下去，而必须在某一顶点停止。这停止的顶 点不能是 A 以外的顶点，因为对 A 以外的顶点，路线经过它时有一条进去的 边，由于它是偶顶点，必然还有一条边未走过，从而可从这条边走出去。可 见这条路必须在顶点 A 停止。即我们将走出一条回路，不妨把它记作 P（在
图 8—8 中，p＝ABCDBEFA）。
　　“假如 P 已走遍图中的所有边，而且因为我们走的边都是先前没走过 的，可见这些边都是不同的。这样 P 就是一条欧拉回路，从而我们证明了这 个图是欧拉图。
　　“假如图中还有一些边没被 P 走到。由于图是连通的，从第六章定理 1 知道，P 中有某个顶点（例如图 8—8 中的 E），关联某条未走过的边。由于
E 是偶顶点，所以和 E 关联的未走过的边的数目一定仍是偶数条。同理，在 图中任一顶点关联的未走过的边都是偶数条。这样，从 E 出发，正像从 A 出 发一样，又可找到一条回路 P′，它走过图中一些不同的未走过的边再回到 E
（见图 8—9，在这图里，p′＝EGHE）。
{ewc MVIMAGE,MVIMAGE, !16000290_0068_1.bmp}
　　“现在我们可从 A 出发，沿 P 的一部分先走到 E（如图 8—9 为 ABCDBE）， 到了 E 后，沿 p′走回 E（EGHE），然后继续走完 P 剩下的一部分回到 A（EFA）。 这样，由 P 和 p′合起来的回路 q 就比 P 走过更多的边了（图 8-9 中 q＝ ABCDBEGHEFA）。如果 q 走遍整个图，它就是一个欧拉回路，我们也就证明了 给定的图是欧拉图。如果 q 还没走遍全图，我们又能仿照上面的办法把 q 再 扩大。由于图的边数有限，扩大有限次后，一定能找到一条回路，它走遍了 整个图的边，而且由于每次走的时候，都是走未走过的 G 边，所以这条回路 中的边都不相同。可见最后这条回路是一条欧图 8-9 拉回路。这也就证明了 所给的图是欧拉图。
“这样，我们就得到了一个定理：
〔定理 2〕一个连通图是欧拉图■这个图所有的顶点都是偶顶点。 “回顾我们探索怎样的一个图是欧拉图的过程，我们再一次看到如何通
过特例的实验，归纳总结规律，提出猜想，最后再给以证明的过程。这种探
索问题的办法是很有用的。今后大家在学习中应当学会使用这种办法。 “应用定理 2，我们很容易判别一个图是否欧拉图。这只要看看所给的
图中是否有奇顶点就可以了。现在我们回到哥尼斯堡七桥问题上来。在这个
问题中，能否设计一条散步路线从陆地的某处出发，走遍每座桥恰好一次再 回到原出发点，相当于问图 8-2（b）是否欧拉图。由于这个图中有 4 个奇顶 点，所以它不是欧拉图，可见这样的散步路线是设计不出来的。这也就是欧 拉那篇论文的答案。
　　“定理 2 有许多实际应用。下次讲座我将介绍如何利用定理 2 来研究游 迷宫问题，探索一个比方法一少走冤枉路的方法。今天的讲座就到这里为 止。”
　　听完这次讲座，大家都感到收获很大。因为有些同学过去玩过一笔画游 戏，以前大家老是一个图一个图去试，不懂得去探索规律，现在有了刘老师 介绍的定理 2，随便拿一个图就能很快判别它是否能一笔画回到原出发点 了，而且还知道怎样去画它。此外，大家还从这件事得到很大的教育，学习 了实验——归纳——猜想——证明的探索问题的方法。从这里，大家更觉得 刘老师循循善诱，既教给大家知识，又教给大家研究问题的方法，他们对刘
　　
老师更加爱戴了。下面是刘老师留下的练习。

练习三


　　1.下列各图，哪些图能从任一顶点出发，走遍图中每条边恰好一次再回 到原出发点？
　　2.一个至少有两个顶点的连通图，假如要从顶点 A 出发，走遍图中的每 条边恰好一次到达另一顶点 B（这种从 A 到 B 所走过的路即欧拉路），这个 图各顶点关联的边数应有什么特征？请你作出猜想并加以证明。
（1）{ewc MVIMAGE,MVIMAGE, !16000290_0070_1.bmp}
（2）{ewc MVIMAGE,MVIMAGE, !16000290_0071_1.bmp}
（3）{ewc MVIMAGE,MVIMAGE, !16000290_0071_2.bmp}
　　3.在哥尼斯堡七桥问题中，请你添一座桥，使得能从一个小岛出发，走 过每座桥恰好一次到达另一小岛。
4.下图表示一个十五座桥的问题。图中的英文字母表示陆地。问：
（1）能否从某地出发，走过每座桥恰好一次再回到该地？
（2）能否从某地出发，走过每座桥恰好一次而终止于另一地？
{ewc MVIMAGE,MVIMAGE, !16000290_0071_1.bmp}

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


　　“上次讲座，我们从哥尼斯堡七桥问题引出了欧拉图的概念，并对怎样 的图是欧拉图作出了猜想，最后证明了如下的定理 2：
“一个连通图是欧拉图■这个图所有的顶点都是偶顶点。 “现在我们要利用它来研究游迷宫问题。我们知道，图 9-1（a）表示图
2-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 的具体方法来。如果能找到这个方 法，就比我们上次讨论的方法一要好多了。”

解迷宫问题方法二的猜想


　　“我们还是从对具体的、特殊的迷宫作实验分析入手，然后加以归纳， 猜想它的一般走法规则，最后给以证明。
{ewc MVIMAGE,MVIMAGE, !16000290_0074_1.bmp}图 9—2
　　“我们先以一个比较简单的连通图为例来进行分析，这个图如图 9-2 所 示，A 表示迷宫入口。
“1.在图 9-2 中，从 A 进入迷宫后，先走哪条边呢？因为进入迷宫后，
如有好几条和 A 关联的边可走，这些边对我们来说，地位都是完全平等的， 哪一条也不特殊，所以我们可猜想，可以任意选一条边走。
“2.假设我们从 A 沿 e2 走到 C，那么回来的时候，就应当从 C 沿 e2 走到
A。这样，在边 e2 上刚好走了两个相反的方向。由此我们猜想，对其他边来
说，每条边刚好走两次，可能也应要求是走两个不同的方向。
“3.当我们从 A 沿 e2 走到 C 后，类似 1 的分析，照理可在 e3、e4 和 CA
中任选一边走，但是 CA 的方向有点特殊性：e3 和 e4 的两个方向都没有走过，
而 e2 的 AC 方向已经走过了。在什么样的情况下，才允许我们沿 CA 的方向走
回 A 呢？这是应当考虑的。显然，我们应当要求除了 C 到 A 的方向外，所有
和 C 关联的边的两个方向都走完了，才能从 C 回到 A。否则，如果和 C 关联 的某条边的某方向（例如 CE）尚未走过，我们就从 C 走到 A，那么为了再走
和 C 关联的那条边（CE），还需要从 A 再走到 C，这样，e2 就不止走两次了。
由此我们又猜想，当从 A 到 c 后，应在 e3 和 e4 中任选一条边走，而不应当沿
CA 走回 A。一般地，我们可作如下猜想：当从某个顶点 X 第一次走到一个新 顶点 Y 时，只在和 Y 关联的所有边的两个方向都走过了，才最后走从 Y 到 X

的方向回到 X。这条猜想很重要，因为如果按这条办法做，当我们从一个顶 点往回走的时候，能保证跟这顶点关联的所有边都已走过两次了。
“4.按上面三条猜想，我们已能一直往前走了。如果我们走回到 A 的时
候，能否就出去呢？还不能，因为 e1 还没走过。所以在一般情况下，当到达
进口处的时候，还要看看和进口关联的所有边的两个不同方向是否都已走过 了，如果都已走过了，才可以走出来。
{ewc MVIMAGE,MVIMAGE, !16000290_0076_1.bmp} “要实践上面几条游迷宫的猜想，必须有一种方法，能标记哪条边的哪
个方向已经走过了，以及当游到一个新顶点的时候，是从什么地方来的。在 实践游迷宫方法一的时候，陈虎等几个同学已经想出一种画箭头的办法，用 它标记从哪个顶点到达哪个顶点，这是一个好办法，现在我们也可以用。当
我们从 A 沿 e2 往 C 走的时候，在 A 处，沿 e2 画一个箭头；到达 C 时，也在 e2
旁画一个箭头。因为顶点 C 第一次走到，CA 的方向应当留待和 C 关联的其他 边的两个方向都走过了才走。所以到达 C 的箭头应有特别标记，我们约定使 用双箭头（如图 9—3）。
　　“现在我们有了走法的猜想和标记方法，就可以用一些图试试看。在试 的过程中，如发现有考虑不周到的地方，再修改补充。如果你动手试一试， 就会发现上面的猜想是可以达到预定目的的。这样，我们就把这些猜想整理 成几条规则，然后再设法证明这些规则的正确性。”
解迷宫问题方法二的规则（猜想）：
　　1.每一条边应走两个不同方向，如果一条边的两个方向都走过了，就不 再走了；
2.从一个顶点 X 第一次走到一个新的顶点 Y，只在和 Y 关联的其他所有
边的两个方向都走过了，才最后从 Y 到 X 的方向走回来；
　　3.从入口 A 可任选一条边走，以后凡是到达一个顶点的时候，可以从没 走过的任意一条边走，如果没有这种没走过的边时，可以选择一条只走过一 次的边，按相反方向走。当然，根据第 2 条，第一次到达这个顶点的边的相 反方向应该最后走。
4.当到达迷宫入口 A 的时候，如果和 A 关联的所有边的两个方向都走过
了，就可以从 A 出去了。 “现在我们先举例说明我们的走法规则，最后才给以证明。先看图 9-2
的图。
“在顶点 A，有两条和 A 关联的边未走，按规则 3，可任选一条，例如选
e2，沿 AC 方向从 A 走到 C。我们在 A 旁沿 AC 方向画一箭头，到达 C 的时候，
也画一箭头。因为我们第一次到达 C，所以这一箭头应画成双箭头（图 9—4）。 “在顶点 C，又有两条和 C 关联的边未走。按规则 3，可任选一条，例如
选 CD，跟前面一样作箭头（图 9—5）。
“在顶点 D，没有未走过的边，所以按 CD 的相反方向走回到 C（图 9—6
（a））。
{ewc MVIMAGE,MVIMAGE, !16000290_0078_1.bmp}图 9—4 图 9—5 “实际上，顶点 D 是迷宫中碰壁的绝点。这在实际游迷宫的时候是很容
易辨认的。对于绝点，必然要回头，所以在实际游迷宫的时候，绝点 D 旁的 两个箭头可以不必画出（见图 9—6（b）），但在 C 旁的两个箭头要画出，

它表明从顶点 C 往 D 的两个方向都已走过，而下次不必再走了。以后遇到绝 点，我们都同样处理。
{ewc MVIMAGE,MVIMAGE, !16000290_0079_1.bmp}图 9—6
“从 D 回到 C 后，由规则 2 不能走 CA，而应走 CE 到 E，下面假设从 E
到 F 到 G 再走到 E（图 9—7）。由于从 G 到 E 是第二次到 E，所以这个箭头 不必画成双箭头。
{ewc MVIMAGE,MVIMAGE, !16000290_0079_1.bmp}图 9—7
　　“现在在顶点 E，由于和 E 关联的三条边都画有一个箭头，说明都走过 一次了，已经没有一个方向都未走过的边。因此，按规则 3，选择一条走过 一次的边按相反方向走。按规则 2，不能走 EC 的方向回来；按规则 1，不能 再走 EF 的方向。于是只能从 EG 走回到 G。到达 G 后，由于还有一条边两个 方向都没走过，所以由 G 走到 H（图 9—8）。H 是绝点，返回 G，由于 GE 的 两个方向都走过了，GH 两个方向也都走过了，由规则 2，我们沿跟第一次到
达 G 的方向的相反方向 GF 返回。下面依同理，从 F 到 E 到 C 到 A。在 A 处， 由于发现 AB 还没走过，所以不能就从 A 出去，而应从 A 到 B，再从 B 返回 A。 这时，跟 A 关联的 AC 和 AB 边的两个方向都已经走过了，才从 A 出来。
{ewc MVIMAGE,MVIMAGE, !16000290_0081_2.bmp} “从图 9—8 我们看到，迷宫中的每条通路，确实两
{ewc MVIMAGE,MVIMAGE, !16000290_0081_1.bmp}图 9—9
个不同方向都刚好走过了。” 接着，刘老师让同学们在笔记本上用方法二画出图 9—1（a）的游迷宫
路线，下面就是小虎子作出的一条游迷宫路线：
ABACEGHJIGIHIJKLKMKJHGEFECDCA（见图 9—9）。 在同学们掌握了游迷宫方法二规则的基础上，刘老师开始讲解方法二的
证明。

解迷宫问题方法二的证明

现在我们来证明上述规则的正确性，为此我们必须证明以下两点：
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 关联的每条边，刚好走过两个相反方向而不会多走。
　　2.现在证明，当我们停止在 A 时，和其他顶点关联的所有边也都按两个 相反方向，刚好走过一次。
假设我们沿 AB 第一次到达顶点 B。当我们停止在 A 时，上面已经证明了
AB 的两个相反方向我们都已走过了。也就是说从 B 返回 A 的方向也已走过 了。我们注意到，沿着 AB 的方向第一次到达顶点 B 的时候，我们在 B 处标有 双箭号；而 BA 正是这个双箭号的相反方向。在规则 2 中，我们曾约定，只有 当和 B 关联的其他所有边的两个方向都走过了才能走 BA。现在既然我们已经 走了 BA，就意味着和 B 关联的所有边的两个方向都已走过了，而且由规则 1， 这些边的两个方向都恰好走过一次。现在我们考察由 B 出发第一次到达的顶
点 C。按同样的推理，和顶点 C 关联的所有边的两个相反方向也恰好走过一 次。仿此一直推下去，因为图是连通的，顶点数有限，我们就能一步步推得 和所有顶点关联的一切边，都按两个不同方向刚好走过一次。这样，我们就 证得了方法二的正确性。所以，规则 1 到 4 就是我们解迷宫问题的方法二， 而不再只是猜想了。
　　刘老师最后风趣地说：“今天我们介绍的解迷宫问题的方法二，应该说 还是纸上谈兵，你们不妨再到青少年乐园中去实践一番。”她接着说：“关 于游迷宫问题的讨论，我们就准备到此为止。通过这几次数学爱好者协会的 活动，你们有什么心得体会，如果有时间的话，可以总结一下，在下一期班 上的学习园地里交流。”
　　
十 小探险家三游迷宫


　　在“五四”青年节的下午，小虎子的班级到青少年乐园举行纪念活动。 在自由活动时间里，我们的三个小探险家第三次游了迷宫。这次他们仍和第 一次一样，商定兵分两路，小虎子从“引人入胜”门进去，林文和黄杰从“渐 入佳境”门进去，约定在门口会师。下图（图 10—1）是小虎子的游宫路线。
他是这样走的： AKLKGFHGIGHMHJHFEBCDCECBABEFGKA。 林文和黄杰的走法如图 10—2。 他们的走法是： ABCEBEFGKAKLKGIGHJHFHMHGFECDCBA。
　　在门口会师的时候，他们完全满意了，回忆起第一次游迷宫时的狼狈情 景，禁不住哈哈大笑起来。{ewc MVIMAGE,MVIMAGE, !16000290_0086_1.bmp}
{ewc MVIMAGE,MVIMAGE, !16000290_0087_1.bmp}图 10—2

练 习 四


　　1.试用解迷宫问题的方法二，各找出练习一第 5 题中两个迷宫的一条游 宫路线。
2.有一座迷宫如下页图所示，A 是入口，X 是出口，迷宫的图是连通的。
　　（1）能否用解迷宫问题的方法二，找到一条从 A 到 X 的路线，如能，请 你找出一条来；
（2）如果有一个人在 Y 处迷了路，问他能否用解迷宫问题的方法二找到
出路？如能，请你帮他找一找。
{ewc MVIMAGE,MVIMAGE, !16000290_0088_1.bmp}

十一 各有所获


　　班上最新一期的《学习园地》出版了。我们三位小主人公的学习心得体 会都被选入。
下面这一段是摘自小虎子的心得体会： “通过这段时间参加数学爱好者协会游迷宫问题的讲座活动，使我学到
了游迷宫的两个方法。将来要是真的到一个迷宫似的山洞里去探险的时候， 再也不会像第一次游迷宫时那么糊里糊涂地乱闯了，当然也不会像提修斯那 样，带着一大团线球进去。从这里，我体会到学习数学的重要性。通过正确 的数学思考方法的训练，能使人思考问题周密细致，此外，应用数学知识还 能帮助我们找到解决问题的最好办法。现在一想起第一次游迷宫的情景，我 就感到惭愧。看来，做任何一件事，都应当先好好想想，周密地考虑一下怎 样做才行，否则就不可能做好。这对我不太爱动脑筋、莽莽撞撞的坏习惯来 说，是一个很好的教训??”
下面这一段引自林文的心得体会： “最使我想不到的是，文学作品中也包含着数学知识。《水浒》我看过
不只一遍，就没有想到盘陀路就是一座迷宫。《三国演义》是囫囵吞枣地看 了一遍，更没注意到八阵图是怎么回事。现在重读这些章回，不仅倍觉亲切， 而且理解也更深了一层。最近，我从图书馆找到了一本《希腊古代的神话传 说》的小说，其中确实有刘老师所说的提修斯的故事，我起初还怀疑提修斯 是否会找不到那个怪物呢！我对文学很有兴趣，有时甚至想将来当个文学家， 可是对数学却兴趣不浓，学习也不太用功，开始有了偏科的倾向。通过这段 讲座活动，看来即使立志将来要当文学家，也必须努力学好数学。通过这段 活动，我感到数学还是很有趣味的。另一方面，刘老师是教数学的，可她的 文学知识多么丰富，故事说得多么引人入胜！因此，看来将来要学理工的， 也要学好语文。总之，中学阶段是一个多么重要的全面打基础阶段啊！”
最后这一段是黄杰心得体会的一部分：
　　“我原以为数学就是几何、代数、三角和现在只是听说而还没有学到的 解析几何、微积分。这段时间参加游迷宫问题的数学爱好者协会活动，使我 开阔了眼界，增长了知识，不仅学会了游迷宫的具体方法，而且还学习了一 些有趣的图论知识。刘老师还在讲座中结合具体问题，介绍了从一些特例着 手，实验归纳一般规律，提出猜想并进而加以证明的探索问题的方法。我感 到这套办法很好，对我很有启发，以前没有认真注意，今后在学习中应当有 意识地运用，以加强自己探究问题的能力。所以这次活动，真是收获不 少??”
亲爱的读者，你们读了这本书有些什么体会呢？

十二 未结束的结束语


　　刘老师看了同学们自己办的学习园地上的文章后，在迷宫问题专题讲座 的最后一次活动上，对这段活动作了小结。她回顾了所介绍的知识和探索问 题的方法，并对同学们的心得体会作了评述。最后，她还说了下面这段似乎 并未结束的结束语：
　　“在我们介绍游迷宫问题的同时，已经讲了图论的一些知识。这些知识 是很初步的，因为实际上只介绍了几个最基本的概念和欧拉图的知识。尽管 如此，我们已经看到图论知识在研究某些实际问题中的重要作用了。例如， 一个眼花缭乱的迷宫用图表示之后就容易研究多了。
　　“我们所介绍的欧拉图知识，虽然是从一个古老的数学游戏中提出的， 但是它却有一些实际应用。例如我们利用它导出了比解迷宫问题方法一好的 方法二。假如将来你们要到一个大岩洞里去考察，只要有照明设备，带上粉 笔就可以按方法二进洞考察了。如果以后你们要负责设计一个展览会，你可 以把它设计成一座迷宫，把展品摆在通道的两旁，而引导观众参观的路线就 按方法二设计，这样，观众们对每件展品刚好可参观一次。
　　“欧拉图的知识不仅用在解决迷宫问题上，而且还可以用来解决其他生 产实际问题。山东师范大学的管梅谷教授在一九六○年为邮递员叔叔设计了 一种最优的投递路线，在解决这个问题的时候也用到了欧拉图的知识。现在 我把它简单介绍一下：
“假设有个邮递员要从邮局出发，走遍他所负责的街区的每条街道至少
一次去投递邮件，然后再返回邮局，问应当怎样设计他的路线，才能使所走 的路最短？
“如图 12-1 中，邮局在 A 处。我们把邮局和街道岔口、拐角都看成图的
顶点，联结两个顶点的街道，当成图的边。那么图 12—1 就是一个各边带有 长度（长度注在边旁）的图。如果这个图的所有顶点都是偶顶点，按照前面 的定理 2，我们能找到一条欧拉回路，邮递员只要按这条回路走，就一定是 最短的路线了。但是，图 12-1 中有 18 个顶点是奇顶点，所以它不是欧拉图。 这样，邮递员要从 A 出发走遍这个图的各条边再回到 A，一定要重图 12-1 复 走一些边才行。图论的知识进一步告诉我们：在一个图中如有奇顶点，其个 数一定是偶数，即可配成双。这样，我们可把所有奇顶点一对对配好，并沿 着图中的边连结起来，使有的边变成重边，那么新得的图（如图 12-2）就没 有奇顶点了，它就可以从 A 出发，再一笔画回到 A。
　　“在图 12-2 中，变成二重边的那些边，就是邮递员必须重复走的街道。 容易看出，怎样把一对对奇顶点连起来的办法不止一种，不同的连法，所重 复的边不一定图 12—2 一样长，而重复边的总长就是邮递员走重复路的长。 那么到底应当如何把奇顶点一对对连起来，才能使邮递员重复走的路总长最 短，是解决这个问题的关键。管梅谷教授提出并证明了一种办法，解决了这 个问题。这个问题很著名，现在外国的图论学者都把它叫做‘中国邮递员问 题’。
　　“应用中国邮递员问题的知识，不仅能设计邮递员叔叔的最优路线，而 且还能设计最优的城市街道洒水车的巡回路线以及自动扫街车的巡回路线。 欧拉图的知识能在这些实际问题中得到应用，你大概没想到吧！
“欧拉图仅仅是图论中讨论的问题之一。在图论中还讨论许多在国民经

济中有重要应用的知识。我们举两个例子： “‘最短（长）路问题’，这个问题是研究如何在每条边都附有长度的
一个图中（如图 12-1），找出任意两个顶点间的最短路（或最长路）。在设 计一个费用最省的石油（自来水、煤气）管道路线或制定运费最省的物资运 输计划的时候就要用到这种知识。此外，如果我们要完成一项工程，往往要 做许多事，而每件事之间又有先后次序和完成时间，我们可以把每件事情用 一条有方向的边表示，这样，一项工程就能用一个边带有方向的图来表示。 这时最短（长）路的知识就能用来帮助我们制订最快完成工程的计划。解放 军叔叔还用这些知识来制订作战计划呢！
　　“‘平面性问题’。这个问题是研究怎样的图能画在一个平面上，使每 条边除顶点外不再相交。无线电工程师设计了一个新的电视机线路图后，就 要用这方面知识考虑它能不能在一个平面上制成印刷电路板。
“此外，电子计算机科学中也用到许多图论知识。 “图论的知识不仅很有用，而且它研究的一些问题还很有趣味。前面介
绍的哥尼斯堡七桥问题和一笔画问题就是很好的例子。我这里再举一个有趣 的问题——哈密尔顿周游世界问题。
　　“一八五九年英国数学家哈密尔顿发明了一种游戏。他在图 12-3 的 20 个顶点上，标上世界各大城市的名字。游戏者从某个城市（顶点）出发，沿 图中的边寻找经过每个城市（顶点）一次且只一次再回到原出发城市的路线。 这种路线，后人称为哈密尔顿回路。
“一般地说，哈密尔顿回路是经过图中每个顶点恰好一次的一条回路。
如果一个图有一条哈密尔顿回路，这个图就叫做哈密尔顿图。由于图 12-3 中的粗线
{ewc MVIMAGE,MVIMAGE, !16000290_0098_1.bmp}图 12—3
是一个哈密尔顿回路，所以图 12-3 就是一个哈密尔顿图。 “哈密尔顿周游世界问题是：任给一个图，怎样判断它是否是哈密尔顿
图？
　　“这个问题和一笔画问题有惊人的类似处。一笔画问题是要判断任一个 图是否有欧拉回路，而哈密尔顿周游世界问题是要判断任一个图是否有哈密 尔顿回路。应该注意的是，欧拉回路是经过图中每条边恰好一次的回路，而 哈密尔顿回路是经过图中每个顶点恰好一次的回路。由于这一点不同，导致 两个类似问题有完全不同的难度。利用定理 2 可以轻而易举地判断一个图是 否是欧拉图，但是哈密尔顿周游世界问题研究了一百多年至今还没解决。由 于图论中有很多悬而未决的问题都跟哈密尔顿周游世界问题的解决有关系， 所以目前还有许多数学家正在努力攻克这个问题。
　　“总而言之，游迷宫问题我们介绍完了，但是图论中还有许多在国民经 济中有重要应用的知识，以及许多有趣的但还没解决的问题，有待将来有志 于图论学习的同学去进一步学习和研究。”
在一阵热烈的掌声中，刘老师结束了她的讲话。

练习解答


练习一
1.
{ewc MVIMAGE,MVIMAGE, !16000290_0100_1.bmp}
2.A 能干工种 A′、B′、D′；
B 能干工种 A′、B′、D′； C 能干工种 C′。
3.有五个元件；元件 A、B；A、C；A、E； A、D；B、E；B、C；
C、D；C、E 必须用导线接通。
4.第 1、3 题的图是连通图；第 2 题的图不是连通图。
5.（1）
{ewc MVIMAGE,MVIMAGE, !16000290_0101_1.bmp}
（2）
{ewc MVIMAGE,MVIMAGE, !16000290_0101_2.bmp}

练 习 二

1.见“小探险家再游迷宫”。
2.游迷宫的路线如下：
　　（ 1 ） AGHGCMIMJMCDEDFDCAB ， 然 后 再 按 原 线 路 返 回 A ： BACDFDEDCMJMIMCGHGA。
{ewc MVIMAGE,MVIMAGE, !16000290_0102_1.bmp}
（2）ACDCEFEGAHABAHAGIJIMIKI，然后再按上述路线的相反方向返回 A： IKIMIJIGAHABAHAGEFECDCA。
{ewc MVIMAGE,MVIMAGE, !16000290_0102_2.bmp}

练 习 三

1.（1）、（2）能；
（3）不能。
　　2.〔分析〕从 A 出发后不回到 A，可见顶点 A 应是奇顶点。同理顶点 B 也应是奇顶点。图中其余各顶点都是有一条边进去，再从另一条不同的边出 来，所以都应是偶顶点。
　　〔猜想〕一个至少有两个顶点的连通图有欧拉路■图中恰有两个奇顶 点。
〔证明〕
　　（1）若一个至少有两个顶点的连通图有欧拉路，则由〔分析〕中所说的 道理，图中恰有两个奇顶点；
　　（2）若一个连通图恰有两个奇顶点 A、B，我们在 A、B 间人为地添加一 条边 AB，则所得的新图无奇顶点。按定理 2，知它有一条欧拉回路 P，且 P 中含有这条增添的边 AB。今在 P 中把边 AB 抹去后，便是一条从 A 到 B 的欧 拉路。
　　
这样，上述猜想便成为一个定理。
　　3.如图，在 A、C 间造一座桥，则它相应的图中，A、C 为偶顶点，B、D 为奇顶点。由第 2 题知，可从 B（或 D）走遍每座桥恰好一次到达 D（或 B）。
4.十五座桥问题所对应的图如下：
在这个图中，顶点 D、E 为奇顶点，其余各顶点为偶顶点，所以：
（1）由定理 2，不能从某地出发走遍每一座桥恰好一次，再回到该地。
　　（2）由第 2 题，可以从 D（或 E）出发，走遍每一座桥恰好一次，终止 于 E（或 D）。
{ewc MVIMAGE,MVIMAGE, !16000290_0104_1.bmp}

练 习 四

1.下面是它们的一种走法：
（1）ABACDFDEDCMJMIMCGHGAGCA。
{ewc MVIMAGE,MVIMAGE, !16000290_0105_1.bmp}
（2）ACDCEGAHABAGIMIKIJIGEFECA。
{ewc MVIMAGE,MVIMAGE, !16000290_0105_2.bmp}
　　2.本题迷宫相应的图如下，它是一个连通图。解迷宫问题的方法二，实 际上能从一个连通图的任意一个顶点走到所有的顶点，所以用解迷宫问题的 方法二，可从 A 走到 X，也可从迷路的 Y 处走到入口 A 或出口 X，从这两个地 方出去。
（1）
{ewc MVIMAGE,MVIMAGE, !16000290_0106_1.bmp}
（2）所走路线是：ADYDBCBFGFX。 所走路线是：YDEDBCBFGFX。
{ewc MVIMAGE,MVIMAGE, !16000290_0106_2.bmp}
当然，他也可能从入口 A 出去，例如：
{ewc MVIMAGE,MVIMAGE, !16000290_0106_3.bmp} 所走路线是：YDBA。