第八讲 邮递线路问题一、多笔画

在第一册第八讲例 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（a）所示的图中共有 B、E、F、G、I、J 六个奇结点，所以不能一笔画成。如果我们将两个奇结点间的连线去掉一条，那么这两个奇结点就成为偶结点了。当我们把图中奇结点的个数减少到 2 个时，（想一想，奇结点个数为何不需减少到零个？）新的图就可以一笔画成了。

在图（a）中，第一笔画 BJ，第二笔画 GF。这样剩下 I、E 两个奇结点， 如图（b）所示，这个图是可以一笔画成的。所以这所房子至少要三笔才能画成。

由上述两个例题看到，如果图中有两个奇结点，一笔就能画出；有四个奇结点，至少两笔才能画出；有六个奇结点，至少三笔才能画出；如果图中有八个奇结点，利用同样的道理分析，至少四笔才能画成。一般地，一个连通图如果有 2n（n 为自然数）个奇结点，那么至少画 n 笔才能画成。我们把这类问题称作多笔画问题。