一笔画与七桥问题.pdf

一笔画与七桥问题 贵州省道真自治县旧城中学 张帮洪(邮编:563509)一笔画就是笔尖在不离开纸面的情况下,一次性画完某个封闭的图形。你能一笔画出下列图形吗?有的图形可以一笔画完,有的却不能,如何来判定一个图形是否为一笔画图形呢?对这一问题的研究还得追溯到十六世纪三十年代。在哥尼斯堡,即现在苏联加里宁格勒，布勒格尔河横贯其境。这条河有两条支流，中间汇合成大河，从而把该地区划分成 A、B、C、D 四块。在这四块土地上，有七座桥梁相连接，如图（1），图（1）人们成年累月的来往于此。于是有人就提出：能否一次走遍这七座桥，既不走重复又不走遗漏？这就是有名的“七桥问题”。1736 年，大数学家欧拉(公元 17071783 年)对七D B A C 桥问题着手研究，并在彼德堡科学院作了一次有趣的报告。把这一问题归结为如图（2）所示的一笔画问题，并得出一次性走完七桥是不可能的结论。C 原因在于 A、B、C、D 四个点都分出 A D 了奇数条叉道，奇数条叉道的点不 B 可能是一笔画中的“过路点”（即不是 图（2）起点，已不是终点），。因为“过路点”必须是偶数条叉道的交点，因此 A、B、C、D 四点必为起点或终点，但一笔画图形中只能有一个起点和一个终点（终点和起点可能为合在一起），故七桥问题得以解决。最后欧拉给了一笔画问题的判定方法：如果把线图中偶数条线的交叉点叫偶点，把奇数条线的交叉点叫奇点，那么，（1）线图中奇点个数不多于 2 个，这个图就是一笔画图形，否则就不是一笔画图形。（2）若没有奇点，则始点与终点重合，若有两个奇点，则始点与终点不重合，还必须从一个奇点画起，另一个奇点必须是终点。（3）奇点数目总是成双出现的。一笔画问题与七桥问题的解决，为解决最短邮路和规划问题提供了理论依据，为拓朴学的研究奠定了基础。因此欧拉对哥尼斯堡七桥问题的研究，成了拓朴学研究的先驱。