《《图论问题起源》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图论问题起源》PPT课件.ppt（9页珍藏版）》请在装配图网上搜索。
1、图论问题起源 吴雪芬 刘姝 小问题 一笔画 世界数学难题 哥尼斯堡七桥问题 18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡 (今俄罗 斯加里宁格勒 )，那里的普莱格尔河上有七座桥。将河中 的两个岛和河岸连结，城中的居民经常沿河过桥散步，于 是提出了一个问题：一个人怎样才能一次走遍七座桥，每 座桥只走过一次，最后回到出发点？大家都试图找出问题 的答案，但是谁也解决不了这个问题 这就是哥尼斯堡七桥问题，一个著名的图论问题。 普通数学算法 著名数学家欧拉后来推论出此种走法是不可能的。他的论 点是这样的，除了起点以外，每一次当一个人由一座桥进 入一块陆地（或点）时，他（或她）同时也由另一座桥离 开此点。
2、所以每行经一点时，计算两座桥（或线），从起 点离开的线与最後回到始点的线亦计算两座桥，因此每一 个陆地与其他陆地连接的桥数必为偶数。 七桥所成之图形中，没有一点含有偶数条数，因此上述的 任务无法完成 欧拉的这个考虑非常重要，也非常巧妙，它正表明了数学 家处理实际问题的独特之处 把一个实际问题抽象成合 适的“数学模型”。这种研究方法就是“数学模型方法”。 这并不需要运用多么深奥的理论，但想到这一点，却是解 决难题的关键。 1736年，欧拉在交给彼得堡科学院的 哥尼斯堡 7座桥 的论文报告中，阐述了他的解题方法。他的巧解，为后来 的数学新分支 拓扑学的建立奠定了基础。 七桥问题和欧拉定理。欧拉通过对七桥问题的研究，不仅 圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明 了更为广泛的有关一笔画的三条结论，人们通常称之为 欧拉定理。对于一个连通图，通常把从某结点出发一笔画 成所经过的路线叫做欧拉路。人们又通常把一笔画成回到 出发点的欧拉路叫做欧拉回路。具有欧拉回路的图叫做欧 拉图。 一笔画： 凡是由偶点组成的连通图，一定可以一笔画成。画时可以 把任一偶点为起点，最后一定能以这个点为终点画完此图。 凡是只有两个奇点的连通图 (其余都为偶点 )，一定可以一 笔画成。画时必须把一个奇点为起点，另一个奇点终点。 其他情况的图都不能一笔画出。 (奇点数除以二便可算出此 图需几笔画成。 ) 答案
《图论问题起源》PPT课件.ppt
