哥尼斯堡七桥问题与一笔画

请你做下面的游戏：一笔画出图1的图形来.规则：笔不离开纸，每根线都只能画一次.你能画出来吗？

如果你画出来了，那么请你再看图2能不能一笔画出来？

虽然你动了脑筋，但我相信你肯定不能一笔画出图2！这就是一笔画问题，它是一种有名的数学游戏.

所谓一笔画指的是：从图的一点出发，笔不离纸，遍历每条边恰好一次，即每条边都只画一次，不准重复.从图1中容易看出：能一笔画出的图首先必须是连通图.但是否所有的连通图都可以一笔画出呢？

有关这个问题的讨论，要追溯到两百多年前的一个著名问题——哥尼斯堡七桥问题.十八世纪，东普鲁士哥尼斯堡城（今俄罗斯加里宁格勒）有一条河叫普莱格尔河，它有两个支流，在城市的中心汇成大河，中间是岛区，河上有7座桥，将河中的两个岛和河岸连接，如图3所示.由于岛上有古老的哥尼斯堡大学，有教堂，还有哲学家康德的墓地和塑像，因此城中的居民经常沿河过桥散步.渐渐地，爱动脑筋的人们提出了一个问题：一个散步者能否一次走遍7座桥，而且每座桥只许通过一次，最后仍回到起始地点？这就是哥尼斯堡七桥问题，一个著名的图论问题.

这个问题看起来似乎并不难，但人们始终没有能找到答案.最后，问题被提到了大数学家欧拉那里.欧拉以深邃的洞察力很快证明了这样的走法是不存在的.欧拉是这样解决问题的：既然陆地是桥梁的连接点，不妨把图中被河隔开的陆地看成4个点，将7座桥看成7条连接这4个点的线，如图4所示.

于是“七桥问题”就等同于图5中所画图形的一笔画问题了.欧拉注意到，如果一个图能一笔画成，那么一定是由一个起点开始画，也有一个终点.图上其它的点是“过路点”——画的时候要经过它.现在看“过路点”具有什么性质.它应该是“有进有出”的点，有一条边进这点，那么就要有一条边出这点.不可能是有进无出，如果有进无出，它就是终点；也不可能有出无进，如果有出无进，它就是起点.因此，在“过路点”进出的边的总数应该是偶数，即“过路点”是偶点.

于是，我们把一个图形中与偶数条线相连接的点叫做偶点.相应地，把与奇数条线相连接的点叫做奇点.一个图形能否一筆画成就有了一个判别准则： （1）能一笔画出的图形必须是连通的图形；（2）凡是只由偶点组成的连通图形，一定可以一笔画出.画时可以由任一偶点为起点.最后仍回到这点；（3）凡是只有两个奇点的连通图形一定可以一笔画出，画时必须以一个奇点为起点，以另一个奇点为终点；（4）奇点个数超过两个的图形，一定不能一笔画出.

现在对照七桥问题的图，所有的顶点都是奇点，共有四个，所以这个图肯定不能一笔画成.欧拉对“七桥问题”的研究是图论研究的开始，同时也为拓扑学的研究提供了一个初级例子.

【例题赏析】

例1 下图6不能一笔画成，请你在下图中添加最少的线段，将其改成一笔画的图形，并画出路线图.

解析：不能一笔画出，因为图中有E H G F四个奇点，连接EH就可以将图形一笔画出.

例2 上图7中的线段表示小路，请你仔细观察，认真思考，能够不重复爬遍小路的是甲蚂蚁还是乙蚂蚁？该怎样爬？

解析：要想不重复爬，需要能将图形一笔画出.由于图中有两个奇点，所以应该从奇点出发才能一笔画出图形，所以甲蚂蚁能够.

例3 如图8邮递员叔叔向11个地点送信，如不想走重复路，怎样走最合适？

解析：不走重复路，一笔能画出路线图，图中有2个奇点，应该从奇点处出发.下面有一种参考路线：4-1-2-5-8-9-6-10-11-7-4-3.

【智力比拼】

1.下面的图形都不能一笔画成，你能否在图中添上一条线段，使它能一笔画成.

2.下图是儿童乐园的道路平面图，要使游客走遍每条路并且不重复路线，那么出、入口应设在哪里？

3.下图是国际奥林匹克运动会的会标，能一笔画成吗？如果能，请你把它画出来.