北京大学：《离散数学》系列课程之一《集合论与图论》第17讲 欧拉图

第17讲欧拉图 1.七桥问题,一笔画欧拉通(回)路,欧拉图 2.判定欧拉图的充分必要条件 3.求欧拉回路的算法 4.中国邮递员问题 《集合论与图论》第17讲

《集合论与图论》第17讲 1 第17讲 欧拉图 1. 七桥问题,一笔画,欧拉通(回)路,欧拉图 2. 判定欧拉图的充分必要条件 3. 求欧拉回路的算法 4. 中国邮递员问题

七桥问题 七桥问题( Seven bridges of Konigsberg problem): River Pregel, Kaliningrad Russia B 《集合论与图论》第17讲

《集合论与图论》第17讲 2 七桥问题 七桥问题(Seven bridges of Königsberg problem): River Pregel, Kaliningrad, Russia

Leonhard euler w Leonhard Euler(1707-1783) 人类有史以来最多产的数学家 1736年;七桥问题”,图论和拓扑学诞生 aseD EULER 《集合论与图论》第17讲

《集合论与图论》第17讲 3 Leonhard Euler Leonhard Euler(1707~1783): 人类有史以来最多产的数学家. 1736年,“七桥问题”,图论和拓扑学诞生 A D c d a b f C g B e

笔画 《集合论与图论》第17讲

《集合论与图论》第17讲 4 一笔画

欧拉图( Eulerian) 鲁欧拉通路 Euler trai经过图中所有边的 简单通路 欧拉回路( Euler tour/ circuit):经过图中所 有边的简单回路 壽欧拉图( Eulerian):有欧拉回路的图 半欧拉图( semi-Eulerian):有欧拉通路的 《集合论与图论》第17讲

《集合论与图论》第17讲 5 欧拉图(Eulerian) 欧拉通路(Euler trail): 经过图中所有边的 简单通路 欧拉回路(Euler tour/circuit): 经过图中所 有边的简单回路 欧拉图(Eulerian): 有欧拉回路的图 半欧拉图(semi-Eulerian): 有欧拉通路的 图

无向欧拉图的充分必要条件 婚定理1:设G是无向连通图,则 (1)G是欧拉图 台(2)G中所有顶点都是偶数度 台→(3)G是若干个边不交的圈的并 静证明:(1)→(2)→(3)→(1) (1)→>(2):若欧拉回路总共k次经过顶点w则 d(v=2k 《集合论与图论》第17讲

《集合论与图论》第17讲 6 无向欧拉图的充分必要条件 定理1: 设G是无向连通图,则 (1) G是欧拉图 ⇔ (2) G中所有顶点都是偶数度 ⇔ (3) G是若干个边不交的圈的并 证明: (1)⇒(2)⇒(3)⇒(1). (1)⇒(2): 若欧拉回路总共k次经过顶点v,则 d(v)=2k.

定理1(2)→3) (2)G中所有顶点都是偶数度 (3)G是若干个边不交的圈的并 证明:(2)→(3):若删除任意1个圈上的边, 则所有顶点的度还是偶数,但是不一定连 通了.对每个连通分支重复进行 《集合论与图论》第17讲

《集合论与图论》第17讲 7 定理1((2)⇒(3)) (2) G中所有顶点都是偶数度 (3) G是若干个边不交的圈的并 证明: (2)⇒(3): 若删除任意1个圈上的边, 则所有顶点的度还是偶数, 但是不一定连 通了. 对每个连通分支重复进行.

定理1(3)=(1) (1)G是欧拉图 (3)G是若干个边不交的圈的并 证明:(3)=(1):有公共点但边不交的简单 回路,总可以拼接成欧拉回路:在交点处, 走完第1个回路后再走第2个回路.# ◆用归纳法严格证明( 《集合论与图论》第17讲

《集合论与图论》第17讲 8 定理1((3)⇒(1)) (1) G是欧拉图 (3) G是若干个边不交的圈的并 证明: (3)⇒(1): 有公共点但边不交的简单 回路, 总可以拼接成欧拉回路: 在交点处, 走完第1个回路后再走第2个回路. # 用归纳法严格证明

无向半欧拉图的充分必要条件 定理2:设G是无向连通图,则 (1)G是半欧拉图 2)G中恰有2个奇度顶点 证明:(1)→>(2):欧拉通路的起点和终点是 奇数度,其余顶点都是偶数度. 2)→(1):在两个奇数度顶点之间加1条新边 所有顶点都是偶数度,得到欧拉回路从欧 拉回路上删除所加边后,得到欧拉通路# 《集合论与图论》第17讲

《集合论与图论》第17讲 9 无向半欧拉图的充分必要条件 定理2: 设G是无向连通图,则 (1) G是半欧拉图 ⇔ (2) G中恰有2个奇度顶点 证明: (1)⇒(2): 欧拉通路的起点和终点是 奇数度,其余顶点都是偶数度. (2)⇒(1): 在两个奇数度顶点之间加1条新边, 所有顶点都是偶数度,得到欧拉回路.从欧 拉回路上删除所加边后,得到欧拉通路. #

有向欧拉图的充分必要条件 婚定理3:设G是有向连通图,则 (1)G是欧拉图 (2)veVG),d()=d() 台→(3)G是若干个边不交的有向圈的并 静证明:(1)→(2)→(3)→(1) (1)=(2):若欧拉回路总共k次经过顶点则 d* (v=d (v=k 其余与定理1类似.# 《集合论与图论》第17讲

《集合论与图论》第17讲 10 有向欧拉图的充分必要条件 定理3: 设G是有向连通图,则 (1) G是欧拉图 ⇔ (2) ∀v∈V(G), d+(v)=d-(v) ⇔ (3) G是若干个边不交的有向圈的并 证明: (1)⇒(2)⇒(3)⇒(1). (1)⇒(2): 若欧拉回路总共k次经过顶点v,则 d+(v)=d-(v)=k. 其余与定理1类似. #