中小学生学习指导百卷书数理学科 迷宫中的数学.pdf

《中小学生学习指导百卷书数理学科 迷宫中的数学.pdf》由会员分享，可在线阅读，更多相关《中小学生学习指导百卷书数理学科 迷宫中的数学.pdf（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、见迷宫中有绕圈子的路。如果提修斯也遇上这种路，他岂不是也在迷宫里老绕圈子。这样，他可能找不到米诺陶就只好顺着线走出来了。所以，希腊神话中所说的提修斯找到怪物并把它杀死，我有点怀疑，这也许缺乏科学根据。”这真是一通怪论！林文发言后，教室里顿时活跃起来。有的同学原先认为带个线球可以解决问题的，现在在重新思索；有的同学不大同意林文的观点，却一时说不清理由。刘老师对林文的看法感到意外，她略微思索了一下，就找到了问题的症结所在。虽然她发现林文的想法是不对的，但是，她为有这样思想活跃的学生感到高兴。她感到，有必要让学生们多想想这个问题，来学会判断这种想法是否正确，于是准备结束这次讲座。“现在请大家静一静。

21、刚才林文的发言，既有实践基础，又有一定的推理，还敢对古希腊的神话传说提出质疑，这种精神是很好的。古人说过， 学贵知疑，小疑则小进，大疑则大进，敢于提出疑问，疑问解决了，知识就长进了。在考虑这个问题的时候，关键是引路线的作用。引路线除了可以指Learning materials?示走出迷宫的路线外，还有没有别的作用？这个问题大家应当好好想一想。“现在除了图 2 - 1 的迷宫平面图外，我再给大家一个青少年乐园的迷宫平面图（见图 1 - 1 ），并且建议大家自己设计一些简单的迷宫，针对这些特例，进行钻研。然后，再回答：如果你是提修斯，身上带有一团足够长的线球，事先又没有见过平面图，你能否走遍迷宫的

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

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

24、认识关系：每一个人用一个小圆圈表示；如果有两个人互相认识，就把表示这两个人的小圆圈用一条线段连起来，那么这 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 是图的一条边，我们说顶点 A和顶点 B相邻，边 A B与顶点 A和 B关联，顶点 A和 B是边 A B 的端点。

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

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

27、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 - 4 点用一条线段连起来。那么图 4 - 4 所表示的交通图也是一个图。“从上面三个例子看出，一个图就

28、是由一些顶点和这些顶点之间的一些边组成的图形。我们以后所讨论的图中的顶点数和边数都是有限个的，这种图也叫做有限图。一个图的顶点可以表示一个人、一个球队或一个城市，当然也可以表示其他事物。而边呢？它可以表示顶点所表示的事物间的某种关系。例如用顶点表示城市，用边表示城市间有公路相通的关系等等。“由于顶点可以表示很多东西，边可以表示这些东西间的一种关系，所以我们就可以把图的知识应用于研究多种事物和它们各自的关系。例如我们要研究的迷宫，现在就可以用图来表示了。“在游迷宫问题中，我们关心的是可以从哪个岔路口（或碰壁的绝点）走到哪个岔路口（或绝点）。因此，我们可以把迷宫中的每个岔路口和绝点用一个顶点来表示

29、，如果两个岔路口（绝点）有一条通道相通，就在这两个顶点间连一条边。这样我们就能用一个图来表示一个迷宫了。下面我用一个简单的迷宫作例子来说明这种表示方法（图 4 - 5 ）。“设有一个迷宫（图 4 - 5 （a ），我们先把所有岔路口和绝点标上英文字母（图 4 - 5 （b ），再把有通道的顶点用边连起来（图 4 - 5 （c ），这样，就得到迷宫的一个图（图 4 - 5 （d ），把它画得更顺眼一些，就得到图 4 - 5（e ）。 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 7 _ 1 . b m p “现在请

30、你们不要看黑板，自己在笔记本上把图 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 V I M A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 2 8 _ 1 . b m p 图 4 - 6刘老师接着说：“现在我们的游迷宫

31、问题，就变成了诸如在图 4 - 6 所表示的图中，从顶点 A 出发，走遍图中每条边至少一次，再回到 A 应当怎么走的问题了。”图的一些名词？为了以后讨论问题的时候说话简洁方便，需要介绍一些跟图有关的名词。Learning materials?1 . 重边如果我们有一个图（图 4 - 7 ）表示 A 、B 、C三个排球队的比赛情况。两个队间赛过一场，就在表示这两队的顶点之间连一条边，赛过二场，连二条边赛过几场，就连几条边。假设 A 、B间赛过两场，A 、C间赛过五场，而 B 、C 间刚刚赛了一场，那么上面的比赛情况就表示成图 4 - 7 所示的图。这时，我们称图 4 - 7中顶点 A 、B间有二

32、重边，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 ）中边 e3是两个端点重合在一起的边，这种边叫做环。 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 0 _ 1 . b m p 如果一

33、个图既无环，又无二重和二重以上的重边，这种图叫做简单图。在图 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 - 1 0 ），记作P A e1B e9E e4D 。在一个简单图中，路也可以只用顶点来记。图 4 - 9 是简单图，所以刚才这条路可记为P A B E D 。 e w c M V I M A G E , M V I M

34、 A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 3 1 _ 1 . b m p 图 4 - 9 图 4 - 1 0实际上，这里“路”的概念跟我们平常走路的路的概念是很类似的。在一条路中，顶点和边都允许重复经过。例如下述的 p1和 p2都是图 4 - 9所表示的图中的路：P1A e1B e8F e5E e9B e2C这条路经过顶点 B 两次，即在路 p1中顶点 B 出现两次。p2G e1 1A e1B e8F e6A e1B e2C 。 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 .

35、 b m p 这条路经过顶点 A 、B各两次，也经过边 e1两次（见图 4 - 1 1 （a ）和图4 - 1 1 （b ）。4 . 回路如果一条路的起点和终点重合， 这条路就叫做一条回路。 下面写出的 p1、p2、p3都是图 4 - 9中所示的图的回路。为了容易看清楚，我们分别再画在图4 - 1 2 中。p1A e6F e8B e1A （图 4 - 1 2 （a ）；P2A e7C e3D e4E e1 0C e2B e1A （图 4 - 1 2 （b ）；P3A e6F e8B e9E e5F e8B e1A （图 4 - 1 2 （c ）。5 . 连通图Learning material

36、s?设 A 、B 是图中的两个顶点。如果在 A 、B 间有一条路，我们称 A 、B 两个顶点在这个图中是连通的。如果一个图中任意两个顶点都是连通的，那么我们称这个图是连通图。换句话说，如果一个图是连通图，那么从图中随便一个顶点出发，都可以经过某一条路走到任意的一个顶点去。我们看到，图 4 - 6 中表示迷宫的两个图都是连通图。要是这两个图不是连通图，那么我们从 A 进去，就无法走遍迷宫的每条边，从而迷宫问题无解。所以今后在讨论迷宫问题时，我们总假设它的图是连通图。如果表示一个迷宫的图中有回路，将表明游迷宫的人有可能一直绕着回路走而兜圈子。图 4 - 6 中的两个图都有回路，进入这两个迷宫的人，

37、都有可能迷路。刘老师介绍的这些图的名词，大家都感到很直观，很容易理解。刘老师接着说：“有了图的概念，你们去研究游迷宫问题就方便多了。现在我们假设怪物米诺陶就住在图 2 - 1 的迷宫的某处，请你们回去研究一下，提修斯带着一个线球能不能找到这个怪物并从迷宫入口出来？如果能找到，他该怎么走？下一次我们举行一次讨论会来讨论这个问题。要是你们有兴趣的话，可以做几个练习，用以加深对图这一新概念的理解。”说着，刘老师留下了几道练习题。练习一1 . 一中初三有 A 、B 、C三个班；二中初三也有三个班 A 、B 、C 。两校初三年级联合举办一次篮球友谊赛，规定每校的一个班级代表队要和另一个学校的三个班级代表

38、队各赛一次。如果友谊赛已结束，试用一个图表示这次友谊赛中，哪些队和哪些队进行过比赛。2 . 下图中顶点 A 、B 、C 分别表示三个工人；A 、B 、C 、D 分别表示四项不同的工种。如果工人 A 能干工种 B ，则在 A 、B 间连一条边，其余类推。试通过图指出，各工人能干一些什么工种？ 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 间连一条边。试通过图指出这个电器系统有几个元件？哪些元件间必

39、须用导线接通？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 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 Learning

40、materials?五 提修斯怎样找到怪物米诺陶？解迷宫问题的方法一按照刘老师的建议，这次数学爱好者协会的活动以讨论会的形式进行。讨论的题目是：提修斯怎样找到怪物米诺陶？黄杰上次听了林文的发言，本来就不太同意他的看法，但是讲不出个道理来。经过刘老师的启发，加上有了图的工具，他回去后认真地研究了图 4 - 6（b ）的图和自己编的一些简单的连通图，一边试验，一边总结规图 5 - 1 律，终于想出了办法。他举手要求第一个发言。得到刘老师的同意后，他先在黑板上画了一个表示图 2 - 1 迷宫的图（图 5 - 1 ），并把顶点和边标上符号。 e w c M V I M A G E , M V I M

41、A G E , ! 1 6 0 0 0 2 9 0 _ 0 0 3 8 _ 1 . b m p 他的发言要点如下：1 . 由于不知道怪物米诺陶藏在迷宫的什么地方，所以提修斯要想找到它，必须想出一个能走遍图 5 - 1 每条边至少一次的办法才行。2 . 引路线的作用，不仅可引导提修斯按照原路走出迷宫，而且可以指出哪些边走过了（这些边上布有引路线），哪些边还没走过（这些边上没有引路线）。上次林文同学的发言中忽略了引路线的第二个作用，才使他怀疑提修斯能找到米诺陶。其实只要注意到引路线的第二个作用，提修斯一定能找到米诺陶（当然要假设米诺陶不在迷宫里跟提修斯捉迷藏。这个假设是合理的，因为当时米诺陶并不知

42、道提修斯要去杀它）。提修斯可以这样走：进迷宫的门后，不断寻找没走过的边继续走，直到没有这种边的时候为止。这样，他就把图 5 - 1 的所有边都至少走过一遍了，然后再按原路走出来。黄杰说：“根据上面的想法，我在图 4 - 6 的两个图和其他一些连通图上都反复试过，找到了一种游迷宫的办法，其步骤是：1 . 从入口 A 任选一条边走到一个新顶点。2 . 当到达一个顶点 X 的时候，如果 X 与一些未走过的边相关联，就任选一条未走过的边走到另一个顶点 Y ；如果到达顶点 X的时候，所有和 X关联的边都已走过了，那就按原路返回。3 . 在返回的途中，还可能遇到有的顶点关联一些未走过的边，这时，从这些边中

43、任选一条，继续按步骤 2 的办法走。如果从某点返回到 A 的途中，没有发现任何一个和顶点（包括 A ）有关联又未走过的边，就可从 A 出来了。“返回途中，是有可能遇到有的顶点关联一些未走过的边的。例如在图5 - 1 中，我们从 A 出发，沿 e2走到 C ，再沿 e4走到 E ，从 E 走到 G ，以后一直往前走。当我们返回的时候，就在顶点 E 遇到 e6还没走过，到达顶点 C 的时候，就会发现 e3还没走过。“我按上面说的办法，试过好多连通图，不管是图 4 - 6 中的 （a ） 或 （b ） ，或者是其他连通图，都能走遍图中所有的边再从 A 出去。”接着他举出两个例子来说明这一方法。第一个

44、例子，使用一个比较简单的连通图，第二个例子，就用图 5 - 1 的图。在这两个例子中，都假设 A 是迷Learning materials?宫入口。【例 1 】在图 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 4 1 _ 1 . b m p 解：（1 ）从 A 出发，沿 e1走到 B ；由于 B 关联两条图 5 - 5 未走过的边，按步骤 2 可任选一条，例如沿 e2走到 C ；从 C 沿 e5走到 E ；E关联未走过的边 e4、e6，按步骤 2 从中任选一条，如沿 e6走到

45、F ；同样道理，沿 e8走到 H（图 5 - 3 ）。（2 ）在顶点 H ，没有关联未走过的边，按步骤 2 沿原路返回。沿 e8返回的时候，途经 F ，发现 e7未走过。按步骤 3 ，沿 e7走到 G （图 5 - 4 ）。（3 ）在顶点 G ，没有关联未走过的边，按步骤 2 ，顺原路返回，即走下面的路：G e7F e8H e8F e6E e （图 5 - 5 ）。（4 ）到 E 后，发现与 E 关联的边 e4还没走过，于是按步骤 3 ，沿 e4走到 D ，再沿 e3走到 B （图 5 - 6 ）。 e w c M V I M A G E , M V I M A G E , ! 1 6 0 0

46、 0 2 9 0 _ 0 0 4 2 _ 1 . b m p 图 5 - 6（5 ）走到 B 后，发现跟 B 关联的所有边都已走过了，按步骤 2 ，顺原路返回，即走下面的路：B e3D e4E e6F e8H e8F e7G e7F e8H e8F e6E e5C e2B e1A 。在这次返回过程中，没有发现和任何一个顶点（包括顶点 A ）有关联未走过的边，于是我们从 A 出来。上述走法，就是从 A 进去，走遍图中每条边至少一次，再从 A 出来的一种走法。【例 2 】在图 5 - 1 中按上述方法解迷宫问题。解：（1 ）从 A进去，有两条边 e1、e2可走，我们从中任选一条边走，例如选 e1，

47、接下去，仿例 1 的分析，我们可以走出如下的一条路（图 5 - 7 ）：A e1B e1A e2C e4E e6F e6E e5G e8H e1 0J e1 1I e7G 。（2 ）到 G 后，由于和 G 关联的所有边都走过了，于是按原路返回：从 G沿 e7走到 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 - 7H e9I e7G e7I e1 1

48、J 。（3 ）在 J 点，发现边 e1 2还没走过，于是可按下法走：J e1 2K e1 4M e1 4K 。（4 ）在顶点 K 发现 e1 3还没走过，于是从 K 经 e1 3。到 L 。（5 ）在顶点 L ，由于和 L 关联的边都已走过，于是按原路返回。这次可以顺原路线一直返回到 C ，然后经 e3到 D 。（6 ）同理，到 D 后，按原路线返回。这次返回到 A 的途中，不会遇到关联未走过边的顶点，所以能一直返回到 A ，并从 A 出来。同学们认真地听了黄杰介绍的办法后，都按这个办法在笔记本上试验，尽管走的路线不一样，但最终确实都走遍图中的每一边并且从 A 出来。一个新的问题产生了， 有的

49、同学提出： 黄杰总结的方法对图 5 - 1 和图 5 - 2Learning materials?是可行的，对其他连通图是否也一定可行？怎么证明这一点？对这个问题，黄杰一时也答复不出来。刘老师意识到，这个新问题的提出，说明同学们的思维往更深的层次发展了，这是一个十分可喜的现象。但是要对这一方法作一般证明，可能是同学们力所不及的。于是她决定亲自出马。她首先肯定了黄杰的发言。她说，黄杰同学从实验入手，从特例中探索走法，总结规律，从而提出了一种解迷宫问题的方法。这个方法，如果用游迷宫的普通语言可以叙述如下：游迷宫的方法一：1 . 进入迷宫后，可以任选一条通道往前走。2 . 碰壁就返回。3 . 到达一

50、个叉路口，观察是否有还没走过的通道，如果有，就任选一条往前走；如果没有，就顺原路返回到下一个叉路口，重复 2 和 3 。4 . 由原路返回迷宫入口处的时候，跟入口相连的各通道都已走过了，就从入口处出来。这时，迷宫里的每条通道都至少走过一次了。这方法不仅对图 5 - 1 和图 5 - 2 等特殊的图可行，而且我们可以证明对任一连通图都可行，即1 . 按照这个方法，的确能从 A 进去，再回到 A 。2 . 按照这个方法，从 A 出来的时候，每条边都已被走过至少一次。她说：“如果我们证明了这二点，那么方法一就成为一个正确的一般方法了。“如果上面这二点还没有证明，那么方法一还只能说是一个从实验、归纳得