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