第三讲从哥尼斯堡七桥问题谈起

第三讲 从哥尼斯堡七桥问题谈起　故事发生在18世纪的哥尼斯堡城.流经那里的一条河中有两个小岛，还有七座桥把这两个小岛与河岸联系起来，那里风景优美，游人众多.在这美丽的地方，人们议论着一个有趣的问题：

精品资源 第三讲从哥尼斯堡七桥问题谈起 故事发生在18世纪的哥尼斯堡城.流经那里的一条河中有两个小岛，还有七 座桥把这两个小岛与河岸联系起来，那里风景优美，游人众多.在这美丽的地方， 人们议论着一个有趣的问题：一个游人怎样才能不重复地一次走遍七座桥，最后 又回到出发点呢？ 对于这个貌似简单的问题，许多人跃跃欲试，但都没有获得成功.直到1836 年，瑞士著名的数学家欧拉才证明了这个问题的不可能性。 欧拉解决这个问题的方法非常巧妙.他认为：人们关心的只是一次不重复地 走遍这七座桥，而并不关心桥的长短和岛的大小，因此，岛和岸都可以看作一个 点，而桥则可以看成是连接这些点的一条线.这样，一个实际问题就转化为一个 几何图形（如下图）能否一笔画出的问题了. 那么，什么叫一笔画？什么样的图可以一笔画出？欧拉又是如何彻底证明七 桥问题的不可能性呢？下面，我们就来介绍这一方面的简单知识。 数学中，我们把由有限个点和连接这些点的线（线段或弧）所组成的图形叫 做图（如图（a））；图中的点叫做图的结点；连接两结点的线叫做图的边.如图 （b）中，有三个结点：E、F、G，四条边：线段EG、FG以及连接E、F的两段弧. 从图（a）、（b）中可以看出，任意两点之间都有一条通路（即可以从其中一点 出发，沿着图的边走到另一点，如A到I的通路为A→H→I或A→D→I…），这 样的图，我们称为连通图；而下图中（c）的一些结点之间却不存在通路（如M 与N），像这样的图就不是连通图。 所谓图的一笔画，指的就是：从图的一点出发，笔不离纸，遍历每条边恰好 一次，即每条边都只画一次，不准重复.从上图中容易看出：能一笔画出的图首 先必须是连通图.但是否所有的连通图都可以一笔画出呢？下面，我们就来探求 解决这个问题的方法。 为了叙述的方便，我们把与奇数条边相连的结点叫做奇点，把与偶数条边相 连的点称为偶点.如上图（a）中的八个结点全是奇点，上图（b）中E、F为奇点， G为偶点。 欢迎下载