《一些特殊的图》PPT课件.ppt

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