9.一笔画和多笔画.doc

第九讲 一笔画和多笔画
问题1 你能一笔画出一个“田”字吗？所谓一笔画出的意思就是在一张纸上（不允许折叠）笔不离纸，而且每一笔划（或称线段）只能画一次，不准重复。对于“串”字或“品”字呢？结果会怎样？（参看、B、C、D都是奇结点，因此，它不能一笔画成，即不存在符合题目要求的曲线。
例5 图8－9表示一个展览馆的平面图，其中共有五个展览室，每个展览室都有一个门通向室外。能否设计一条参观路线，一次不重复地穿过每一个门并能回到原地。
分析与解：如果用A、B、C、D、E表示展览室，用F表示室外，用连线表示相应的门，那么图8－9（a）就变成了图8－9（b）于是问题就转化为判断图8－9（b）是否为欧拉图。
　　由图中可以看出，点C、D、E、F都是奇给点，因而图8－9（b）不具有欧拉回路。所以不是欧拉图。也就是说，不存在题中所要求的那种参观路线。
　　可以进一步考虑，关闭了哪两个门之后，就能设计出符合题中要求的参观路线了？为此，只要使图8－9（b）变为欧拉图，即使它的奇结点个数为O即可。例如抹去线段CD和EF后的图就没有奇结点了。也就是说，如果关闭C、D之间和E、F之间的两个门，就能设计出一条参观路线，一次不重复的穿过每一个门，并能回到原地。请你试一试，同时想一想，是否还存在其它的答案，一共有几种？
三、多笔画
　　在第一册第八讲例1中，我们讨论了下列图形的一笔画问题。
　　通过观察列出了下表：
　　由此表我们发现，一个图能否一笔画成与图的奇结点的个数有关系。如果我们再进一步观察，还可发现，这些图中的奇结点的数目都是偶数。这是一种偶然的巧合还是一种普遍的规律呢？如果我们再观察一些其它的图，结果也是没有出现奇结点数目是奇数的现象。于是我们可以作如下猜想：
　　在任何一个图中，奇结点的个数一定是偶数。
　　这是因为一个图的每条边都与两个结点相连结，所以，如果把一个图的所有结点的度数相加，由于每条边都计算了两次，其度数和是边数的2倍，它是偶数，可设为2n。又因为每个偶结点的度数都是偶数，它们的度数和当然是偶数，可设为2m。由此可知，所有奇结点的度数和为
　　2n－2m＝2（n－m）（n、m为自然数）
　　也是一个偶数，但每个奇结点的度数都是奇数，所以奇结点的个数一定是偶数。否则，如果奇结点的个数是奇数，那么，因为奇数个奇数的和是奇数，就得到所有奇结点度数的和是奇数。这与上述结论相矛盾。这就说明，在任何一个图中，奇结点的个数一定是偶数。
例1 先数一数下列各图形中奇结点的个数。如果有的图形不能一笔画成，那么，至少几笔才能画成？
分析与解 ：图8－2（a）中只有两个奇结点，根据欧拉定理，可从A点出发一笔画出到B点结束，图（b）中有四个奇结点，不能一笔画成。图8－2（b）与图（a）比较，多出了折线CEFD。如果先一笔画出图（a），再添一笔画出折线CEFD，就可得到图（b）。因此，图（b）至少两笔才能画成。图8－2（c）中共有六个奇结点，也不能一笔画成。图（c）与图（b）比较又多出了一面旗子。它也含有两个奇结点，于是在两笔画出图（b）的基础上，再添一笔画上旗子，就成了图（c）。因此，图（c）至少三笔才能画成。
例2 图8－3（a）表示一所房子，问至少几笔才能画成？
分析与解：1图8－3