离散数学 欧拉图.ppt

欧拉图
欧拉通路
欧拉回路
欧拉图
半欧拉图
快郎莎恋嗣拯诬睛考靛酱铡召禁忘癌骋脱辽辈狮撕念团执钳恐时仪盲淹裸离散数学 欧拉图离散数学 欧拉图
1
一、哥尼斯堡七桥问题
十八世纪德国哥尼斯堡城位于普雷格尔河畔,河中有两个岛,
河两岸和河中的两个岛架起了七座桥与两岛相连.
游人从任何一个地点出发走过七座桥且每座桥只走一次,
问是否最后又能回到原地,这就是著名的七桥问题.
今曳羽塞胡哺泥毛寅霸框桃抑剩政静赛赞中毛擒尤那什悦敷馒酵盗揪焚昂离散数学 欧拉图离散数学 欧拉图
2
1736年瑞士著名数学家欧拉用图论的方法解决了这个问题
欧拉用点表示岛和两岸,用边表示桥。
于是问题就归结为这个图是否能一笔画的问题
该问题转化为：从图中任意一点出发一笔画出这个图形，
并且最后回到出发点。
斥趁驮厌抠灌恰躁彼柏枝液秘捌勺环街糖占税辊焙肋船位过临堡鸯影纳膘离散数学 欧拉图离散数学 欧拉图
3
当图中的点是偶数度时，该图的特点是能进能
出或能出能进。
欧拉在解决七桥问题时引进了“度”的
概念，并对此作了详细分析。
肌劲恍义务晶辟翼迈陕骄襄培黔酪伸叶智吉压姥肛果岸乍僳嗅漫杠蜜藻挤离散数学 欧拉图离散数学 欧拉图
4
当图中的点是奇数度时，该图的特点是能出
不能进或能进不能出。
冈胳伤拿裁枕炒米事妨癣鞍吸粪纱解庚锯偷俏瓶粕无印鄂终劈来纽鞭猴婉离散数学 欧拉图离散数学 欧拉图
5
当连通图的各个顶点都是偶数度时，该图可
以一笔画，且始点和终点重合。
当一个图中仅有两个奇数度点时，该图也可以一笔画，但必须
把其中一个奇数度点作为起点，另一个奇数度点作为终点。
由此，欧拉得到如下结论：
狈全殃咽毋涎轮阔吵腻归抖钳夺幅搞氢垦标赌惨巷遏忘渗僻饥裙撑裴犬猴离散数学 欧拉图离散数学 欧拉图
6
二、欧拉定理
定义1 如果图中存在一条通过各边一次且仅
一次的回路，称此回路为欧拉回路或
称为欧拉圈。
定义2 如果图中存在一条通过各边一次且仅
一次的通路，称此通路为欧拉通路或
称为欧拉链。
具有欧拉回路的图称为欧拉图，
具有欧拉通路的图称为半欧拉图.
几点说明：
上述定义对无向图和有向图都适用.
规定平凡图为欧拉图.
欧拉通路是简单通路, 欧拉回路是简单回路.
环不影响图的欧拉性.
猫砧遏步碑叔捉测啦备警空钞赁和西蝴京政翔液北爵昏硷菏储驴四胜寥闭离散数学 欧拉图离散数学 欧拉图
7
定理：一个无向连通图是欧拉图的充分必要条件
是：图中各点度数都为偶数。
一个无向连通图是半欧拉图的充分必要条
件是：图中至多有两个奇数度点。
挎垄贮腿亢咯档复裔饺妇蟹模孔借忌雇馅篮狭绸诧赡吠短疯耻晶斩涅前驰离散数学 欧拉图离散数学 欧拉图
8
由此，在七桥问题中，其4个顶点都是奇数度点，
所以，七桥图不是欧拉图，也不是半欧拉图。
因此，这个图不可能一笔画成。
整肄临献狱搅狐痊痒礼侵劫典瞬勿西紊余脑敝素椰肌喧扰催味迸裙匿载靴离散数学 欧拉图离散数学 欧拉图
9
PLAY
作疵缕遂堡君舶苔洲欢喜帽朵嘛腑娃券掐卢厉关耸惩昌革竭狐秒鸣告震囚离散数学 欧拉图离散数学 欧拉图
10