无向欧拉图的充分必要条件 婚定理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类似. #