多笔画
-
第三讲
多笔画及应用问题
上一讲中，
我们主要研究了利用奇偶
点来判别一笔画，
学习了利用一
笔画来研究一些简单的实际问题
.
然而，实际生活中，许多问题的图并不
能一笔画出，也就是说，一笔画理论不能直接用来解决这些问题
.
因此，
在一笔画的基础上，我们有必要对这一类的问题作一些深入研究。
一、多笔画
我们把不能一笔画成的图，归纳为多笔画
.
首先，我们来考虑一个不
能一笔画成的图，
至少用几笔才能画完呢？
（为了研究的方便，
我们仍
然
只研究连通图，非连通图可转化为连通图
.
< br>）
下面，我们就用简单熟悉的图来研究这个问题
.
通过前面的学
习我们
已经知道：当奇点个数不是
0
或
2
时，图不能一笔画出
.
因此，我们可以
猜想；奇点个数是研究多笔画问题的关键。
< br>
观察下面的图形，并列出
奇点的个数与笔画数（至少几笔画完此图）
的关系表格。
为了表
示得清楚一些，
我们把图中第一笔画出的部分用实线表示，
第<
/p>
二笔画出的部分用虚线表示，
第三笔画出的部分用点线表示，
其余部分请
大家自己画出
.
奇点个数与笔画数的关系可列表如下：
容易看
出，笔画数恰等于奇点个数的一半
.
事实上，对于任意的连通<
/p>
图来说，如果有
2n
个奇点（
n
为自然数），那么这个图一定可以用
n
笔
画成
.
公式如下：<
/p>
奇点数÷
2=
笔画数，即
2n
< br>÷
2=n
。
细心的同学可能会问：
2n
是表示一个偶数，但假若有奇数个奇点怎
么办
？实际上，
这种情况不可能出现，
连通图中，
< br>奇点的个数只能是偶数
.
想一想，这是为什么呢？
例
1
观察下面的图，看各至少用几笔画成？
分析解答
（
1
）图中有
8
个奇结点，因此需用
4
笔画成。
（
2
）图中有
12
个奇点
，需
6
笔画成。
（
3
）图是无奇点的连通图，可一笔画成。
例
2
判断下面的图能否一笔画成；若不能，你能用什么方法把它改
成一笔
画？
分析解答
图中共有
4
个奇点，因此，显然无法一笔画成
.
要想改为一笔画，关
键在于减少奇点的数目
（把奇点的个数减少
到
0
或
2
）<
/p>
，
具体方法有两种：
①去边
.
即将多余的两奇点间的边去掉
.
这种方法只适用于多余的两
奇点间有边相
连的情况，如对下图就不适用
.
本题中，可去掉连结奇点
B
、
C
的边
BC
。
②添边
.
即在多余的两奇点间添上一条边
.
本题中，可以在奇点
A
、
C
间添上边
AC.
< br>添边的方法适用于任意多笔画的图。
改为一笔画时，
具体实现的方案很多
，
如本题中，
我们可以通过上述
两种方
法把奇点个数减少到
0
。
小结：对于有
2n
（
n
为大于
< br>1
的自然数）个奇点的连通图来说，改为
一笔画的方法一
般是：在多余的
n-1
（或
n
）对奇点间，各添上一条边；
如果这
n-1
对（或
n
对）奇点间都有边相连，也可以在
这
n-1
（或
n
）对
间各去掉一条边。
例
3
将下图改为一笔画
.
分析解答
图（<
/p>
1
）中有
6
个奇
点，因此可添上两条（或
3
条）边后可改为一笔
画；
又因为这个图中，
把这
6
个奇点任意分为
3
对后，
最多只有两对奇点
间有边相连，
因此，
可去掉两条边后改为一笔画，
举例如图
（
3
）
～
（
6
）
。