七桥问题探究.pptx

《七桥问题探究.pptx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、七桥问题探究目录七桥问题的产生七桥问题的复杂欧拉与欧拉的解七桥问题的解小结七桥问题的产生18世纪，位于现立陶宛内的哥尼斯堡镇，一条河流叫普雷格尔河穿镇而过，河中有两个相邻的小岛，岛与岛、岛与陆地之间建有七座桥（如图，A、B为岛屿，C、D为两岸。）当时哥尼斯堡的居民经常到河边散步，或者到岛上买东西，有人提出了一个问题：一个人能否一次无重复地走遍所有的七座桥，最后回到出发点？当时，对这个问题谁也回答不了，这就是著名的“七桥问题”。聪明的你们能不能解答这个问题呢？七桥问题的复杂——走法……………………7…………

2、……6…………………5…………………4………………………3…………………………2…………………………11234567437657645765767七桥问题的复杂关键在于它的走法太多，右图只是示例，因为太过于复杂，在这里就不一一列举了，从树状图中我们可以知道至少有754321=5040种走法。那哪一种走法才符合条件呢？欧拉莱昂哈德·欧拉（LeonhardEuler，1707年4月15日～1783年9月18日），瑞士数学家、自然科学家。1707年4月15日出生于瑞士的巴塞尔，1783年9月18日于俄国圣彼得堡

3、去世。欧拉是18世纪数学界最杰出的人物之一，他不但为数学界作出贡献，更把整个数学推至物理的领域。1736年，一位小学教师写信给当时著名的数学家欧拉，请教对七桥问题的解答，这个问题引起了欧拉的极大兴趣，他用数学方法对七桥问题进行了深入的研究。欧拉的解答——一笔画问题欧拉发现该问题不是一个代数问题，也不是一个平面几何问题。该问题的解决仅依赖与陆地、岛屿、桥梁等的具体个数及其相互位置关系，因此可以把陆地看成“点”，将桥梁看作“线”（如下图的数学模型）。按照欧拉的思想，七桥问题就转化为以下问题：一笔画问题：能否从

4、图上某一点开始，笔不离纸、不重复的画出整个图形？我们知道，数学上把下图形称为一个图(graph)，其中的点称为顶点，线称为边，顶点集记为V，一个顶点记为v，边的集合记为E，一条边记为e。如果n条边e₁、e₂、e₃、……en首尾相连组成一个序列，其中ei链接顶点vi和vi+1（i=1，2，3，……n）称该序列为从端点v1到端点vn+1的链长为n的链。如果一个图的任意两顶点之间都有链相连，则称为连通图。把一个顶点v处引出边的条数叫做该顶点v的次数，顶点次数为奇（偶）数的顶点叫奇（偶）点。为了更好地理解，用右图

5、作说明，A、B、C、D为顶点，且任意两顶点之间都有链相连，所以很明显右图是连通图。根据概念可知，A、B、C、D均为奇点（A点引出了5条边，B、C、D引出了3条边）。我们也可以从此图中推出，所有顶点的次数总和必然是偶数，且在奇点处，必然有一条只进不出或只出不进的边（如右图中BD线没有进出与之对应），因而奇点的个数必为偶数。右图也是一个连通图，且A、B、C均为偶点。我们可以看到，在偶点处边线有进有出，进出对应。基于此，欧拉给出了如下的一笔画定理。定理1：一个图是一笔画的充要条件是：图形是连通的，并且奇点的个数

6、为0或2.同学们能不能根据下图分析一下奇点为0和奇点为2时的特点。AAB上图没有奇点，从任意一顶点（A）出发，最终也会到了那一顶点，且路线不会重复。上图有两个奇点（A、B），你会发现只有从一个奇点出发到另一个奇点终止，才能不重复的走完路线。定理2：当奇点个数为2时，一个奇点为起点，另一个则为终点；当奇点个数为0时，任取一个顶点，它是起点，也是终点。七桥问题的解讲到这里，大家是不是已经知道七桥问题的解了呢？现在，请大家看一下下面的图形，你们能不重复地走完全部路线吗？没错，这个图根本就无法不重复地走完全部路线

7、，原因在于它的奇点个数有四个，就意味着要想不重复，无论怎么走，最终都有两段是没走过的，这与七桥问题是一样的，所以我们可以知道，七桥问题其实是没有解的。小结欧拉一笔画定理：定理1：一个图是一笔画的充要条件是：图形是连通的，并且奇点的个数为0或2.定理2：当奇点个数为2时，一个奇点为起点，另一个则为终点；当奇点个数为0时，任取一个顶点，它是起点，也是终点。读读欧拉，读读欧拉，他是我们大家的老师。————拉普拉斯