o_迷宫中的数学.pdf

《o_迷宫中的数学.pdf》由会员分享，可在线阅读，更多相关《o_迷宫中的数学.pdf（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、前 言 如果你要到一个大岩洞里去探险，该怎样走才能走遍岩洞的每个地方再 安全地出来？如果你在地道里迷了路，如何自寻出路？读了这本小册子，不 仅将得到这两个问题的满意答案，而且还可以学到一些图论的基本知识和探 索问题的基本方法。 迷宫中的数学 一 小探险家一游迷宫 我们的故事发生在一座风景秀丽的滨海城市。这个市的青少年乐园里， 新近落成了一座奇巧的建筑物迷宫。几天时间，吸引了很多很多的青少 年朋友。凡是游过迷宫的人，无不感到兴趣盎然。那些在迷宫里迷了路，吃 够了“绕圈子”、“碰壁”的苦头，最后拖着酸软的双腿走出迷宫的人，更 是津津乐道，准备重游。迷宫落成的消息，很快惊动了我们这本小书的主人 公之

2、一陈虎。 陈虎确实生得虎头虎脑，身体胖得像个一号电池。他正在念初中三年级， 同学们都叫他小虎子。他有很强的好奇心，爱看冒险小说，打算将来做个探 险家，只是他的性情比较急躁，行动莽撞。迷宫落成的消息使他兴奋异常， 他马上去约同班的好友林文和黄杰一起去“探险”一番。 林文和黄杰的性格比较文静。林文喜爱文学，黄杰却对数学特别感兴趣。 他们对迷宫的兴趣显然不如陈虎大，但是经不起好朋友绘影绘声的宣传，终 于同意星期天下午一道去游迷宫。 这是一个风和日丽的日子。三个小探险家来到了那座奇妙的建筑物前 面。那是一个边长约 3 0 米的露天正方形建筑物，大门的扁额上写着“迷宫” 二字。进出的游人不少，小虎子一下

3、子就想闯进去，想不到衣角却被黄杰拉 住了。 “哎！哎！哎！看看说明再进去！” 原来黄杰一眼看见了墙上贴有“游宫说明”。这份说明实在跟公园的其 他说明大不一样，现抄录于下： 游宫说明 一、游迷宫是一种益智的数学游戏，敬请游客多动脑筋，十二岁以下儿 童如无年长者带领，谢绝游宫； 二、迷宫中心的标志是一尊半人半牛的希腊神像米诺陶，并备有休息处； 三、每个岔路口都有开关一只，如果迷路时需要问路，可掀开开关，将 有一张图纸详细指示你所在的位置和继续前进的方法，看完请即关闭开关， 图纸自行消失； 四、游客如需要，可领粉笔一支，以备游宫时使用。 迷宫管理处 我们的三个小探险家实在不明白第四条说明的意思，于是

4、他们决定不予 理睬，开始走入进口。一进迷宫，首先见到的是两个精致小巧的拱门，一个 上方写着“引人入胜”，一个上方写着“渐入佳境”。三个小探险家犹豫了： 该从哪个门进去呢？小虎子早就跃跃欲试，他提议道：“既然一道门能引 人入胜，一道门可以渐入佳境，可能都是可以走的。咱们来个兵分两 路，一路去 入胜，一路走 佳境，比赛谁先到迷宫中心，你们看如何？” 这个富有挑战性的建议，马上得到其他两个人的一致赞同。他们商定陈虎从 “入胜”进去，林文和黄杰去探寻“佳境”。 他们探险的结果如何，我们等一下再说，现在先向读者介绍一下这座迷 宫的结构。为了便于说明，我们把它的平面图画在下面（图 1 1 ）。 原来这座迷

5、宫除了入口处有两个标有“引人入胜”和“渐入佳境”的拱 门外，里面都以装饰相同的墙壁隔成许多弯弯曲曲的走道。迷宫的设计师为 了迷惑游人，不仅在每个岔路口都造有拱门，而且明明走不通的绝路顶端， 也造了外形完全一样的假拱门，乍一看去，使人分不清真假。为了后面说明 方便，我们把“渐入佳境”的门记为甲，把“引人入胜”的门记为乙，并把 每个岔路口和绝路端点都标上英文字母，M 处是迷宫中心。 e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 0 6 _ 1 . b m p 图 1 - 1 当然，我们的这三个小探险家是没有见过这张平面图

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

7、，一直向中心进发， 想不到竟拐了几个弯才走到 E ，更糟糕的是到了 E以后，方向搞不清了。他 们糊里糊涂走到 D ，碰了壁，退到 C ，穿过 C 从拱门甲出来，转过身一看，坏 了！居然还是“渐入佳境”！他们知道这是未到中心先绕了一个圈子。以后 他们又从原路进去，走到 E ，正在往 F走的时候，看见小虎子在向他们招手 哩！ 当他们互相报告了碰壁的经过后，这三个难兄难弟哈哈大笑起来。他们 决定启动开关问路，按照图纸的指示，终于到达了迷宫中心 M 。在这里，他 们看到了一座小巧玲珑的假山，假山上有一尊牛头人身的怪物，看来这就是 米诺陶了。他们在这里的水泥椅上休息、谈笑，最后寻路出去。天哪！怎么 走出

8、去又是一道难题！但是，我可以告诉读者们，他们最终都走了曲折的道 路出来了。至于有没有再打开开关，那就不得而知了。 在回家的路上，他们虽然有些疲劳，但还是十分兴奋地议论着：这座迷 宫确实是一个很奥妙的谜，既迷人又有趣。到底怎样自由进出迷宫呢？这是 大家共同产生的问题。小虎子主张设法搞一张迷宫的平面图来，这样就可以 按图游宫了。可是黄杰却不以为然，他说：“既然游宫说明中说游迷宫是一 个益智的数学游戏，也许这里要用到什么数学知识，才能解决呢。”林文还 补充了一个问题，那就是，迷宫中放一个半人半牛的怪物是怎么回事？他们 决定把这些问题带回去请教他们的数学老师。 二 神奇的迷宫刘老师的第一次讲座 他们的

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

10、俗地介绍给大家。” 黄杰一听，高兴得几乎跳起来，他说：“刘老师，那就请您在数学爱好 者协会里做几次讲座吧！” 刘老师欣然答应了下来。 游迷宫问题的专题讲座，吸引了很多同学，我们的三位小主人公当然也 参加了。下面是刘老师的第一次讲座。题目是： 神奇的迷宫 “我先给大家讲一个古希腊的神话传说。 “古希腊的克里特岛王米诺斯的王后生了一个半人半牛的怪物，取名米 诺陶。皇后为了保护这个怪物的安全，请希腊最有本领的建筑师代达罗斯造 了一座著名的迷宫。迷宫里有数以百计的狭窄、曲折、幽深的道路和使人眼 花缭乱的阶梯以及很多小房间。不熟悉路径的人一旦走进迷宫，就会因迷失 方向而走不出来。迷宫造成后，王后就把米诺

11、陶藏在这座迷宫里。这个怪物 靠吃人肉为生，它不仅吃在迷宫里迷路的人，而且米诺斯王还强迫雅典人每 九年进贡七个童男、七个童女送到迷宫里给它吞食。这件事给雅典人民造成 了深重的灾难。当米诺斯王派使臣第三次到雅典索取贡品的时候，年轻的雅 典王子提修斯决心为民除害，自告奋勇和其他十三名童男童女一起去克里特 岛。雅典王虽然很伤心，却阻挡不住提修斯的决心，提修斯一行终于出发了。 当他被带去见米诺斯王的时候，引起了克里特岛王美丽、聪明的公主阿里阿 德尼的爱慕，她偷偷地送给提修斯一个线球，并教他把线球的一端紧紧地拴 在迷宫的入口处，然后放着线走进迷宫。她还给提修斯一把魔剑，用来杀死 怪物。提修斯得到公主的帮助

12、，把童男童女带进迷宫，找到怪物，经过一番 激烈的搏斗，终于用魔剑把它杀死，然后顺着线路，把童男童女安全带出迷 宫，为雅典人民做了一件大好事。 “克里特岛迷宫的故事脍炙人口，一直为人们所传颂。一九年，英 国地质学家兼考古学家阿瑟伊文思在这个岛的三米深的地层下，发现了一 座面积达二万四千平方米的宫殿遗址，共有一千二百到一千五百个房间，据 说这就是米诺斯迷宫的遗址。 “上面说的是古希腊关于迷宫的一个古代神话传说。在现实世界中，确 实有一种叫做迷宫的建筑物。迷宫建筑是建筑学中的一种学问，据说外国至 今还有一座建于一六九年的迷宫，图 2 - 1 是它的平面图。 “传说古罗马的埃德萨城也有一座迷宫，它建在

13、一个巨大的山洞里，里 面不仅有走道、房间，而且还有迷惑人的阶梯，看上去以为是往上走的，走 一段后却发现是往下去的。 e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 1 3 _ 1 . b m p “所谓迷宫，通常是指包括许多被墙壁所围的曲折的道路、绝路（有的 还连着一些小房间）所组成的建筑物。青少年乐园新落成的那座建筑物，就 是一座迷宫，它的中心有一尊牛头人身的怪物，就取自提修斯的故事。不熟 悉路径的人进入迷宫，很容易迷路，绕了半天还走不出来。 “在我国的古典小说里，也有类似迷宫的记载。三国演义中有一段 描述东吴大将陆

14、逊陷入诸葛亮的八阵图的故事：有一天，陆逊在进军途中， 到了一个叫渔腹浦的地方。看到诸葛亮过去布下的一个石阵，只见它四面八 方都有门户，陆逊以为这没什么奥妙， 闯入石阵观看，只见怪石嵯峨 c u ， 横沙立土重叠如墙。一时间风声阵阵，天色渐暗，当他急着要往回走的时候， 却一直找不到出路，后来幸好一个老人引他出来。这个神奇的石阵看来就是 一座迷宫。 “你们一定都看过水浒。实际上，三打祝家庄里所描写的盘 陀路也是一种迷宫。要进入祝家庄只有通过盘陀路，而这种盘陀路是容 易入得来，只是出不去的。第一次攻打祝家庄的梁山泊好汉吃尽了盘陀路 的苦头。他们走了一遭又转到这里，弄得不少好汉被活捉，幸亏石秀侦 察得

15、盘陀路的走法，才把兵马带了出去。 “我们再举一个现代的例子。大家看过电影地道战，那里的地道， 实际上也是神奇的地下迷宫，在抗日战争中，它起了很大作用。实际上，现 代的地下人防工事，也是一座座神奇的迷宫。 “前几天，我们班上有几位同学到青少年乐园的迷宫里探险一番， 回来后向我提出了一个能不能用数学方法找出游迷宫路线的问题。这个问题 提得很好，但是他们提的问题还不够明确，我想把它说得更明确一点，即： “假设从迷宫的每个地方，可以走到任何一个地方，问如何从迷宫入口 进去，游遍迷宫的每一条通道至少一次，再从迷宫的入口出来？我们以后就 简称这个问题为游迷宫问题。 “游迷宫问题不仅是一个游戏，而且也有实用

16、价值。当我们发现一个新 的岩洞，需要进去考察，这个岩洞就可能是一座迷宫，设计考察路线就要用 到游迷宫的知识；一个大型展览馆，也可以设计成一座迷宫，参观路线需要 设计得使每个观众恰好经过每件展品一次。这些都要用到游迷宫的知识。 “关于这个问题的条件，还需要补充几句。有的同学可能在儿童杂志的 数学游戏栏里见过游迷宫的游戏。你可能会想到，如果手中有一张迷宫平面 图，那么仔细观察一下就能从图中找到一条所需要的路线，按找出的路线走 就很容易了，何必用到数学知识呢？ “的确是这样的，如果有了平面图，就很好办了。但是，如果你要到一 个新发现的山洞里去探险，那是什么平面图也没有的。我们的条件就是要在 没有平面

17、图的情况下来研究游迷宫问题。黄杰等几个同学已经试过了，在没 有见到平面图的情况下，进入迷宫，到处都是装饰一样的墙壁，拐几道弯就 迷失了方向。看来，如果没有一套办法，是很难游遍迷宫再出来的。” 刘老师讲到这里停了一下，问大家是否把我们要讨论的问题弄清楚了？ 大家回答都清楚了。刘老师让大家休息一会儿，然后再初步议论一下如何来 解决这个问题。 三 林文的怪论 刘老师的讲座一开头就把同学们带进了古今中外神秘莫测的迷宫世界 里，引起了同学们的极大兴趣，以致在休息的时候这些故事还萦回在他们的 脑际。他们三三两两地议论着，男同学们崇拜提修斯的勇敢无畏，女同学们 却更赞佩阿里阿德尼的聪明机智。更有不少同学想到

18、青少年乐园的迷宫里实 践一下，所以我们的三位小主人公就忙得不亦乐乎，因为同学们知道他们游 过迷宫，都要他们介绍经验哩！ 小虎子本来就直言快语，更拗（n i ）不过同学们的请求，于是向大家介 绍了青少年乐园的迷宫和他们三个人游迷宫的经过。 最后， 他说了一句话： “ 我 们差点碰扁了鼻子。” 这话引起了一阵哄堂大笑。 笑声伴随着铃声，同学们又回到了教室。刘老师等大家静下来以后，开 始提出问题： “刚才我们介绍了游迷宫问题，接下去我们要考虑如何来解这个问题， 关于这方面，大家有些什么想法没有？” 不少同学举手要求发言，小虎子也是其中的一个。 “好！陈虎同学，谈谈你的看法。” “我想我们能否也像提修

19、斯一样，带一个线团去游迷宫。” “你怎么利用这一团线团呢？”刘老师进一步问。 “我们也把它的一端拴在门口，然后放着线直冲进去。”陈虎的话逗得 大家都笑了起来。 刘老师对这个回答是不够满意的。她感到陈虎考虑问题太粗糙。于是她 请陈虎坐下，并且说： “陈虎同学的思考太简单化。请不要忘记我们的目标是游遍迷宫的每个 地方，如何靠线团的帮助，使我们能走遍迷宫的每个地方，是需要仔细考虑 的问题。” 这时，林文要求发言，得到刘老师的同意后，他说： “我认为提修斯带一个线球好像不能解决游迷宫问题。提修斯的线球只 能保证他按原路走出迷宫，但是要走遍迷宫的每个地方就有困难了。那一天 我们三个人去游迷宫的时候，我和

20、黄杰从渐入佳境的门进去，陈虎从 引 人入胜的门进去，大家都没找到米诺陶就相遇了，可见迷宫中有绕圈子的 路。如果提修斯也遇上这种路，他岂不是也在迷宫里老绕圈子。这样，他可 能找不到米诺陶就只好顺着线走出来了。所以，希腊神话中所说的提修斯找 到怪物并把它杀死，我有点怀疑，这也许缺乏科学根据。” 这真是一通怪论！林文发言后，教室里顿时活跃起来。有的同学原先认 为带个线球可以解决问题的，现在在重新思索；有的同学不大同意林文的观 点，却一时说不清理由。刘老师对林文的看法感到意外，她略微思索了一下， 就找到了问题的症结所在。虽然她发现林文的想法是不对的，但是，她为有 这样思想活跃的学生感到高兴。她感到，有

21、必要让学生们多想想这个问题， 来学会判断这种想法是否正确，于是准备结束这次讲座。 “现在请大家静一静。刚才林文的发言，既有实践基础，又有一定的推 理，还敢对古希腊的神话传说提出质疑，这种精神是很好的。古人说过， 学 贵知疑，小疑则小进，大疑则大进，敢于提出疑问，疑问解决了，知识就 长进了。在考虑这个问题的时候，关键是引路线的作用。引路线除了可以指 示走出迷宫的路线外，还有没有别的作用？这个问题大家应当好好想一想。 “现在除了图 2 - 1 的迷宫平面图外，我再给大家一个青少年乐园的迷宫 平面图（见图 1 - 1 ），并且建议大家自己设计一些简单的迷宫，针对这些特 例，进行钻研。然后，再回答：如

22、果你是提修斯，身上带有一团足够长的线 球，事先又没有见过平面图，你能否走遍迷宫的每条通道（这样当然就找到 了那个怪物），再从原路出来？如果能，该怎么走？如果不能，原因是什么？ 以后我们再来讨论。 “最后顺便提一下，古希腊神话传说是世界文学宝库的财富之一，今天 我们看到，理解文学作品，有时也需要有一定的数学知识。准备将来当文学 家的同学们，同样也要学好数学啊！” 刘老师的一席话说得大家都乐了。 四 什么叫做图？刘老师的第二次讲座 “上次讲座，我给大家介绍了两个迷宫的平面图（图 1 - 1 ，图 2 - 1 ），并 且请你们研究了我们提出的游迷宫问题。不少同学告诉我，看了迷宫的平面 图使人眼花缭乱

23、，很不好研究。确实是这样的。今天我要给大家介绍一个工 具，它叫做图。利用图的知识，我们能把迷宫问题转化为一个图 的问题，也就是说，把一个实际问题化成一个数学问题。” 什么是图？ “大家可能会说：图是什么还用介绍吗？迷宫的平面图不就是一个 图吗？三毛流浪记一整本漫画不也都是图吗？错了，我们这里 所说的图指数学的一个分支图论中的专有名词。它跟迷宫的平 面图、函数的图象和图画的图是不同的。让我们先看一些例子。 【例 1 】假设有 5 个人，分别记作 A 、B 、C 、D 和 E 。在这 5 个人中，设 A 、B 两人互相认识； B 、C 两人互相认识； A 、C 两人互相认识； B 、D 两人互相认

24、识； C 、E 两人互相认识。 “我们可以用一个几何图形表示上面提到的 5 个人以及他们的认识 关系：每一个人用一个小圆圈表示；如果有两个人互相认识，就把表示这两 个人的小圆圈用一条线段连起来，那么这 5 个人和他们之间的相互认识关系 就可以表示成图 4 - 1 了。 e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 2 3 _ 1 . b m p 图 4 - 1 “如图 4 - 1所画的图形就叫做一个图。组成图的小圆圈 A 、B 、 C 、D 、E 叫做图的顶点。联结顶点的那些线段叫做图的边。如果 A B 是图的一 条

25、边，我们说顶点 A和顶点 B相邻，边 A B与顶点 A和 B关联，顶点 A和 B 是边 A B 的端点。 “从上面的例子中我们看到，在理解图这个概念的时候，应当注意： 1 . 图的顶点的位置可以随便画。 2 . 图的边可以画成直线段，也可以画成曲线段，并且画长画短都没有关 系。关键的是，一个图中有几个顶点 （有几个人），哪些顶点间有边相连 （哪 些人互相认识）。 3 . 图的两条边可能在非顶点的地方相交，这时候它们的交点不是图的顶 点。如图 4 - 1 中，顶点只有 5 个，应该把边 B D 想象为跨过边 A C 和 C E 。所以， 画一个图的时候，顶点一定要用小圆圈表示，以免和两条边的不是

26、顶点 的交点相混淆。 e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 2 4 _ 1 . b m p “这样，我们也可以把图 4 - 1画成图 4 - 2 ，它同样表示例 1 中的 5个人 和他们之间的认识关系。 【例 2 】设有一个表示篮球队循环赛的图，如图 4 - 3所示，它的一个顶 点表示一个篮球队。如果两个篮球队已经比赛过了，就在图 4 - 3 表示这两个 篮球队的顶点间连一条边。你们能不能说说看，图 4 - 3 中表示几个篮球队？ 哪两个篮球队间已经进行过比赛？哪些篮球队间还没有进行过比赛？” e w c M

27、 V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 2 5 _ 1 . b m p 同学们七嘴八舌地回答，刘老师都听见了，她说：“对的！图 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

28、 - 4 点用一条线段连起来。那么图 4 - 4 所表示的交通 图也是一个图。 “从上面三个例子看出，一个图就是由一些顶点和这些顶点之间的一些 边组成的图形。我们以后所讨论的图中的顶点数和边数都是有限个的，这种 图也叫做有限图。一个图的顶点可以表示一个人、一个球队或一个城市，当 然也可以表示其他事物。而边呢？它可以表示顶点所表示的事物间的某种关 系。例如用顶点表示城市，用边表示城市间有公路相通的关系等等。 “由于顶点可以表示很多东西，边可以表示这些东西间的一种关系，所 以我们就可以把图的知识应用于研究多种事物和它们各自的关系。例如我们 要研究的迷宫，现在就可以用图来表示了。 “在游迷宫问题中，

29、我们关心的是可以从哪个岔路口（或碰壁的绝点） 走到哪个岔路口（或绝点）。因此，我们可以把迷宫中的每个岔路口和绝点 用一个顶点来表示，如果两个岔路口（绝点）有一条通道相通，就在这两个 顶点间连一条边。这样我们就能用一个图来表示一个迷宫了。下面我用一个 简单的迷宫作例子来说明这种表示方法（图 4 - 5 ）。 “设有一个迷宫（图 4 - 5 （a ），我们先把所有岔路口和绝点标上英文 字母（图 4 - 5 （b ），再把有通道的顶点用边连起来（图 4 - 5 （c ），这样， 就得到迷宫的一个图（图 4 - 5 （d ），把它画得更顺眼一些，就得到图 4 - 5 （e ）。 e w c M V I

30、 M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 2 7 _ 1 . b m p “现在请你们不要看黑板，自己在笔记本上把图 1 - 1 和图 2 - 1 的迷宫用 图表示出来。” 这时，大家都动起手来，刘老师也在黑板上画出图 1 - 1 和图 2 - 1 两个迷 宫相应的“图”（图 4 - 6 （a ）和（b ）。 同学们把两个迷宫的平面图用“图”表示后，发现像图 2 - 1 那样复杂的 迷宫，用图来表示（图 4 - 6 （b ）竟是那样简单，感到十分惊讶。大家开始 对图的作用有了一点体会。 e w c M V I M A G E , M

31、V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 2 8 _ 1 . b m p 图 4 - 6 刘老师接着说：“现在我们的游迷宫问题，就变成了诸如在图 4 - 6 所表 示的图中，从顶点 A 出发，走遍图中每条边至少一次，再回到 A 应当怎么走 的问题了。” 图的一些名词？ 为了以后讨论问题的时候说话简洁方便，需要介绍一些跟图有关的名 词。 1 . 重边 如果我们有一个图（图 4 - 7 ）表示 A 、B 、C三个排球队的比赛情况。两 个队间赛过一场，就在表示这两队的顶点之间连一条边，赛过二场，连二条 边赛过几场，就连几条边。假设 A 、B间赛过两场，A 、C间赛过

32、五场， 而 B 、C 间刚刚赛了一场，那么上面的比赛情况就表示成图 4 - 7 所示的图。 这时，我们称图 4 - 7中顶点 A 、B间有二重边，A 、C间有五重边。其他 的重边情况仿这个规定命名。 2 . 简单图 今后我们常用大写英文字母表示图中的顶点，用小写字母 e 加上足码记 边。图 4 - 8 （a ）、（b ）、（c ）都表示一个图。 e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 2 9 _ 1 . b m p 注意到图 4 - 8 （a ）中边 e 3是两个端点重合在一起的边，这种边叫做环。 e w c

33、M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 3 0 _ 1 . b m p 如果一个图既无环，又无二重和二重以上的重边，这种图叫做简单图。 在图 4 - 8 中，（a ）、（b ）不是简单图，（c ）是简单图；在图 4 - 6 中图 4 - 8 （a ）、（b ）都是简单图。 3 . 路 在图 4 - 9 所示的图中，如果我们从 A 出发，沿边 e 1走到 B ，再从 B 沿边 e 9走到 E ，从 E 又沿 e4走到 D 。我们就说这是一条从 A 到 D 的路（图 4 - 1 0 ）， 记作 P A e 1 B e 9 E

34、e 4 D 。 在一个简单图中，路也可以只用顶点来记。图 4 - 9 是简单图，所以刚才 这条路可记为 P A B E D 。 e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 3 1 _ 1 . b m p 图 4 - 9 图 4 - 1 0 实际上，这里“路”的概念跟我们平常走路的路的概念是很类似的。 在一条路中，顶点和边都允许重复经过。例如下述的 p 1和 p2都是图 4 - 9 所表示的图中的路： P 1 A e 1 B e 8 F e 5 E e 9 B e 2 C 这条路经过顶点 B 两次，即在路 p 1中顶

35、点 B 出现两次。 p 2 G e 1 1 A e 1 B e 8 F e 6 A e 1 B e 2 C 。 e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 3 1 _ 2 . b m p 这条路经过顶点 A 、B各两次，也经过边 e 1两次（见图 4 - 1 1 （a ）和图 4 - 1 1 （b ）。 4 . 回路 如果一条路的起点和终点重合， 这条路就叫做一条回路。 下面写出的 p 1 、 p 2 、p 3都是图 4 - 9中所示的图的回路。为了容易看清楚，我们分别再画在图 4 - 1 2 中。 p 1 A e

36、 6 F e 8 B e 1 A （图 4 - 1 2 （a ）； P 2 A e 7 C e 3 D e 4 E e 1 0 C e 2 B e 1 A （图 4 - 1 2 （b ）； P 3 A e 6 F e 8 B e 9 E e 5 F e 8 B e 1 A （图 4 - 1 2 （c ）。 5 . 连通图 设 A 、B 是图中的两个顶点。如果在 A 、B 间有一条路，我们称 A 、B 两个 顶点在这个图中是连通的。 如果一个图中任意两个顶点都是连通的，那么我们称这个图是连通图。 换句话说，如果一个图是连通图，那么从图中随便一个顶点出发，都可 以经过某一条路走到任意的一个顶点去。

37、 我们看到，图 4 - 6 中表示迷宫的两个图都是连通图。要是这两个图不是 连通图，那么我们从 A 进去，就无法走遍迷宫的每条边，从而迷宫问题无解。 所以今后在讨论迷宫问题时，我们总假设它的图是连通图。 如果表示一个迷宫的图中有回路，将表明游迷宫的人有可能一直绕着回 路走而兜圈子。图 4 - 6 中的两个图都有回路，进入这两个迷宫的人，都有可 能迷路。 刘老师介绍的这些图的名词，大家都感到很直观，很容易理解。刘老师 接着说：“有了图的概念，你们去研究游迷宫问题就方便多了。现在我们假 设怪物米诺陶就住在图 2 - 1 的迷宫的某处，请你们回去研究一下，提修斯带 着一个线球能不能找到这个怪物并从迷

38、宫入口出来？如果能找到，他该怎么 走？下一次我们举行一次讨论会来讨论这个问题。要是你们有兴趣的话，可 以做几个练习，用以加深对图这一新概念的理解。”说着，刘老师留下了几 道练习题。 练习一 1 . 一中初三有 A 、B 、C三个班；二中初三也有三个班 A 、B 、C 。 两校初三年级联合举办一次篮球友谊赛，规定每校的一个班级代表队要和另 一个学校的三个班级代表队各赛一次。如果友谊赛已结束，试用一个图表示 这次友谊赛中，哪些队和哪些队进行过比赛。 2 . 下图中顶点 A 、B 、C 分别表示三个工人；A 、B 、C 、D 分别表 示四项不同的工种。如果工人 A 能干工种 B ，则在 A 、B 间

39、连一条边，其 余类推。试通过图指出，各工人能干一些什么工种？ e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 3 4 _ 1 . b m p 3 . 下图中各顶点代表一种电器元件。如果 A 、B两元件间必需用导线接 通，则在 A 、B 间连一条边。试通过图指出这个电器系统有几个元件？哪些元 件间必须用导线接通？ 4 . 以上各题中，哪些图是连通图？哪些图不是连通图？ e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 3 5 _ 1 . b m p

40、 e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 3 5 _ 2 . b m p 5 . 试把下列迷宫用图表示出来。 （2 ） e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 3 6 _ 1 . b m p 五 提修斯怎样找到怪物米诺陶？ 解迷宫问题的方法一 按照刘老师的建议，这次数学爱好者协会的活动以讨论会的形式进行。 讨论的题目是： 提修斯怎样找到怪物米诺陶？ 黄杰上次听了林文的发言，本来就不太同意他的看法，但是讲不出个道 理来。经过刘老师

41、的启发，加上有了图的工具，他回去后认真地研究了图 4 - 6 （b ）的图和自己编的一些简单的连通图，一边试验，一边总结规图 5 - 1 律， 终于想出了办法。他举手要求第一个发言。得到刘老师的同意后，他先在黑 板上画了一个表示图 2 - 1 迷宫的图（图 5 - 1 ），并把顶点和边标上符号。 e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 3 8 _ 1 . b m p 他的发言要点如下： 1 . 由于不知道怪物米诺陶藏在迷宫的什么地方，所以提修斯要想找到 它，必须想出一个能走遍图 5 - 1 每条边至少一次的办法

42、才行。 2 . 引路线的作用，不仅可引导提修斯按照原路走出迷宫，而且可以指出 哪些边走过了（这些边上布有引路线），哪些边还没走过（这些边上没有引 路线）。 上次林文同学的发言中忽略了引路线的第二个作用，才使他怀疑提修斯 能找到米诺陶。其实只要注意到引路线的第二个作用，提修斯一定能找到米 诺陶（当然要假设米诺陶不在迷宫里跟提修斯捉迷藏。这个假设是合理的， 因为当时米诺陶并不知道提修斯要去杀它）。提修斯可以这样走：进迷宫的 门后，不断寻找没走过的边继续走，直到没有这种边的时候为止。这样，他 就把图 5 - 1 的所有边都至少走过一遍了，然后再按原路走出来。 黄杰说：“根据上面的想法，我在图 4 -

43、 6 的两个图和其他一些连通图上 都反复试过，找到了一种游迷宫的办法，其步骤是： 1 . 从入口 A 任选一条边走到一个新顶点。 2 . 当到达一个顶点 X 的时候，如果 X 与一些未走过的边相关联，就任选 一条未走过的边走到另一个顶点 Y ；如果到达顶点 X的时候，所有和 X关联 的边都已走过了，那就按原路返回。 3 . 在返回的途中，还可能遇到有的顶点关联一些未走过的边，这时，从 这些边中任选一条，继续按步骤 2 的办法走。如果从某点返回到 A 的途中， 没有发现任何一个和顶点（包括 A ）有关联又未走过的边，就可从 A 出来了。 “返回途中，是有可能遇到有的顶点关联一些未走过的边的。例如

44、在图 5 - 1 中，我们从 A 出发，沿 e 2走到 C ，再沿 e4走到 E ，从 E 走到 G ，以后一直 往前走。当我们返回的时候，就在顶点 E 遇到 e 6还没走过，到达顶点 C 的时 候，就会发现 e 3还没走过。 “我按上面说的办法，试过好多连通图，不管是图 4 - 6 中的 （a ） 或 （b ） ， 或者是其他连通图，都能走遍图中所有的边再从 A 出去。” 接着他举出两个例子来说明这一方法。第一个例子，使用一个比较简单 的连通图，第二个例子，就用图 5 - 1 的图。在这两个例子中，都假设 A 是迷 宫入口。 【例 1 】在图 5 - 2 中按上述方法解迷宫问题： e w c

45、 M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 4 1 _ 1 . b m p 解：（1 ）从 A 出发，沿 e 1走到 B ；由于 B 关联两条图 5 - 5 未走过的边， 按步骤 2 可任选一条，例如沿 e 2走到 C ；从 C 沿 e5走到 E ；E关联未走过的 边 e 4 、e 6 ，按步骤 2 从中任选一条，如沿 e 6走到 F ；同样道理，沿 e8走到 H （图 5 - 3 ）。 （2 ）在顶点 H ，没有关联未走过的边，按步骤 2 沿原路返回。沿 e 8返回 的时候，途经 F ，发现 e 7未走过。按步骤 3 ，沿

46、 e7走到 G （图 5 - 4 ）。 （3 ）在顶点 G ，没有关联未走过的边，按步骤 2 ，顺原路返回，即走下 面的路： G e 7 F e 8 H e 8 F e 6 E e （图 5 - 5 ）。 （4 ）到 E 后，发现与 E 关联的边 e 4还没走过，于是按步骤 3 ，沿 e4走 到 D ，再沿 e 3走到 B （图 5 - 6 ）。 e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 4 2 _ 1 . b m p 图 5 - 6 （5 ）走到 B 后，发现跟 B 关联的所有边都已走过了，按步骤 2 ，顺原路

47、 返回，即走下面的路： B e 3 D e 4 E e 6 F e 8 H e 8 F e 7 G e 7 F e 8 H e 8 F e 6 E e 5 C e 2 B e 1 A 。 在这次返回过程中，没有发现和任何一个顶点（包括顶点 A ）有关联未 走过的边，于是我们从 A 出来。 上述走法，就是从 A 进去，走遍图中每条边至少一次，再从 A 出来的一 种走法。 【例 2 】在图 5 - 1 中按上述方法解迷宫问题。 解：（1 ）从 A进去，有两条边 e 1 、e 2可走，我们从中任选一条边走， 例如选 e 1 ，接下去，仿例 1 的分析，我们可以走出如下的一条路（图 5 - 7 ）：

48、A e 1 B e 1 A e 2 C e 4 E e 6 F e 6 E e 5 G e 8 H e 1 0 J e 1 1 I e 7 G 。 （2 ）到 G 后，由于和 G 关联的所有边都走过了，于是按原路返回：从 G 沿 e 7走到 I 。这时，发现和 I 关联的 e9还没走过，于是从 I 沿 e9走到 H ，由 于和 H 关联的所有边都走过了，于是按原路返回： e w c M V I M A G E , M V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 4 3 _ 1 . b m p 图 5 - 7 H e 9 I e 7 G e 7 I e 1 1 J

49、 。 （3 ）在 J 点，发现边 e 1 2还没走过，于是可按下法走： J e 1 2 K e 1 4 M e 1 4 K 。 （4 ）在顶点 K 发现 e 1 3还没走过，于是从 K 经 e1 3 。到 L 。 （5 ）在顶点 L ，由于和 L 关联的边都已走过，于是按原路返回。这次可 以顺原路线一直返回到 C ，然后经 e 3到 D 。 （6 ）同理，到 D 后，按原路线返回。这次返回到 A 的途中，不会遇到关 联未走过边的顶点，所以能一直返回到 A ，并从 A 出来。 同学们认真地听了黄杰介绍的办法后，都按这个办法在笔记本上试验， 尽管走的路线不一样，但最终确实都走遍图中的每一边并且从 A 出来。 一个新的问题产生了， 有的同学提出： 黄杰总结的方法对图 5 - 1 和图 5 - 2 是可行的，对其他连通图是否也一定可行？怎么证明这一点？对这个问题， 黄杰一时也答复不出来。 刘老师意识到，这个新问题的提出，说明同学们的思维往更深的层次发 展了，这是一个十分可喜的现象。但是要对这一方法作一般证明，可能是同 学们力所不及的。于是她决定亲自出马。 她首先肯定了黄杰的发言。她说，黄杰同学从实验入手，从特例中探索 走法，总结规律，从而提出了一种解迷宫问