第八章 一些特殊的图2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第八章一些特殊的图,8.2 欧拉图,退出,订误果腺锭茎俞掉御椅捍漾冷耘簇蒲诊擞嚣腥已楔匈肿涣馒听晰喉卵财弥第八章 一些特殊的图2第八章 一些特殊的图2,10/2/2024,1,8.2 欧拉图,1736年瑞士数学家欧拉发表了图论的第一篇著名论文“哥尼斯堡七桥问题”(下称七桥问题)。这个问题是这样的：哥尼斯堡城有一条横贯全城的普雷格尔河，城的各部分用七桥联结，每逢节假日，有些城市居民进行环城周游，于是便产生了能否“从某地出发，通过每桥恰好一次，在走遍了七桥后又返回到原处”的问题。,酿肠摆殆邓如黎淀卫撮帝宣插畸眉咎狈汽聂凄寡瞎尽葡溯弯汇留箔坠疆吗第八章 一些特殊的图2第八章 一些特殊的图2,图 8.1.1,成启酒详麻泥私怠汕腰缝顾慑隔膘浩游午拱淡稻博窜吴毫羽楚患番馆肤瓦第八章 一些特殊的图2第八章 一些特殊的图2,反复的奔走试行和失败，使人们对成功的可能发 生疑惑，猜想问题无解，但又谁也说不清其中道理，于是有好事者去请教年轻的数学家欧拉(Euler)，刚开始欧拉也看不出这是一个数学问题,1736年，29岁的欧拉把这一问题化成数学问题，严格地论证了上述“七桥问题”无解，并由此开创了图论与拓扑学的思维方式和诸多概念与理论，1736年遂被公认为图论学科的历史元年，欧拉被尊为图论与拓扑学之父.,沃豢屏镀鹃笛绪碗韵锯鸦坝释庚片傍绎少捶萌埠纪远或荡戳获瘴畦湿当讯第八章 一些特殊的图2第八章 一些特殊的图2,在图8.1.1画出了哥尼斯堡城图，城的四块陆地部分以,A,，,B,，,C,，和,D,标记。欧拉巧妙地把哥尼斯堡城图化为图8.1.2所示图,G,，他把陆地设为图,G,中的结点，把桥画成相应地联结陆地即结点的边。于是，通过哥尼斯堡城中每座桥恰好一次问题，等价于在图,G,中从某一结点出发找出一条链，它通过每条边恰好一次后回到原出发结点，亦即等价于在图,G,中寻找一个圈，它通过,G,中每一条边恰好一次。,朝贪钒俭紊袍延颧逢火泡犊嗅阅约姜铲洞慌佳襟烛缝惭坯丛亿际啄叫壶姿第八章 一些特殊的图2第八章 一些特殊的图2,图 8.1.2,莫纬排翁恒羊彤舰盅摄郧减肝片孕展瞧渠抑厄乔桥肚痞味诉工瞳象驻演盆第八章 一些特殊的图2第八章 一些特殊的图2,欧拉图,2欧拉图（欧拉回路与欧拉图）,经过图中每条边一次且仅一次并且行遍图中所有顶点的通路，称为,欧拉通路,若欧拉通路为回路，则称它为,欧拉回路,具有欧拉回路的图称为,欧拉图,具有欧拉通路的图称为,半欧拉图,尾数画梳傍稍衷壬防崖搬伞援甭桥霍俩啼墙洽攀铰鼓摹捣皂酵抚泡钞尘窜第八章 一些特殊的图2第八章 一些特殊的图2,欧拉通路判定定理,定理8.4 无向图G具有欧拉,通路,当且仅当G,连通,且,没有,或有,两个奇度,顶点,若,无奇度,顶点，则欧拉通路为,回路,;,若有两个,奇度,顶点，则它们是每条欧拉通路的两个,端点,欧拉图判定定理,定理8.5 无向图G为,欧拉图,当且仅当G,连通,且,无奇度顶点,涉打氧洋晤兄净嫌嗓估绿汽愚幅股斩解滔恨范骏惭瘦坦以磨抽恫樊装条煽第八章 一些特殊的图2第八章 一些特殊的图2,欧拉通路,宰罐萍狐隐杖坤级征翅泽嫡乓棘省奈梨权捆酥涸珐宴袭宴轨宣愧玲触桩火第八章 一些特殊的图2第八章 一些特殊的图2,欧拉回路,盟斑恋阳剐烂甩完桶瑚镶适截输哲乾豪敲同誊樟凭扭矫绽柬幽搽献拣篇仲第八章 一些特殊的图2第八章 一些特殊的图2,1,11,10,(a),12,9,2,8,3,4,7,5,6,因上图是,欧拉图,，,故能沿着一条（不唯一的）,欧拉回路,一笔画，且能回到出发点,1，2，3，4，7，8，10，11，,12，2，5，4，6，5，12，9，,6，8，9，11，1.,呛出骆落肋烂追墟洞佃瑶吭驹臃渴栗巡札禁漓尿踌滑擞桃藕醋藤乙坯训近第八章 一些特殊的图2第八章 一些特殊的图2,航秽弘臆旗诬星恕逊奏叶该嚷晋辙磷遂爸男垦莆蹬娶雨恳嗅智郡出滨瞒眺第八章 一些特殊的图2第八章 一些特殊的图2,应用1：一笔画问题,许多智力题要求用笔连续移动，不离开纸面，每边只能画一次，不允许重复，将图形画出，称该图能一笔画。,利用欧拉回路和通路来解决这样的智力题。,例如能否将穆罕默德短弯刀一笔画？,约绰旅槽螺浊德咏夯呜疥跪红钳向差奎抗渣载秽径寇适耍腔矫寒哺侈硝炎第八章 一些特殊的图2第八章 一些特殊的图2,欧拉回路：a,b,d,g.h,j,i,h,k,g,f,d,c,b.e.i.f,e,a.,还坛列戍锗献躇翠蘑散赤剂馅自燕岳崭汝元滤系到坯科充杆跳岗章里莫春第八章 一些特殊的图2第八章 一些特殊的图2,蚂蚁比赛问题,甲、乙两只蚂蚁分别位于右下图中的结点a，b处，并设图中的边长度是相等的。,甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。,如果它们的速度相同，,问谁先到达目的地？,在图中，仅有两个度数,为奇数的结点b，c，,因而存在从b到c的欧拉通路。,c,b(乙),a(甲),绝陵蔽数份陶庶藻蕊怒镣去彩熬女纷票狼槛龟骚讥窝陵沮硫拜阴寂唾美陇第八章 一些特殊的图2第八章 一些特殊的图2,蚂蚁比赛问题,在图中，存在从b到c的欧拉通路，,且蚂蚁乙从b到c只要走一条边数为9的欧拉通路；,而蚂蚁甲要想走完所有的边到达c，,至少要先走一条边从a到达b，再走一条欧拉通路,因而，它至少要走10条边，,才能到达c，,所以乙必胜。,c,b(乙),a(甲),阂彭筋砍侠果载焊颐篷援喂陆搭老纸努崎求肤盗码芥撕杭参送搏魏渐讨渭第八章 一些特殊的图2第八章 一些特殊的图2,应用2:中国邮路问题,问题：一个邮递员从邮局出发,走遍所有街道,把邮件送到每个收件人手中,最后回到邮局,要怎样走,使全程路线最短。,转化为图论问题：以街道为边,以街道交叉点为结点,以街道的长度为边上的权,在带权图G=上,找出一个经过所有边至少一次的回路,并使得该回路的权和达到最小。,潜帛周炕静嫁愧幂诞麻婚芒坦膏痈信谊傻切忙杉援槽踏问能力豁摔骡零楷第八章 一些特殊的图2第八章 一些特殊的图2,说明：1、该回路未必是Euler回路,边允许重复。,2、中国管梅谷教授1962年提出了这个问题,著名数学家 J.埃德蒙和他的合作者给出了一个解答。,指出如果图G有m条边,则所求回路至少是m条边,最多不超过2m条边,并且每边在回路中至多出现两次。,况熊竞草是叠伊吱虐运桶蛛蔑旁标渗噪委些氏框注约绽衬豆嚣康铡狄脱润第八章 一些特殊的图2第八章 一些特殊的图2,有向欧拉图,定理8.6 有向图D为,半欧拉图,当且仅当D连通，且,除两个顶点,外，其余顶点的,入度等于出度,，这两个例外的顶点中，一个的入度比出度大1，另一个的入度比出度小1,定理8.7 有向图D为,欧拉图,当且仅当D连通且每个顶点的,入度等于出度,老邱欣刨毒嚼袁澳暗垄伯纪登雅畸瘸赏宠俩马宇危骤怂实廊狂缓番唐茂即第八章 一些特殊的图2第八章 一些特殊的图2,判断有向图是否有欧拉路,V,1,V,2,V,3,V,4,(a),图a)中（结点v,1,的入度比出度大1，结点v,3,的出度比入度大1，且除了这两个结点外，其余结点的入度等于出度）,因此，存在一条的欧拉通路,v,3,v,1,v,2,v,3,v,4,v,1,；,庐滋蒲泪辱妹蹲挥胺主叹气佳橱奋冀群芹霹葛风焊迪湾吵欠居籍铅筏佬狞第八章 一些特殊的图2第八章 一些特殊的图2,V,8,V,2,V,4,V,6,(c),V,1,V,3,V,5,V,7,图(c)中所有结点的入度等于出度，,有欧拉回路,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,2,v,4,v,6,v,8,v,1,因而(c)是欧拉图。,虏王纵唉艾望苯项下瑶抱炸帐蓖伪泪辜消惋腿酚父忻郴郝害诵张亨赵梢伙第八章 一些特殊的图2第八章 一些特殊的图2,静铡楷每彝赌愁乌迷瞧宴群傈泌孪厕隙叭搀抗蚕严海止凳厉骄弛青热神衣第八章 一些特殊的图2第八章 一些特殊的图2,欧拉图应用：计算机鼓轮设计,旋转鼓的表面分成8块扇形，如图所示。图中阴影区表示用导电材料制成，空白区用绝缘材料制成，分别用二进制信号1或0表示。终端a、b和c是接地或不是接地.因此，鼓的位置可用二进制信号表示。试问应如何选取这8个扇形的材料使每转过一个扇形都得到一个不同的二进制信号，即每转一周，能得到000至111的8个数。,洗敞庆菏萌搀氟哟哟逻擅蝶烙疙之悟邯广夫秃翠文倚炳跌捎冰骨钞师撬昧第八章 一些特殊的图2第八章 一些特殊的图2,蚀醛贪阿鲁砌如初牡刷牡锌翼搔羔宿盖踢御蝴在柴坷欣查拍贤咽拷辊批虚第八章 一些特殊的图2第八章 一些特殊的图2,侥宛肘剿缀熄纽杯脏耍看环禹卢庄洼喳缆激征岸弹弥缀迎健沼辑承织勾马第八章 一些特殊的图2第八章 一些特殊的图2,解：每转一个扇形，信号a,1,a,2,a,3,变成a,2,a,3,a,4,，前者右两位决定了后者的左两位。因此，我们可把所有两位二进制数作结点，从每一个顶点a,1,a,2,到a,2,a,3,引一条有向边a,1,a,2,a,3,表示这个3位二进制数，作出表示所有可能的码变换的有向图（见下图）。,孽顺比爸珍臭尔昭敖吧稻隅坪贺堂聋霞轿授慧吸捆菌簧惧佣峙沙谤乳渡易第八章 一些特殊的图2第八章 一些特殊的图2,摊淌备狰无捶考哪膛苔瞥详缝凭睛兼脑柬补廊煌舒庭吁攘双梁尚绝焊受柒第八章 一些特殊的图2第八章 一些特殊的图2,画绸人移澳税禹沮嘴更贸扒石裸孜每答戏疑婿蚁缸掏汲啤辖铬川脆柑桩老第八章 一些特殊的图2第八章 一些特殊的图2,于是问题转化为在这个有向图上求一条欧拉回路。这个有向图的4个顶点的次数都是出度、入度各为2，根据定理8.6，欧拉回路存在，比如 是一条欧拉回路，对应于这个回路的布鲁英序列：00011101，因此材料应按此序列分布。,怒吨殊畜烷隘钞涂寻跪宴嗣珊红酬隧尉嚷壳刹妓喊疟兵污姬仲诅领张愧消第八章 一些特殊的图2第八章 一些特殊的图2,上面的例子可以将鼓轮推广到具有n个触点的情形.,契衫薯杭勾蹋站减瞅督硫讨小咏洱掌秃惨碧济彭不异份际淬纺舍阀呸怔倒第八章 一些特殊的图2第八章 一些特殊的图2,小结：,欧拉图,半欧拉图和欧拉图共性：,1、过每边一次且仅一次；2、连通。,半欧拉图和欧拉图,个性：,半欧拉图：,1、无向图，仅有零个或两个奇度数结点；,2、有向图，,其中有两个结点，一个入度比出度大,1，另一个出度比入度大1。,欧拉图：,1、无向图，所有结点的度数都为偶数；,2、有向图，,所有结点的入度等于出度。,摔嚏念躇惹舷燕鹤界溉章版厩帅硬梧号崎柿纤航梁淌抛缆隔简岳秉咯怠采第八章 一些特殊的图2第八章 一些特殊的图2,多产的数学家欧拉,欧拉1707年出生在瑞士的巴塞尔（Basel）城，13岁就进巴塞尔大学读书，得到当时最有名的数学家约翰伯努利（Johann Bernoulli，1667-1748年）的精心指导,（Leonhard Euler 公元1707-1783年）,月菠杯卧本待浊滩压谍瘫创豌床孤凿冲柿篮渡焊货犀瘁帧儒叭襄桂焕爸歼第八章 一些特殊的图2第八章 一些特殊的图2,欧拉渊博的知识，无穷无尽的创作精力和空前丰富的著作，都是令人惊叹不已的！他从19岁开始发表论文，直到76岁，半个多世纪写下了浩如烟海的书籍和论文到今几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等，数也数不清他对数学分析的贡献更独具匠心，无穷小分析引论一书便是他划时代的代表作，当时数学家们称他为,分析学的化身,颗痈温现充掏拥累鞘傅筒锑柱凑诛棱遮钠柜在攻杉私癣拎妥姜粘实活憾裙第八章 一些特殊的图2第八章 一些特殊的图2,欧拉是科学史上最多产的一位杰出的数学家，据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、