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

作者: 孙永(山东)

哥尼斯堡地方有一条布勒尔河。这条河两个支流,在城中心汇合成大河。中间是岛区。岛和河的两岸有7座桥相连,如图1所示。

图1

哥尼斯堡的大学生,在傍晚散步时,总想一次走过7座桥,而每座桥只允许走一遍。但试来试去,谁都没有成功。于是便写信提请著名的数学家欧拉解决。当时欧拉只有二十多岁,王在俄国圣彼得堡科学院任职,他想了几天,彻底解决了这一问题。这是发生在1735年的故事。现在王老师讲完这个故事之后,与刘徽数学小组成员共同来展示解决这个问题的思维过程。

师:“岛与半岛无非是桥梁连接地点,两岸陆地也是桥梁通往的地点,那么就不妨把这4处地方缩小成A,B, C, D 4个点,并把7座桥表示成7条线。这样简化并不影响我们问题的性质。这样一来,图1就简化成图2。于是,一次无重复地走过7座桥的问题,就转化为图2的图形的一笔画问题。

图2

“谁能把图2 一笔画出来?”

大家在试画着。停了一会,王老师又展示出一组图形(图3～图9),让大家把这些图形试着一笔画出。

师:“哪些图形可以一笔画出?”

甲生:“图3、图4可以一笔画出。具体画法分别为A→B→,A→B→C→B→A。”

乙生:“图5、图6、图7也可以一笔画出,具体画法分别为 A→B→C→B→A→D-C;A→B→C→D→A→C→E→B; B→E→F→A→B→C→D→E。”

丙生:“还有图9也能一笔画出,具体画法为A→B→H→I→D →F→I →B → C →D→E→F→G→H→A。”

师:“剩下的图2、图8能否一笔画出? ”

图3

图4

图5

图6

图7

图8

图9

丁生:“图2、图8不能一笔画出。”

师:“为什么有些图形能够一笔画出?有些图形不能一笔画出?这可考虑图形的结构特征。”

大家在思考着,王老师又作了如下启发:

“可以把由一点出发的线条数目一一标记出来。”

于是刘徽小组成员把图2 到图9的图形上的点的线条数标记如下图2'～图9'。

师:“一笔画中间经过的一些点有什么特点?”

甲生:“中间经过的点的曲线一进一出,其数目都是偶曲数。”

师:“这就是说,中间点处经过的曲线条数一定是偶数。这样的点,称为偶点。一笔画的起点和终点是否也是偶点?”

乙生:“不一定。当起点和终点重合时,为偶点,不重合时,不是偶点。”

师:“这就是说,起点和终点通过的曲线的条数可能是奇数条。当一个总通过的曲线条数为奇数时,该点称为奇点。”

丙生:“从图可看出,一笔画的图形中诸点都是偶点,这时起点和终点重合。”

G生:“一笔画的图形中只有两个奇点,且其中一个奇点为起点,另一个奇点为终点。”

师:“这样一来,我们就得到一笔画图形的必要条件为奇点的数目为0或2。利用这个条件我们可以判断一个图形是否能一笔画出。”

甲生:“在图2中有4个奇点,所以图2不能一笔画出。”

乙生:“在图8中也有4个奇点,故图8也不能一笔画出。”

师:“当年欧拉指出,奇点是0或2同时也是一笔画的充分条件,并从理论上证明了一笔画图形的充要条件是其奇点的数目是0或2。本世纪发展起来有着广泛应用的一个崭新数学分支——图论,若追溯其历史渊源,当追溯到欧拉对哥尼斯堡七桥问题的解决。

图2

图3

图4

图5

图6

图7

图8

图9