哥尼斯堡七桥问题：模型应用

《哥尼斯堡七桥问题：模型应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、【模型应用】例1观察下面的图形，说明哪些图可以一笔画完，哪些不能，为什么？对于可以一笔画的图形，指明画法.　（a）图：可以一笔画，因为只有两个奇点A、B；画法为A→头部→翅膀→尾部→翅膀→嘴。　(b）图：不能一笔画，因为此图不是连通图。　（c）图：不能一笔画，因图中有四个奇点：A、B、C、D。　（d）图：不能一笔画，因为此图不是连通图。　（e）图：可以一笔画，因为没有奇点；画法可以是：A→B→C→D→E→F→G→H→I→J→B→D→F→H→J→A。　（f）图：不能一笔画出，因为图中有八个奇点。　

2、　注意：在上面能够一笔画出的图中，画法并不是惟一的.事实上，对于有两个奇点的图来说，任一个奇点都可以作为起点，以另一个奇点作为终点；对于没有奇点的图来说，任一个偶点都可以作为起点，最后仍以这点作为终点。例2下图是国际奥委会的会标，你能一笔把它画出来吗？　　一个图能否一笔画出，关键取决于这个图中奇点的个数.通过观察可以发现，上图中所有的结点都是偶点，因此，这个图可以一笔画出.画时可以任一结点作为起点。例3下图是某展览厅的平面图，它由五个展室组成，任两展室之间都有门相通，整个展览厅还有一个进口和一个

3、出口，问游人能否一次不重复地穿过所有的门，并且从入口进，从出口出？这种应用题，表面看起来不易解决，事实上，只要认真分析，就可以发现：我们并不关心展室的大小以及路程的远近，关心的只是能否一次不重复地走遍所有的门，与七桥问题较为类似.因此，仿照七桥问题的解法，我们可以把每个展室看作一个结点，整个展厅的外部也看作一个点，两室之间有门相通，可以看作两点之间有边相连.这样，展厅的平面图就转化成了我们数学中的图，一个实际问题也就转化为这个图（如下图）能否一笔画成的问题了，即能否从A出发，一笔画完此图，最后再

4、回到A。　　上图（b）中，所有的结点都是偶点，因此，一定可以以A作为起点和终点而一笔画完此图.也即游人可以从入口进，一次不重复地穿过所有的门，最后从出口出来.　　下面仅给出一种参观路线：　　A→E→B→C→E→F→C→D→F→A。注意：本题中，必须以A分别作为起点和终点.这就要求图中必须没有奇点，否则，若有两个奇点，虽能一笔画出，但与从入口入、出口出（即游人的出发和终止点都在展厅外）有矛盾，其他有多个奇点的情况则根本不可能一笔画出。另外，通过前面的学习，大家已经知道：一个图如果能够一笔画出，则画

5、的方法不止一种，但各种方法大同小异.因此，一般我们只给出一种画法。