第二讲从哥尼斯堡七桥问题谈起.pdf

《第二讲从哥尼斯堡七桥问题谈起.pdf》由会员分享，可在线阅读，更多相关《第二讲从哥尼斯堡七桥问题谈起.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二讲 从哥尼斯堡七桥问题谈起 故事发生在 18 世纪的哥尼斯堡城.流经那里的一条河中有两个小岛，还有七座桥把这两个小岛与河岸联系起来，那里风景优美，游人众多.在这美丽的地方，人们议论着一个有趣的问题：一个游人怎样才能不重复地一次走遍七座桥，最后又回到出发点呢？对于这个貌似简单的问题，许多人跃跃欲试，但都没有获得成功.直到 1836年，瑞士著名的数学家欧拉才证明了这个问题的不可能性。欧拉解决这个问题的方法非常巧妙.他认为：人们关心的只是一次不重复地走遍这七座桥，而并不关心桥的长短和岛的大小，因此，岛和岸都可以看作一个点，而桥则可以看成是连接这些点的一条线.这样，一个实际问题就转化为一个几何图形

2、（如下图）能否一笔画出的问题了.那么，什么叫一笔画？什么样的图可以一笔画出？欧拉又是如何彻底证明七桥问题的不可能性呢？下面，我们就来介绍这一方面的简单知识。数学中，我们把由有限个点和连接这些点的线（线段或弧）所组成的图形叫做图（如图（a）；图中的点叫做图的结点；连接两结点的线叫做图的边.如图（b）中，有三个结点：E、F、G，四条边：线段 EG、FG 以及连接 E、F 的两段弧.从图（a）、（b）中可以看出，任意两点之间都有一条通路（即可以从其中一点出发，沿着图的边走到另一点，如 A 到 I 的通路为 A H I 或 A D I），这样的图，我们称为连通图；而下图中（c）的一些结点之间却不存在通

3、路（如 M 与 N），像这样的图就不是连通图。所谓图的一笔画，指的就是：从图的一点出发，笔不离纸，遍历每条边恰好一次，即每条边都只画一次，不准重复.从上图中容易看出：能一笔画出的图首先必须是连通图.但是否所有的连通图都可以一笔画出呢？下面，我们就来探求解决这个问题的方法。为了叙述的方便，我们把与奇数条边相连的结点叫做奇点，把与偶数条边相连的点称为偶点.如上图（a）中的八个结点全是奇点，上图（b）中 E、F 为奇点，G 为偶点。容易知道，上图（b）可以一笔画出，即从奇点 E 出发，沿箭头所指方向，经过 F、G、E，最后到达奇点 F；同理，从奇点 F 出发也可以一笔画出，最后到达奇点 E.而从偶点

4、 G 出发，却不能一笔画出.这是为什么呢？事实上，这并不是偶然现象.假定某个图可以一笔画成，且它的结点 X 既不是起点，也不是终点，而是中间点，那么 X 一定是一个偶点.这是因为无论何时通过一条边到达 X，由于不能重复，必须从另一条边离开 X.这样与 X 连结的边一定成对出现，所以 X 必为偶点，也就是说：奇点在一笔画中只能作为起或终点.由此可以看出，在一个可以一笔画出的图中，奇点的个数最多只有两个。在七桥问题的图中有四个奇点，因此，欧拉断言：这个图无法一笔画出，也即游人不可能不重复地一次走遍七座桥.更进一步地，欧拉在解决七桥问题的同时彻底地解决了一笔画的问题，给出了下面的欧拉定理：凡是由偶点

5、组成的连通图，一定可以一笔画成；画时可以任一偶点为起点，最后一定能以这个点为终点画完此图。凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完；画时必须以一个奇点为起点，另一个奇点为终点。其他情况的图，都不能一笔画出。下面我们就来研究一笔画问题的具体应用：例 1 观察下面的图形，说明哪些图可以一笔画完，哪些不能，为什么？对于可以一笔画的图形，指明画法.分析与解答（a）图：可以一笔画，因为只有两个奇点 A、B；画法为 A 头部翅膀尾部翅膀嘴。(b）图：不能一笔画，因为此图不是连通图。（c）图：不能一笔画，因图中有四个奇点：A、B、C、D。（d）图：可以一笔画，因为只有两个奇点；画法为：A

6、C D A B E F G H IJ K B。（e）图：可以一笔画，因为没有奇点；画法可以是：A B C D E F G H I JB D F H J A。（f）图：不能一笔画出，因为图中有八个奇点。注意：在上面能够一笔画出的图中，画法并不是惟一的.事实上，对于有两个奇点的图来说，任一个奇点都可以作为起点，以另一个奇点作为终点；对于没有奇点的图来说，任一个偶点都可以作为起点，最后仍以这点作为终点。例 2 下图是国际奥委会的会标，你能一笔把它画出来吗？分析与解答 一个图能否一笔画出，关键取决于这个图中奇点的个数.通过观察可以发现，上图中所有的结点都是偶点，因此，这个图可以一笔画出.画时可以任一结

7、点作为起点。例 3 下图是某地区所有街道的平面图.甲、乙二人同时分别从 A、B 出发，以相同的速度走遍所有的街道，最后到达 C.如果允许两人在遵守规则的条件下可以选择最短路径的话，问两人谁能最先到达 C？分析与解答 本题要求二人都必须走遍所有的街道最后到达 C，而且两人的速度相同.因此，谁走的路程少，谁便可以先到达 C。容易知道，在题目的要求下，每个人所走路程都至少是所有街道路程的总和。仔细观察上图，可以发现图中有两个奇点：A 和 C.这就是说，此图可以以 A、C两点分别作为起点和终点而一笔画成.也就是说，甲可以从 A 出发，不重复地走遍所有的街道，最后到达 C；而从 B 出发的乙则不行.因此，甲所走的路程正好等于所有街道路程的总和，而乙所走的路程则必定大于这个总和，这样甲先到达 C。