一笔画问题(学生).doc

七桥问题（一笔画问题）

沿着俄国和波兰的边界，有一条长长的布格河。这条河流经俄国的古城康尼斯堡——它就是今天俄罗斯西北边界城市加里宁格勒。
　　布格河横贯康尼斯堡城区，它有两条支流，一条称新河，另一条叫旧河，两河在城中心会合后，成为一条主流，叫做大河。在新旧两河与大河之间，夹着一块岛形地带，这里是城市的繁华地区。全城分为北、东、南、岛四个区，各区之间共有七座桥梁联系着。
　　人们长期生活在河畔、岛上，来往于七桥之间。有人提出这样一个问题：能不能一次走遍所有的七座桥，而每座桥只准经过一次？问题提出后，很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。最后，人们只好把这个问题向俄国科学院院士欧拉提出，请他帮助解决。

　　公元1737年，欧拉接到了“七桥问题”，当时他三十岁。他心里想：先试试看吧。他从中间的岛区出发，经过一号桥到达北区，又从二号桥回到岛区，过四号桥进入东区，再经五号桥到达南区，然后过六号桥回到岛区。现在，只剩下三号和七号两座桥没有通过了。显然，从岛区要过三号桥，只有先过一号、二号或四号桥，但这三座桥都走过了。这种走法宣告失败。欧拉又换了一种走法：
　　岛东北岛南岛北
　　这种走法还是不行，因为五号桥还没有走过。
　　欧拉连试了好几种走法都不行，这问题可真不简单！他算了一下，走法很多，共有
　　7×6×5×4×3×2×1=5040（种）。
　　好家伙，这样一种方法，一种方法试下去，要试到哪一天，才能得出答案呢？他想：不能这样呆笨地试下去，得想别的方法。
　　聪明的欧拉终于想出一个巧妙的办法。他用A代表岛区、B、C、D分别代表北、东、西三区，并用曲线弧或直线段表示七座桥，这样一来，七座桥的问题，就转变为数学分支“图论”中的一个一笔画问题，即能不能一笔头不重复地画出上面的这个图形。

　　欧拉集中精力研究了这个图形，发现中间每经过一点，总有画到那一点的一条线和从那一点画出来的一条线。这就是说，除起点和终点以外，经过中间各点的线必然是偶数。像上面这个图，因为是一个封闭的曲线，因此，经过所有点的线都必须是偶数才行。而这个图中，经过A点的线有五条，经过B、C、D三点的线都是三条，没有一个是偶数，从而说明，无论从那一点出发，最后总有一条线没有画到，也就是有一座桥没有走到。欧拉终于证明了，要想一次不重复地走完七座桥，那是不可能的。
天才的欧拉只用了一步证明，就概括了5040种不同的走法，从这里我们可以看到，数学的威力多么大呀！
【一笔画问题的规律】
早在18世纪，瑞士的著名数学家欧拉就找到了一笔画的规律。欧拉认为，能一笔画的图形必须是连通图。连通图就是指一个图形各部分总是有边相连的．
但是，不是所有的连通图都可以一笔画的。能否一笔画是由图的奇、偶点的数目来决定的。
数学家欧拉找到一笔画的规律是：
1．凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。
2．凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。
3．其他情况的图都不能一笔画出。（有偶数个奇点除以二便可算出此图需几笔画成）
比如附图：（a）为（1）情况，因此可以一笔画成；（b）（c）（d）则没有符合以上两种情况，所以不能一笔画成。
补充：相关名词的含义
◎顶点与指数：设一个平面图形是由有限个点及有限条弧组成的，这些点称为图形的顶点，从任一顶点引出的该图形的弧的条数，称为这个顶点的指数。
◎奇顶点：指数为奇数的顶点。
◎偶顶点：指数为偶数的顶点

引例：下面两个图是一个小朋友一笔画出的，你能画出来吗？试一试！
⑵
⑴

例1、 下列各图中，哪一幅能一笔画？试画出来？（）

⑴
⑵

例2、 下列各图中，哪些图能够一笔画成，试画出来；（）
⑴
⑵
⑶

⑷
⑸
⑹
⑺
B
A
E
D
C
F

图 号
⑴
⑵
⑶
⑷
⑸
⑹
奇 数 点

偶 数 点

能否一笔画成

例3、 下图是某公园的平面图，要使游客走遍每条路且不重复，问出入口应设在哪里？
N
M

哥尼斯堡七桥问题18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如图1所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。
　　　　B
C
G
J
I
H
D
E
F
A

例4、 下图是一座房屋的平面图，每两个相邻房间之间，都有一个门相通，除中间两人房间E和F以外，每个房间都有门通向室外，你能够不重复穿过每一道门吗？

思维训练题
1、 填空：
⑴
⑵
⑶
⑷

图⑴中，有 个奇点；有 个偶点；
图⑵中，有 个奇点；有 个偶点；
图⑶中，有 个奇点；有 个偶点；
图⑷中，有 个奇点；有 个偶点；
上面各图中， 能一笔画出； 不能一笔画出；

2、 下列各图中，哪些能一笔画出？哪些不能一笔画出？能一笔画出的，请把它们画出来。
⑴
⑵
⑶
⑷
⑸

⑹
⑺
⑻
⑼

3、 下图是某公园的平面图，要使游客走遍每条路，且不重复，问出入口应高在哪里？
A
B
C
D
E
F
G
H
K

第 5 页 共 5 页