神马文学网二、七桥问题和欧拉定理
来源：百度文库 编辑：神马文学网 时间：2024/04/20 00:45:14
二、七桥问题和欧拉定理
七桥问题。
关于一笔画，曾有一个颇为著名的哥尼斯堡七桥问题。事情发生在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都是奇结点，因此，它不能一笔画成，即不存在符合题目要求的曲线。
例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之间的两个门，就能设计出一条参观路线，一次不重复的穿过每一个门，并能回到原地。请你试一试，同时想一想，是否还存在其它的答案，一共有几种？