离散数学 欧拉图.ppt

欧拉图
欧拉通路
欧拉回路
欧拉图
半欧拉图
既么构酌炸辽少佳拂笼晨刊橱仓躬脯问绢假毫深品锹河拙氨窜漫笨稻飞讹离散数学欧拉图离散数学欧拉图
1
一、哥尼斯堡七桥问题
十八世纪德国哥尼斯堡城位于普雷格尔河畔,河中有两个岛,
河两岸和河中的两个岛架起了七座桥与两岛相连.
游人从任何一个地点出发走过七座桥且每座桥只走一次,
问是否最后又能回到原地,这就是著名的七桥问题.
铱食刮坟施胶委其恃酋长艾帜晓蛮荡叔抗帅嘉等蘑怀贵稳梳迅晚荚葛顺典离散数学欧拉图离散数学欧拉图
2
1736年瑞士著名数学家欧拉用图论的方法解决了这个问题
欧拉用点表示岛和两岸,用边表示桥。
于是问题就归结为这个图是否能一笔画的问题
该问题转化为:从图中任意一点出发一笔画出这个图形,
并且最后回到出发点。
收玉钨吠咏源利蔗漫锄海油唯舒膏詹梢涎管见镣入绷汇俯咬摇溯嗜赤账淮离散数学欧拉图离散数学欧拉图
3
当图中的点是偶数度时,该图的特点是能进能
出或能出能进。
欧拉在解决七桥问题时引进了“度”的
概念,并对此作了详细分析。
惧启渡骂爽撵联辽消墨羊架询异栖炳放辆纹烹桑跨皿钢宗狱瞻肯砾薄寝骇离散数学欧拉图离散数学欧拉图
4
当图中的点是奇数度时,该图的特点是能出
不能进或能进不能出。
逞趣尸逝厘渺弥迭占絮挺玻谤燥居更尉庶翰泽淄拼俗梆惜布衙激伦变割斌离散数学欧拉图离散数学欧拉图
5
当连通图的各个顶点都是偶数度时,该图可
以一笔画,且始点和终点重合。
当一个图中仅有两个奇数度点时,该图也可以一笔画,但必须
把其中一个奇数度点作为起点,另一个奇数度点作为终点。
由此,欧拉得到如下结论:
难脖员惕盔苑鸟旧乍被馒蹬棕尼恫拾锣税蓬折窘增篓刨纲袭湘镭窟坊盛瘸离散数学欧拉图离散数学欧拉图
6
二、欧拉定理
定义1 如果图中存在一条通过各边一次且仅
一次的回路,称此回路为欧拉回路或
称为欧拉圈。
定义2 如果图中存在一条通过各边一次且仅
一次的通路,称此通路为欧拉通路或
称为欧拉链。
具有欧拉回路的图称为欧拉图,
具有欧拉通路的图称为半欧拉图.
几点说明:
上述定义对无向图和有向图都适用.
规定平凡图为欧拉图.
欧拉通路是简单通路, 欧拉回路是简单回路.
环不影响图的欧拉性.
虹晤恫荧登园暗睁出抡姥惧邯像赊致算摄笺沥诉芭懈瓢秃风钮乡郡痞坤猛离散数学欧拉图离散数学欧拉图
7
定理:一个无向连通图是欧拉图的充分必要条件
是:图中各点度数都为偶数。
一个无向连通图是半欧拉图的充分必要条
件是:图中至多有两个奇数度点。
琳戮堑扰蒙益谬浴袍绰麓修贼胶得蛇酚展戏且熟韩乏浩嫡拈袁胺晚棱永公离散数学欧拉图离散数学欧拉图
8
由此,在七桥问题中,其4个顶点都是奇数度点,
所以,七桥图不是欧拉图,也不是半欧拉图。
因此,这个图不可能一笔画成。
铣汽鞭附必宿这埋渗底疡挺赔狞洋衫漂件眉就降涂谅讥菊产愤壶滦亮捣卤离散数学欧拉图离散数学欧拉图
9
PLAY
碱挎辙恩徐实鬃狰卉榔巍壮矩廊扶蚕界吝嗽咖浑桩链漠韩枣美谆巡苛规汪离散数学欧拉图离散数学欧拉图
10