《图论的起源ppt课件.ppt》由会员分享，可在线阅读，更多相关《图论的起源ppt课件.ppt（11页珍藏版）》请在三一办公上搜索。
1、图论的起源,什么是图论？1,图论诞生和孕育于民间游戏。创生：1736年 瑞士数学家欧拉图论之父；进展：1936年，匈牙利数学家寇尼希(Konig)发 表名著 有限图和无限图理论 1930年，波兰数学家库拉托父斯基(Kulatowsky)证明了平面图可以画在平面上。 其后，图论在现代数学、计算机科学、工程技术、优化管理等领域有大用而得以大力发展,Konisberg七桥问题(Euler问题),柯尼斯堡七桥问题是图论中的著名问题。 这个问题是基于一个现实生活中的事例:位于当时东普鲁士柯尼斯堡(今日俄罗斯加里宁格勒)有一条河，河中心有两个小岛。小岛与河的两岸有七条桥连接。如何才能在所有桥都恰巧只走一遍
2、的前提下，回到原出发点？,一、Konisberg七桥问题(Euler问题)1,如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点?,一、Konisberg七桥问题(Euler问题)2,不少数学家都尝试去解析这个事例。而这些解析，最后发展成为了数学中的图论。 莱昂哈德欧拉(Leonhard Euler)在1736年圆满地解决了这一问题，证明这种方法并不存在。他在圣彼得堡科学院发表了图论史上第一篇重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数。,一、Konisberg七桥问题(Euler
3、问题)3,A,C,B,D,A,C,B,D,如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点?,求从图中任一点出发，通过每条边一次，最后回到起点。,桥所连接的地区视为点,每一座桥视为一条线,一、Konisberg七桥问题(Euler问题)4,如果通奇数座桥的地方不止两个，那麽满足要求的路线便不存在了。 如果只有两个地方通奇数座桥，则可从其中一地出发可找到经过所有桥的路线。 若没有一个地方通奇数座桥，则从任何一地出发，所求的路线都能实现。 ,什么是图论？,图论是离散数学的分支： 图(graph)：是一个离散集和某些两元素子集的集合。 数学形象是：纸上画几个顶点，把其中一些点用曲线段或直线连起来
4、。图显示的是点与点之间的二元关系。,1 引论2,图论计算机问题求解的描述工具。,实际问题,数学模型,求解算法（算法）,编程实现,用大量数据验证,抽象,求解,测试,什么是图论？2,图论(Graphic Theory)的分支很多，例如：图论算法图论极值图论网络图论模糊图论代数图论随机图论超图论,欧拉生平简介,莱昂哈德欧拉(Leonhard Euler，1707.4.51783.9.18) 瑞士的数学家和物理学家。他被称为历史上最伟大的两位数学家之一（另一位是卡尔弗里德里克高斯）。欧拉出生于瑞士，在那里受教育。他是一位数学神童。作为数学教授，他先后任教于圣彼得堡(1727-1741)和柏林，尔后再返
5、圣彼得堡(1766)。 欧拉的一生很虔诚。然而，那个广泛流传的传说却不是真的。传说中说到，欧拉在叶卡捷琳娜二世的宫廷里，挑战德尼狄德罗：“先生，(a+b)n/n = x；所以上帝存在，这是回答！” 欧拉的离世也很特别：据说当时正是下午茶时间，正在逗孙儿玩的时候，被一块蛋糕卡在喉头窒息而死。 欧拉是第一个使用“函数”一词来描述包含各种参数的表达式的人，例如：y = F(x) (函数的定义由莱布尼兹在1694年给出)。他是把微积分应用于物理学的先驱者之一。欧拉是有史以来最多产的数学家，他的全集共计75卷。欧拉实际上支配了18世纪的数学，对于当时新发明的微积分，他推导出了很多结果。在他生命的最后7年中，欧拉的双目完全失明，尽管如此，他还是以惊人的速度产出了生平一半的著作。 小行星欧拉2002是为了纪念欧拉而命名的。,莱昂哈德欧拉,
