第八章 一些特殊的图精选文档.ppt

第八章第八章 一些特殊的图一些特殊的图本讲稿第一页，共四十四页8.2 欧拉图欧拉图1736年年瑞瑞士士数数学学家家欧欧拉拉发发表表了了图图论论的的第第一一篇篇著著名名论论文文“哥哥尼尼斯斯堡堡七七桥桥问问题题”(下下称称七七桥桥问问题题)。这这个个问问题题是是这这样样的的：哥哥尼尼斯斯堡堡城城有有一一条条横横贯贯全全城城的的普普雷雷格格尔尔河河，城城的的各各部部分分用用七七桥桥联联结结，每每逢逢节节假假日日，有有些些城城市市居居民民进进行行环环城城周周游游，于于是是便便产产生生了了能能否否“从从某某地地出出发发，通通过过每每桥桥恰恰好好一次，在走遍了七桥后又返回到原处一次，在走遍了七桥后又返回到原处”的问题。的问题。本讲稿第二页，共四十四页图图8.1.1本讲稿第三页，共四十四页 反复的奔走试行和失败，使人们对成功的反复的奔走试行和失败，使人们对成功的可能发可能发 生疑惑，猜想问题无解，但又谁也说不清生疑惑，猜想问题无解，但又谁也说不清其中道理，于是有好事者去请教年轻的数学家欧拉其中道理，于是有好事者去请教年轻的数学家欧拉(Euler)(Euler)，刚开始欧拉也看不出这是一个数学问题，刚开始欧拉也看不出这是一个数学问题,1736,1736年，年，2929岁的欧拉把这一问题化成数学问题，岁的欧拉把这一问题化成数学问题，严格地论证了上述严格地论证了上述“七桥问题七桥问题”无解，并由此开创无解，并由此开创了图论与拓扑学的思维方式和诸多概念与理论，了图论与拓扑学的思维方式和诸多概念与理论，17361736年遂被公认为图论学科的历史元年，欧拉被尊年遂被公认为图论学科的历史元年，欧拉被尊为图论与拓扑学之父为图论与拓扑学之父.本讲稿第四页，共四十四页在图在图8.1.1画出了哥尼斯堡城图，城的四块画出了哥尼斯堡城图，城的四块陆地部分以陆地部分以A，B，C，和，和D标记。欧拉巧妙地把标记。欧拉巧妙地把哥尼斯堡城图化为图哥尼斯堡城图化为图8.1.2所示图所示图G，他把陆地设，他把陆地设为图为图G中的结点，把桥画成相应地联结陆地即结中的结点，把桥画成相应地联结陆地即结点的边。于是，通过哥尼斯堡城中每座桥恰好点的边。于是，通过哥尼斯堡城中每座桥恰好一次问题，等价于在图一次问题，等价于在图G中从某一结点出发找出中从某一结点出发找出一条链，它通过每条边恰好一次后回到原出发一条链，它通过每条边恰好一次后回到原出发结点，亦即等价于在图结点，亦即等价于在图G中寻找一个圈，它通过中寻找一个圈，它通过G中每一条边恰好一次。中每一条边恰好一次。本讲稿第五页，共四十四页图图8.1.2本讲稿第六页，共四十四页欧拉图欧拉图2 2欧拉图（欧拉图（欧拉回路与欧拉图）欧拉回路与欧拉图）经过图中每条边一次且仅一次并且行遍图经过图中每条边一次且仅一次并且行遍图中所有顶点的通路，称为中所有顶点的通路，称为欧拉通路欧拉通路若欧拉通路为回路，则称它为若欧拉通路为回路，则称它为欧拉回路欧拉回路具有欧拉回路的图称为具有欧拉回路的图称为欧拉图欧拉图具有欧拉通路的图称为具有欧拉通路的图称为半欧拉图半欧拉图 本讲稿第七页，共四十四页欧拉通路判定定理欧拉通路判定定理欧拉通路判定定理欧拉通路判定定理定理定理定理定理8.4 8.4 8.4 8.4 无向图无向图无向图无向图G G G G具有欧拉具有欧拉具有欧拉具有欧拉通路通路通路通路当且仅当当且仅当当且仅当当且仅当G G G G连通连通连通连通且且且且没有没有没有没有或有或有或有或有两个奇度两个奇度两个奇度两个奇度顶点顶点顶点顶点若若若若无奇度无奇度无奇度无奇度顶点，则欧拉通路为顶点，则欧拉通路为顶点，则欧拉通路为顶点，则欧拉通路为回路回路回路回路;若有两个若有两个若有两个若有两个奇度奇度奇度奇度顶点，则它们是每条欧拉通路的两个顶点，则它们是每条欧拉通路的两个顶点，则它们是每条欧拉通路的两个顶点，则它们是每条欧拉通路的两个端点端点端点端点欧拉图判定定理欧拉图判定定理欧拉图判定定理欧拉图判定定理定理定理定理定理8.5 8.5 8.5 8.5 无向图无向图无向图无向图G G G G为为为为欧拉图欧拉图欧拉图欧拉图当且仅当当且仅当当且仅当当且仅当G G G G连通连通连通连通且且且且无奇度顶点无奇度顶点无奇度顶点无奇度顶点本讲稿第八页，共四十四页欧拉通路欧拉通路本讲稿第九页，共四十四页欧拉回路欧拉回路本讲稿第十页，共四十四页1 111111010(a)(a)12129 92 28 83 34 47 75 56 6因上图是因上图是欧拉图欧拉图，故能沿着一条（不唯一故能沿着一条（不唯一的）的）欧拉回路欧拉回路一笔画，且能回到出发点一笔画，且能回到出发点1 1，2 2，3 3，4 4，7 7，8 8，10 10，11 11，12 12，2 2，5 5，4 4，6 6，5 5，12 12，9 9，6 6，8 8，9 9，11 11，1.1.本讲稿第十一页，共四十四页本讲稿第十二页，共四十四页应用应用1：一笔画问题：一笔画问题许多智力题要求用笔连续移动，不离开纸面，许多智力题要求用笔连续移动，不离开纸面，每边只能画一次，不允许重复，将图形画出，称每边只能画一次，不允许重复，将图形画出，称该图能一笔画。该图能一笔画。利用欧拉回路和通路来解决这样的智力题。利用欧拉回路和通路来解决这样的智力题。例如能否将穆罕默德短弯刀一笔画？例如能否将穆罕默德短弯刀一笔画？本讲稿第十三页，共四十四页欧拉回路：欧拉回路：a,b,d,g.h,j,i,h,k,g,f,d,c,b.e.i.f,e,a.本讲稿第十四页，共四十四页蚂蚁比赛问题蚂蚁比赛问题l 甲、乙两只蚂蚁分别位于右下图中的结点甲、乙两只蚂蚁分别位于右下图中的结点a a，b b处，并设图中的边长度是相等的。处，并设图中的边长度是相等的。l 甲、乙进行比赛：从它们所在的结点出发，走过甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点图中的所有边最后到达结点c c处。处。l 如果它们的速度相同，如果它们的速度相同，l 问谁先到达目的地？问谁先到达目的地？l 在图中，仅有两个度数在图中，仅有两个度数 为奇数的结点为奇数的结点b b，c c，l 因而存在从因而存在从b b到到c c的欧拉通路。的欧拉通路。c cb(b(乙乙)a(a(甲甲)本讲稿第十五页，共四十四页蚂蚁比赛问题蚂蚁比赛问题l 在图中，存在从在图中，存在从b b到到c c的欧拉通路，的欧拉通路，l 且蚂蚁乙且蚂蚁乙从从b到到c c只要走一条边数为只要走一条边数为9 9的欧拉通路；的欧拉通路；l而蚂蚁甲要想走完所有的边到达而蚂蚁甲要想走完所有的边到达c c，l 至少要先走一条边从至少要先走一条边从a a到达到达b b，再走一条欧拉通路，再走一条欧拉通路l 因而，它至少要走因而，它至少要走1010条边，条边，l 才能到达才能到达c c，l 所以乙必胜。所以乙必胜。c cb(b(乙乙)a(a(甲甲)本讲稿第十六页，共四十四页应用应用2:中国邮路问题中国邮路问题问题：一个邮递员从邮局出发问题：一个邮递员从邮局出发,走遍所有街走遍所有街道道,把邮件送到每个收件人手中把邮件送到每个收件人手中,最后回到邮局最后回到邮局,要要怎样走怎样走,使全程路线最短。使全程路线最短。转化为图论问题：以街道为边转化为图论问题：以街道为边,以街道交叉以街道交叉点为结点点为结点,以街道的长度为边上的权以街道的长度为边上的权,在带权图在带权图G=上上,找出一个经过所有边至少一次的找出一个经过所有边至少一次的回路回路,并使得该回路的权和达到最小。并使得该回路的权和达到最小。本讲稿第十七页，共四十四页说明：说明：1 1、该回路未必是、该回路未必是EulerEuler回路回路,边允许边允许重复。重复。2 2、中国管梅谷教授、中国管梅谷教授19621962年提出了这个问题年提出了这个问题,著名数学家著名数学家J.埃德蒙和他的合作者给出了一个埃德蒙和他的合作者给出了一个解答。解答。指出如果图指出如果图G G有有m m条边条边,则所求回路至少是则所求回路至少是m m条边条边,最多不超过最多不超过2m2m条边条边,并且每边在回路中至并且每边在回路中至多出现两次。多出现两次。本讲稿第十八页，共四十四页有向欧拉图有向欧拉图定理定理8.6 8.6 有向图有向图D D为为半欧拉图半欧拉图当且仅当当且仅当D D连连通，且通，且除两个顶点除两个顶点外，其余顶点的外，其余顶点的入度等于出入度等于出度度，这两个例外的顶点中，一个的入度比出度，这两个例外的顶点中，一个的入度比出度大大1 1，另一个的入度比出度小，另一个的入度比出度小1 1定理定理8.7 8.7 有向图有向图D D为为欧拉图欧拉图当且仅当当且仅当D D连连通且每个顶点的通且每个顶点的入度等于出度入度等于出度本讲稿第十九页，共四十四页判断有向图是否有欧拉路判断有向图是否有欧拉路V V1 1V V2 2V V3 3V V4 4(a)(a)图图a)a)中（结点中（结点v v1 1的入度比出度大的入度比出度大1 1，结点，结点v v3 3的出度比入度大的出度比入度大1 1，且除了这两个结点外，其余，且除了这两个结点外，其余结点的入度等于出度）结点的入度等于出度）因此，存在一条的欧拉通路因此，存在一条的欧拉通路 v v3 3v v1 1v v2 2v v3 3v v4 4v v1 1；本讲稿第二十页，共四十四页V V8 8V V2 2V V4 4V V6 6(c)(c)V V1 1V V3 3V V5 5V V7 7图图(c)(c)中所有结点的入度等于出度，中所有结点的入度等于出度，有欧拉回路有欧拉回路 v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8 8v v2 2v v4 4v v6 6v v8 8v v1 1因而因而(c)(c)是欧拉图。是欧拉图。本讲稿第二十一页，共四十四页本讲稿第二十二页，共四十四页欧拉图应用：计算机鼓轮设计欧拉图应用：计算机鼓轮设计 旋转鼓的表面分成旋转鼓的表面分成8 8块扇形，如图所示。块扇形，如图所示。图中阴影区表示用导电材料制成，空白区用绝图中阴影区表示用导电材料制成，空白区用绝缘材料制成，分别用二进制信号缘材料制成，分别用二进制信号1 1或或0 0表示。终表示。终端端a a、b b和和c c是接地或不是接地是接地或不是接地.因此，鼓的位置因此，鼓的位置可用二进制信号表示。试问应如何选取这可用二进制信号表示。试问应如何选取这8 8个扇个扇形的材料使每转过一个扇形都得到一个不同的形的材料使每转过一个扇形都得到一个不同的二进制信号，即每转一周，能得到二进制信号，即每转一周，能得到000000至至111111的的8 8个数。个数。本讲稿第二十三页，共四十四页本讲稿第二十四页，共四十四页本讲稿第二十五页，共四十四页解：解：每转一个扇形，信号每转一个扇形，信号a a1 1a a2 2a a3 3变成变成a a2 2a a3 3a a4 4 ，前者右两位决定了后者的左两位。因此，我，前者右两位决定了后者的左两位。因此，我们可把所有两位二进制数作结点，从每一个顶们可把所有两位二进制数作结点，从每一个顶点点a a1 1a a2 2到到a a2 2a a3 3引一条有向边引一条有向边a a1 1a a2 2a a3 3表示这个表示这个3 3位二位二进制数，作出表示所有可能的码变换的有向图进制数，作出表示所有可能的码变换的有向图（见下图）。（见下图）。本讲稿第二十六页，共四十四页本讲稿第二十七页，共四十四页本讲稿第二十八页，共四十四页于是问题转化为在这个有向图上求一条欧于是问题转化为在这个有向图上求一条欧拉回路。这个有向图的拉回路。这个有向图的4 4个顶点的次数都是出度、个顶点的次数都是出度、入度各为入度各为2 2，根据定理，根据定理8.68.6，欧拉回路存在，比，欧拉回路存在，比如如 是一条欧拉回路，对应于是一条欧拉回路，对应于这个回路的布鲁英序列：这个回路的布鲁英序列：0001110100011101，因此材料，因此材料应按此序列分布。应按此序列分布。本讲稿第二十九页，共四十四页上面的例子可以将鼓轮推广到具有上面的例子可以将鼓轮推广到具有n个触点个触点的情形的情形.本讲稿第三十页，共四十四页小结：小结：欧拉图欧拉图半欧拉图和欧拉图共性：半欧拉图和欧拉图共性：半欧拉图和欧拉图共性：半欧拉图和欧拉图共性：1 1、过每边一次且仅一次；、过每边一次且仅一次；、过每边一次且仅一次；、过每边一次且仅一次；2 2、连通。、连通。、连通。、连通。半欧拉图和欧拉图半欧拉图和欧拉图半欧拉图和欧拉图半欧拉图和欧拉图个性：个性：个性：个性：半欧拉图：半欧拉图：半欧拉图：半欧拉图：1 1 1 1、无向图，仅有零个或两个奇度数结点；、无向图，仅有零个或两个奇度数结点；、无向图，仅有零个或两个奇度数结点；、无向图，仅有零个或两个奇度数结点；2 2 2 2、有向图，、有向图，、有向图，、有向图，其中有两个结点，一个入度比出度大其中有两个结点，一个入度比出度大其中有两个结点，一个入度比出度大其中有两个结点，一个入度比出度大 1 1，另一个出度比入度大另一个出度比入度大另一个出度比入度大另一个出度比入度大1 1。欧拉图：欧拉图：欧拉图：欧拉图：1 1 1 1、无向图，所有结点的度数都为偶数；、无向图，所有结点的度数都为偶数；、无向图，所有结点的度数都为偶数；、无向图，所有结点的度数都为偶数；2 2 2 2、有向图，、有向图，、有向图，、有向图，所有结点的入度等于出度。所有结点的入度等于出度。所有结点的入度等于出度。所有结点的入度等于出度。本讲稿第三十一页，共四十四页多产的数学家欧拉多产的数学家欧拉 欧拉欧拉17071707年出生在瑞年出生在瑞士的巴塞尔（士的巴塞尔（BaselBasel）城，）城，1313岁就进巴塞尔大学读书，得岁就进巴塞尔大学读书，得到当时最有名的数学家约翰到当时最有名的数学家约翰伯努利（伯努利（Johann BernoulliJohann Bernoulli，1667-17481667-1748年）的精心指导年）的精心指导 （Leonhard Euler 公元公元1707-1783年）年）本讲稿第三十二页，共四十四页 欧拉渊博的知识，无穷无尽的创作精力和空欧拉渊博的知识，无穷无尽的创作精力和空前丰富的著作，都是令人惊叹不已的！他从前丰富的著作，都是令人惊叹不已的！他从1919岁岁开始发表论文，直到开始发表论文，直到7676岁，半个多世纪写下了浩岁，半个多世纪写下了浩如烟海的书籍和论文到今几乎每一个数学领域如烟海的书籍和论文到今几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等，数也学的欧拉方程，复变函数的欧拉公式等等，数也数不清他对数学分析的贡献更独具匠心，数不清他对数学分析的贡献更独具匠心，无无穷小分析引论穷小分析引论一书便是他划时代的代表作，当一书便是他划时代的代表作，当时数学家们称他为时数学家们称他为 分析学的化身分析学的化身 本讲稿第三十三页，共四十四页 欧拉是科学史上最多产的一位杰出的数学家，欧拉是科学史上最多产的一位杰出的数学家，据统计他那不倦的一生，共写下了据统计他那不倦的一生，共写下了886886本书籍和论本书籍和论文，其中分析、代数、数论占文，其中分析、代数、数论占40%40%，几何占，几何占18%18%，物，物理和力学占理和力学占28%28%，天文学占，天文学占11%11%，弹道学、航海学、，弹道学、航海学、建筑学等占建筑学等占3%3%，彼得堡科学院为了整理他的著作，彼得堡科学院为了整理他的著作，足足忙碌了四十七年足足忙碌了四十七年 本讲稿第三十四页，共四十四页 欧拉著作的惊人多产并不是偶然的，他可以欧拉著作的惊人多产并不是偶然的，他可以在任何环境中工作，他常常抱着孩子在膝上完成在任何环境中工作，他常常抱着孩子在膝上完成论文，也不顾孩子在旁边喧哗他那顽强的毅力论文，也不顾孩子在旁边喧哗他那顽强的毅力和孜孜不倦的治学精神，使他在双目失明以后，和孜孜不倦的治学精神，使他在双目失明以后，也没有停止对数学的研究，在失明后的也没有停止对数学的研究，在失明后的1717年间，年间，他还口述了几本书和他还口述了几本书和400400篇左右的论文篇左右的论文1919世纪伟世纪伟大数学家高斯（大数学家高斯（GaussGauss，1777-18551777-1855年）曾说：年）曾说：研研究欧拉的著作永远是了解数学的最好方法究欧拉的著作永远是了解数学的最好方法 本讲稿第三十五页，共四十四页 17251725年约翰年约翰伯努利的儿子丹尼尔伯努利的儿子丹尼尔伯努利赴伯努利赴俄国，并向沙皇喀德林一世推荐了欧拉，这样，俄国，并向沙皇喀德林一世推荐了欧拉，这样，在在17271727年年5 5月月1717日欧拉来到了彼得堡日欧拉来到了彼得堡17331733年，年年，年仅仅2626岁的欧拉担任了彼得堡科学院数学教授岁的欧拉担任了彼得堡科学院数学教授17351735年，欧拉解决了一个天文学的难题（计算慧年，欧拉解决了一个天文学的难题（计算慧星轨道），这个问题经几个著名数学家几个月的星轨道），这个问题经几个著名数学家几个月的努力才得到解决，而欧拉却用自己发明的方法，努力才得到解决，而欧拉却用自己发明的方法，三天便完成了然而过度的工作使他得了眼病，三天便完成了然而过度的工作使他得了眼病，并且不幸右眼失明了，这时他才并且不幸右眼失明了，这时他才2828岁岁本讲稿第三十六页，共四十四页17411741年欧拉应普鲁士彼德烈大帝的邀请，到年欧拉应普鲁士彼德烈大帝的邀请，到柏林担任科学院物理数学所所长，直到柏林担任科学院物理数学所所长，直到17661766年，年，后来在沙皇喀德林二世的诚恳敦聘下重回彼得堡，后来在沙皇喀德林二世的诚恳敦聘下重回彼得堡，不料没有多久，左眼视力衰退，最后完全失明不料没有多久，左眼视力衰退，最后完全失明不幸的事情接踵而来，不幸的事情接踵而来，17711771年彼得堡的大火灾殃年彼得堡的大火灾殃及欧拉住宅，带病而失明的及欧拉住宅，带病而失明的6464岁的欧拉被围困在岁的欧拉被围困在大火中，虽然他被别人从火海中救了出来，但他大火中，虽然他被别人从火海中救了出来，但他的书房和大量研究成果全部化为灰烬了的书房和大量研究成果全部化为灰烬了 本讲稿第三十七页，共四十四页 沉重的打击，仍然没有使欧拉倒下，他发誓沉重的打击，仍然没有使欧拉倒下，他发誓要把损失夺回来在他完全失明之前，还能朦胧要把损失夺回来在他完全失明之前，还能朦胧地看见东西，他抓紧这最后的时刻，在一块大黑地看见东西，他抓紧这最后的时刻，在一块大黑板上疾书他发现的公式，然后口述其内容，由他板上疾书他发现的公式，然后口述其内容，由他的学生特别是大儿子的学生特别是大儿子A A欧拉（数学家和物理学家）欧拉（数学家和物理学家）笔录欧拉完全失明以后，仍然以惊人的毅力与笔录欧拉完全失明以后，仍然以惊人的毅力与黑暗搏斗，凭着记忆和心算进行研究，直到逝世，黑暗搏斗，凭着记忆和心算进行研究，直到逝世，竟达竟达1717年之久年之久 本讲稿第三十八页，共四十四页 欧拉的风格是很高的，拉格朗日是稍后于欧欧拉的风格是很高的，拉格朗日是稍后于欧拉的大数学家，从拉的大数学家，从1919岁起和欧拉通信，讨论等周岁起和欧拉通信，讨论等周问题的一般解法，这引起变分法的诞生等周问问题的一般解法，这引起变分法的诞生等周问题是欧拉多年来苦心考虑的问题，拉格朗日的解题是欧拉多年来苦心考虑的问题，拉格朗日的解法，博得欧拉的热烈赞扬，法，博得欧拉的热烈赞扬，17591759年年1010月月2 2日欧拉在日欧拉在回信中盛称拉格朗日的成就，并谦虚地压下自己回信中盛称拉格朗日的成就，并谦虚地压下自己在这方面较不成熟的作品暂不发表，使年青的拉在这方面较不成熟的作品暂不发表，使年青的拉格朗日的工作得以发表和流传，并赢得巨大的声格朗日的工作得以发表和流传，并赢得巨大的声誉他晚年的时候，欧洲所有的数学家都把他当誉他晚年的时候，欧洲所有的数学家都把他当作老师，著名数学家拉普拉斯（作老师，著名数学家拉普拉斯（LaplaceLaplace）曾说过：）曾说过：欧拉是我们的导师欧拉是我们的导师本讲稿第三十九页，共四十四页 作为这样一位科学巨人，在生活中他并不是作为这样一位科学巨人，在生活中他并不是一个呆板的人。他性情温和，性格开朗，也喜欢一个呆板的人。他性情温和，性格开朗，也喜欢交际。欧拉结过两次婚，有交际。欧拉结过两次婚，有1313个孩子。他热爱家个孩子。他热爱家庭的生活，常常和孩子们一起做科学游戏，讲故庭的生活，常常和孩子们一起做科学游戏，讲故事。事。欧拉充沛的精力保持到最后一刻，欧拉充沛的精力保持到最后一刻，17831783年年9 9月月1818日下午，欧拉为了庆祝他计算气球上升定律日下午，欧拉为了庆祝他计算气球上升定律的成功，请朋友们吃饭，那时天王星刚发现不久，的成功，请朋友们吃饭，那时天王星刚发现不久，欧拉写出了计算天王星轨道的要领，还和他的孙欧拉写出了计算天王星轨道的要领，还和他的孙子逗笑，喝完茶后，突然疾病发作，烟斗从手中子逗笑，喝完茶后，突然疾病发作，烟斗从手中落下，口里喃喃地说：落下，口里喃喃地说：我死了我死了，欧拉终于，欧拉终于 停止停止了生命和计算了生命和计算 本讲稿第四十页，共四十四页在普及教育和科研中，欧拉意识到符号的简在普及教育和科研中，欧拉意识到符号的简在普及教育和科研中，欧拉意识到符号的简在普及教育和科研中，欧拉意识到符号的简化和规则化既有有助于学生的学习，又有助于数学化和规则化既有有助于学生的学习，又有助于数学化和规则化既有有助于学生的学习，又有助于数学化和规则化既有有助于学生的学习，又有助于数学的发展，所以欧拉创立了许多新的符号。如的发展，所以欧拉创立了许多新的符号。如的发展，所以欧拉创立了许多新的符号。如的发展，所以欧拉创立了许多新的符号。如17341734年年年年用用用用f f(x x)表示函数，表示函数，17361736年用年用 e 表示自然对数的表示自然对数的表示自然对数的表示自然对数的底，底，底，底，1748174817481748年用年用sinsin 、cos cos，（，（，（，（1753175317531753年）年）年）年）tg等表示三等表示三角函数，角函数，17551755年用年用年用年用 表示求和，表示求和，表示求和，表示求和，17771777年用年用 i i表示表示表示表示虚数等。虚数等。虚数等。虚数等。1736173617361736年，圆周率年，圆周率 虽然不是欧拉首创，虽然不是欧拉首创，但却是经过欧拉的倡导才得以广泛流行。但却是经过欧拉的倡导才得以广泛流行。本讲稿第四十一页，共四十四页欧拉在数学上的建树很多，对著名的哥尼斯堡欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。欧拉将三角函七桥问题的解答开创了图论的研究。欧拉将三角函数与指数函联结起来得到的著名的公式：数与指数函联结起来得到的著名的公式：，尤其是把，尤其是把e、i i 统一在一个令人叫绝的关系式统一在一个令人叫绝的关系式统一在一个令人叫绝的关系式统一在一个令人叫绝的关系式 中。中。中。中。欧拉还发现欧拉还发现欧拉还发现欧拉还发现，不论什么形状的凸多面体，其顶点数，不论什么形状的凸多面体，其顶点数，不论什么形状的凸多面体，其顶点数，不论什么形状的凸多面体，其顶点数v v、棱数棱数e e、面数、面数、面数、面数f f f f之间总有之间总有之间总有之间总有v-e+f=2这个关系。这个关系。v-e+f被称为被称为欧拉示性数，成为拓扑学的基础概念。在数论中，欧拉示性数，成为拓扑学的基础概念。在数论中，欧拉首先引进了重要的欧拉函数欧拉首先引进了重要的欧拉函数(n)，用多种方法证，用多种方法证，用多种方法证，用多种方法证明了费马小定理。以欧拉的名字命名的数学公式、定理明了费马小定理。以欧拉的名字命名的数学公式、定理明了费马小定理。以欧拉的名字命名的数学公式、定理明了费马小定理。以欧拉的名字命名的数学公式、定理等在数学书籍中随处可见等在数学书籍中随处可见等在数学书籍中随处可见等在数学书籍中随处可见,与此同时，他还在物理、天与此同时，他还在物理、天与此同时，他还在物理、天与此同时，他还在物理、天文、建筑以至音乐、哲学方面取得了辉煌的成就。文、建筑以至音乐、哲学方面取得了辉煌的成就。文、建筑以至音乐、哲学方面取得了辉煌的成就。文、建筑以至音乐、哲学方面取得了辉煌的成就。本讲稿第四十二页，共四十四页思考题思考题：1 1、判断右图、判断右图在所示的欧拉图中，在所示的欧拉图中，在所示的欧拉图中，在所示的欧拉图中，求从求从求从求从v v v v1 1 1 1出发的欧拉回路出发的欧拉回路出发的欧拉回路出发的欧拉回路P P P P（请同学思考回答）（请同学思考回答）（请同学思考回答）（请同学思考回答）先走先走 P Pv v1 1e e1 1v v2 2e e2 2v v3 3e e3 3v v4 4e e7 7v v7 7，再往下走，就可以走出欧拉回路再往下走，就可以走出欧拉回路P Pv v1 1e e1 1v v2 2e e2 2v v3 3e e3 3v v4 4e e7 7v v7 7e e6 6v v6 6e e5 5v v5 5e e4 4v v4 4e e8 8v v2 2e e9 9v v7 7e e1010v v1 1.本讲稿第四十三页，共四十四页 2 2、判断下列各图、判断下列各图（请同学思考回答）（请同学思考回答）（请同学思考回答）（请同学思考回答）图图图图a a a a和图和图和图和图d d d d是欧拉图；是欧拉图；是欧拉图；是欧拉图；图图图图b b b b和图和图和图和图e e e e不是欧拉图，但存在欧拉通路；不是欧拉图，但存在欧拉通路；不是欧拉图，但存在欧拉通路；不是欧拉图，但存在欧拉通路；图图图图c c c c和图和图和图和图f f f f不存在欧拉通路。不存在欧拉通路。不存在欧拉通路。不存在欧拉通路。本讲稿第四十四页，共四十四页