第七章图与树.pptVIP

欧拉简介 欧拉（Leonhard Euler 公元1707-1783年） 1707年出生在瑞士的巴塞尔（Basel）城，13岁就进巴塞尔大学读书，15毕业，16获得硕士学位，得到当时最有名的数学家约翰·伯努利的精心指导，欧拉是有名的数学家和自然科学家。 欧拉从19岁开始发表论文，直到76岁，据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%，彼得堡科学院为了整理他的著作，足足忙四十七年。 1725年约翰·伯努利的儿子丹尼尔·伯努利赴俄国，并向沙皇喀德林一世推荐了欧拉，这样，在1727年5月17日欧拉来到了彼得堡。1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1735年，欧拉解决了一个天文学的难题（计算慧星轨道），这个问题经几个著名数学家几个月的努力才得到解决，而欧拉却用自己发明的方法，三天便完成了。然而过度的工作使他得了眼病，并且不幸右眼失明了，这时他才28岁。1741年欧拉应普鲁士彼德烈大帝的邀请，到柏林担任科学院物理数学所所长，直到1766年，后来在沙皇喀德林二世的诚恳敦聘下重回彼得堡，不料没有多久，左眼视力衰退，最后完全失明。不幸的事情接踵而来，1771年彼得堡的大火灾殃及欧拉住宅，带病而失明的64岁的欧拉被围困在大火中，虽然他被别人从火海中救了出来，但他的书房和大量研究成果全部化为灰烬了。 在他完全失明之前，还能朦胧地看见东西，他抓紧这最后的时刻，在一块大黑板上疾书他发现的公式，然后口述其内容，由他的学生特别是大儿子A·欧拉（数学家和物理学家）笔录。欧拉完全失明以后，仍然以惊人的毅力与黑暗搏斗，凭着记忆和心算进行研究，直到逝世，竟达17年之久。 ?欧拉的记忆力和心算能力是罕见的，他能够复述年青时代笔记的内容，心算并不限于简单的运算，高等数学一样可以用心算去完成。有一个例子足以说明他的本领，欧拉的两个学生把一个复杂的收敛级数的17项加起来，算到第50位数字，两人相差一个单位，欧拉为了确定究竟谁对，用心算进行全部运算，最后把错误找了出来。欧拉在失明的17年中；还解决了使牛顿头痛的月离问题和很多复杂的分析问题。 欧拉的风格是很高的，拉格朗日是稍后于欧拉的大数学家，从19岁起和欧拉通信，讨论等周问题的一般解法，这引起变分法的诞生。等周问题是欧拉多年来苦心考虑的问题，拉格朗日的解法，博得欧拉的热烈赞扬，1759年10月2日欧拉在回信中盛称拉格朗日的成就，并谦虚地压下自己在这方面较不成熟的作品暂不发表，使年青的拉格朗日的工作得以发表和流传，并赢得巨大的声誉。他晚年的时候，欧洲所有的数学家都把他当作老师，著名数学家拉普拉斯（Laplace）曾说过：欧拉是我们的导师。 欧拉充沛的精力保持到最后一刻，1783年9月18日下午，欧拉为了庆祝他计算气球上升定律的成功，请朋友们吃饭，那时天王星刚发现不久，欧拉写出了计算天王星轨道的要领，还和他的孙子逗笑，喝完茶后，突然疾病发作，烟斗从手中落下，口里喃喃地说：我死了，欧拉终于停止了生命和计算。 ????欧拉的一生，是为数学发展而奋斗的一生，他那杰出的智慧，顽强的毅力，孜孜不倦的奋斗精神和高尚的科学道德，永远是值得我们学习的。［欧拉还创设了许多数学符号，例如π（1736年），e（1748年），sin和cos（1748年），tg（1753年），△x（1755年），Σ（1755年），f(x)（1734年）等。 图论起源： 哥尼斯堡七桥问题 在18 世纪,普鲁士的哥尼斯堡镇被普雷格尔河分成4 个部分。包括河两岸、中心岛以及两条支流之间所夹的部分,河上建有7 座桥连接着小镇的4 部分。 第七章 图论基础 7.1 图的基本概念 一、图的定义及有关术语 1、图的定义 图是二元组G=V, E,其中V是节点集合，E是边集合。 2、 专业术语 无向边，有向边，平行边，自回路（环，其边的方向没有意义），邻接点，邻接边，孤立点， 3、图的分类 有向图、无向图和混合图，简单图（不含平行边，自回路），完全图（每对节点之间有边相连）多重图（含平行边），边权图与点权图，平凡图（一个点）与零图（多个点，无边） 二、节点度 1、节点度定义 deg(vi) 表示与节点vi相关连的边的条数，其中含环节点度加2。 2、有向图节点度 节点入度：在有向图中，射入一个节点的边数称为该节点入度，记为deg— (vi) ； 节点出度：射出一个节点的边数为该节点的出度，记为deg+ (vi)； 节点度： deg(vi) = deg— (vi) + deg+ (vi) 3、节点的最大度和最小度 4、 定理 Kn边的条数: |E|=n(n-1)/2 其中n为节点数 5、任何图