9.一笔画和多笔画
竞选体育委员演讲稿-山西对口高考成绩查询
第九讲 一笔画和多笔画
问题1 你能一笔画出一个“田”字吗？所谓一笔画出的意
思就是在一张纸上（不
允许折叠）笔不离纸，而且每一笔划（或称线段）只能画一次，不准重复。对于<
br>“串”字或“品”字呢？结果会怎样？（参看图8－1）
通过各种尝试发现，“
田”字总也不能一笔画成，而“串”字却可以一笔画
成。由于“品”字中的三个“口”字不连在一起，显
然也不能一笔画成。
我们把那些能一笔画成的图形叫一笔画。一笔画问题主要讨论什么样的图形
可以一笔画成。
例1 下列图形哪些能一笔画成？哪些不能一笔画成？
经过尝试，你会发现，
图8－2（a）、（c）、（e）是可以一笔画成的。而
且图（c）、（e）可从任意一点出发，一笔画
成回到出发点，而图（a）只能从
A（或D）点出发，一笔画成到D（或A）点结束。
如
果图形非常复杂，用这种逐一尝试的方法，则所花的时间较多，且有时还
无法下结论。有没有一种简便的
判断方法呢？下面就来研究这个问题。
上面研究的图形都是由点和线段（或弧）组成的，在数学中
叫做图。图形中
的点叫图的结点，线段（或弧）叫做图的边。作为一个图，其图形还必须满足以
下条件：
（1）每条边都有两个端点（可以重合）作为结点；
（2）各条边之间互不相交。
一个图完全由它的结点和边的个数以及它们相互连结的情况来确定，而与边
的曲直长短无关。
图中与一个结点相连结的边的条数称为这个结点的度数。度数为偶数的结点
叫做偶结点。例如，图8－3
中结点C、D、E都是偶结点。度数为奇数的结点叫
做奇结点。例如，图8－3中结点A、B、F、G都
是奇结点。
任何两点间都有线连接的图称作连通图。（如图8－3中D与G可通过DB、
BA、AG连接）
观察例1中的五个图，其结点的奇偶性可列成下表：
从表中可以发现，一个图能否一笔画成，与图的奇结点的个数有密切联系，
人们总结出如下规律：
一个图若是一笔画必定是个连通图。
一个连通图，若没有奇结点（即全是偶结点），
那么这个图一定可以一笔画
成，而且可以从任一偶结点出发，一笔画成回到出发点。
一个
连通图，若只有两个奇结点，那么这个图也可以一笔画成。而且只能从
某一奇结点出发一笔画成，到另一
奇结点结束。
一个图，若奇结点个数多于两个，那么这个图就不能一笔画成。
例2
判断下列各图是否能一笔画出来。
解：其中（b）、（d）、（e）三个图无奇结点，所以
可从任一点出发，一笔画
成，并且回到出发点；（a）、（f）两图各有两个奇结点，所以可从其中一个
奇
结点出发，一笔画成，到另一个奇结点结束；而图（C）的八个结点都是奇结点，
所以不能一
笔画出来。
当作练习，请把例2中能够一笔画的图一笔画出来。
二、七桥问题和欧拉定理
问题2 七桥问题。
关于一笔画，曾有一个颇为著名
的哥尼斯堡七桥问题。事情发生在18世纪
的哥尼斯堡，有一条河流从这个城市穿过，河中有两个小岛A
、B，河上有七座
桥连结两个小岛及河的两岸（参看图8－5），那里的居民在星期日有散步的习
惯。有的人想，能不能一次走遍七座桥，每座桥只走过一次，最后回到出发点？
这个问题似乎不难，谁
都想试一试，但谁也没有找到答案。后来有人写信请教著
名的瑞士数学家欧拉。欧拉的头
脑比较冷静，千百人的失败使他猜想：也许那样
的走法根本就不存在。1936年他证明了自己的猜想。
欧拉解决七桥问题的方法独特，思想新颖，非常富有启发性。他用点表示小
岛和
两岸，用连结两点的线段表示连结相应两地的桥，得到由七条线段连结四个
点而成的图形（参看图8－5
（b））。这样七桥问题就变成了一个一笔画问题：
能不能一笔画出这个图形，并且最后返回起点？前面
我们虽然通过对例1的分析
归纳出了一个连通图是否能一笔画出来的三条结论，但并没有证明，没有说明
这
是为什么。下面我们简要说明其中的道理。
一个连通图能否一笔画成主要是与结点的边
数（也称度数）有关。假定某个
图能一笔画成，如果结点P不是起点或终点，而是中间点，那么P一定是
个偶结
点。因为无论何时通过一条边进入P，由于不能重复，必须从另一条边离开P，
因此与P
连结的边一定成对出现，所以P是偶结点。如果一个结点Q是奇结点，
那么在一笔画中只能是起点或终点
。由此可以看出，在一个一笔画中，奇结点个
数至多只能有两个。
由于哥尼斯堡七桥问题
相应的图中有四个奇结点，所以不能一笔画成。也就
是说，七桥问题无解，证实了欧拉的猜想。
欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，
而且得到并证明
了更为广泛的上述有关一笔画的三条结论，人们通常称之为欧拉
定理。1736年，欧拉在圣彼得堡科学
院作了一次报告，公布了他关于七桥问题
的研究成果。欧拉在研究中提出了一种新颖的数学问题及思想方
法，它标志着一
门崭新的数学学科——图论的诞生。
对于一个连通图，通常把从某结点出发一笔画成所经过的路线叫做欧拉路。
例如，图8－6（a）
中的图无奇结点，可以从A点出发，一笔画成回到A点，
其路线为A→D→E→H→D→G→H→I→F
→E→B→F→C→B→A。图8－6（b）中的
图有两个奇结点C和E，可以从E出发一笔画成，到C
结束。其路线为E→D→C
→B→A→C。这两条路线都是欧拉路。应当注意：一个图如果存在欧拉路，
那么
不一定是唯一的。
人们又通常把一笔画成回到出发点的欧
拉路叫做欧拉回路。具有欧拉回路的
图叫做欧拉图。例如，图8－6（a）所表示的路线就是一条欧拉回
路，因此相应
的图就是一个欧拉图。
例3
图8－7是一公园的平面图，线段表示路径，要使游客走遍每条路且不重复，
问出入口应设在哪里？
分析与解：这个问题实质上是一个一笔画问题。图中只有两个奇结点C和E，因
此，
只要把出入口分别设在这两个奇结点处，游客就能由入口进入公园，不重复
地走遍每条路，然后从出口处
离开公园。
例4
能否一笔画出一条曲线，使它和图8－8中的八条线段都只相交一次（不准
在端点处相交）？
分析与解：尝试几次后，会感到很难下结论。事实上，直接寻找答案并不容易。
我们可从七桥问
题得到启示。原图形把平面分成了五个部分，分别用A、B、C、
D、E五个点表示。两个点之间的连线
正好用来表示与相应的线段相交一次，如
图8－8（b）。于是，问题就变成了图8－8（b）中所表示
的图能否一笔画成。
因为图中A、B、C、D都是奇结点，因此，它不能一笔画成，即不存在符合题目<
br>要求的曲线。
例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（a）所示的
图中共有B、E、F、G、I、J六个奇结点，所以
不能一笔画成。如果我们将两个奇结点间的连线去掉
一条，那么这两个奇结点就
成为偶结点了。当我们把图中奇结点的个数减少到2个时，（想一想，奇结点
个
数为何不需减少到零个？）新的图就可以一笔画成了。
在图（a）中，第一笔画BJ，
第二笔画GF。这样剩下I、E两个奇结点，如
图（b）所示，这个图是可以一笔画成的。所以这所房子
至少要三笔才能画成。
由上述两个例题看到，如果图中有两个奇结点，一笔就能画出；有四个奇结
点，至少两笔才能画出；有六个奇结点，至少三笔才能画出；如果图中有八个奇
结点，利用同样
的道理分析，至少四笔才能画成。一般地，一个连通图如果有
2n（n为自然数）个奇结点，那么至少画
n笔才能画成。我们把这类问题称作多
笔画问题。
四、邮递路线
问题 一个邮
递员每次送信，要走遍他负责投递的范围内的街道，完成任务
后回到邮局。问他按怎样的路线走，所走的
路程最短？
这个问题叫做最短邮递路线问题，是一个即有趣又实用的问题。
例3 图8
－4（a）、（b）都表示街道图。图中A是邮局的位置，问邮递员应如
何设计他的邮递路线，才能使他
所走的路程最短？
分析与解：由于（a）所表示的图无奇结点，所以是一
个欧拉图。他可以从邮局
出发，不重复地走遍每条街道，回到邮局，这就是投递员的最短路线。而（b）
所表示的图有六个奇结点，它不是一笔画，要不重复地走遍街道是不可能的。为
了走遍所有的街
道，必须重复走某些街道。重复走哪些街道才能使总路程最短
呢？
由于任何一个图中奇结
点的个数都是偶数，所以可把奇结点两两配对。如果
在一对奇结点之间连一条虚线当作增添的重复边，奇
结点就变成了偶结点，用这
种方法可使原来的图变成没有奇结点的欧拉图（增添了重复边）。现在的问题
是
如何去连这些虚线，才能保证总路程最短。其原则是：
（1）连线（虚线）不能有重叠线段；
（2）在每一个圈上，连线长度之和不能超过圈长的一半。
例如，图8－5（a）中，连虚线时在KG一段上发生重叠。根据原则（1），
应去掉重叠部分改成图8－5（b）。但在（b）中，对于BKJCB这个圈来说，增
添的虚线长超过圈
长的一半。根据原则（2），可以继续改进成（c）中增添虚线
的情形，这是一种最好的增添虚线的方法
。因此，最好的投递路线是ABCDE－
FIFJCBKGFGHNA（参看图8－6）
例4 图8－7表示某城市的街道图，九个区都是边长为1公里的正方形，现需设
一牛奶站，希
望找一最佳地址，要能使送奶车以最短路程跑遍城市的所有街道，
然后返回奶站。如果小明把奶站选在P
点，试问他选的地方对吗？送一遍奶所走
的最短路程比该城市全部街道的总长长多少？
<
/p>
分析与解：由于图8－7中有8个奇结点，所以必须重复走某些街道，才能送遍
全
城回到奶站。根据例3中的两条原则，重复路线可添设如图8－8。这样图中
的结点全部为偶结点，说明
奶站设在街道任何一处都一样。因此，小明选在P
点没有错。一次送遍全城回到奶站的最短路程应是24
＋4＝28（公里）比城市全
部街道总长多4公里，多走城市街道总长的16.7%。
习题十六
1．判断下列各图能否一笔画成。若不是一笔画，则至少几笔才能画成？
2．各单位在图中用数字标出，彼此间有路相通。一邮递员从邮局出发，向
各单
位传递邮件，他能否不走重复路线，也不经重复单位，又回到邮局？
3．一个邮递员投递信件的街
道如图所示。图上数字表示各段街道的公里数。
他从邮局出发，要走遍各街道，最后回到邮局，请为他设
计一条最合理的路线，
全程要走多少公里？
4．一个投递员投递的街区如图所
示。图上数字表示各街道的长度。他从邮
局出发，走遍各街道，最后回到邮局。请为他设计一条最优投递
路线，并求出全
程的公里数。
参考答案：
1
．（a）有两个奇结点，可以一笔画成；（b）有8个奇结点，需四笔画成；（c）
有4个奇结点，需两
笔画成；（e）有10个奇结点，需五笔画成；（d）、（f）
没有奇结点，是欧拉图，可以一笔画成回
到起点。
2．能。路线可以这样设计：邮局→21→17→18→12→11→6→5→2→1→
4
→3→8→7→13→14→19→20→15→9→10→16→邮局
3．全程要走46公里，邮递路线如下图。
4．需要重复走的路段为FG、BC、DI
和JNM。最佳路线为：邮局→F→A→B
→G→F→G→H→C→B→C→D→I→D→E→J→H→
M→N→J→N→M→邮局，全程要走
33公里。