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