有向欧紅图的定定理 定理15.3有向图D是欧拉图当且仅当D是强连通的且每个顶点的 入度都等于出度。 定理15.4有向图D是半欧拉图当且仅当D是单向连通的,且D中 恰有两个奇度顶点,其中一个的入度比出度大1,另一个的出 度比入度大1,而其余顶点的入度都等于出度。(举例) (2) 定理15.5G是非平凡的欧拉图当且仅当G是连通的且为若干个边 不重的圈的并
有向欧拉图的判定定理 定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶点的 入度都等于出度。 定理15.4 有向图D是半欧拉图当且仅当D是单向连通的，且D中 恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出 度比入度大1，而其余顶点的入度都等于出度。(举例) 定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干个边 不重的圈的并
15,1 例15.1设G是非平凡的且非环的欧拉图,证明 (1)入G)≥2 (2)对于G中任意两个不同顶点u,,都存在简单回路C含u和v 证明(1)由定理155可知,ve∈E(G,存在圈C,e在C中 因而p(G-e)=p(G,故e不是桥。 由e的任意性λ(G≥2,即G是2边-连通图。 (2)u,v∈V(G,u≠v,由G的连通性可知,,v之间必存在路径 「1,设G′=GE(「1,则在G中n与还必连通, 否则,u与w必处于G'的不同的连通分支中, 这说明在「1上存在G中的桥,这与(1)矛盾。 于是在G中存在u到v的路径「2,显然「与「2边不重, 这说明u,v处于「1U「2形成的简单回路上
例15.1 例15.1 设G是非平凡的且非环的欧拉图，证明： (1)λ(G)≥2。 (2)对于G中任意两个不同顶点u,v，都存在简单回路C含u和v。 证明 (1)由定理15.5可知，e∈E(G)，存在圈C，e在C中， 因而p(G-e)＝p(G)，故e不是桥。 由e的任意性λ(G)≥2，即G是2边-连通图。 (2)u,v∈V(G)，u≠v，由G的连通性可知，u,v之间必存在路径 Г1，设G ＝G-E(Г1 )，则在G 中u与v还必连通， 否则，u与v必处于G 的不同的连通分支中， 这说明在Г1上存在G中的桥，这与(1)矛盾。 于是在G 中存在u到v的路径Г2，显然Г1与Г2边不重， 这说明u,v处于Г1∪Г2形成的简单回路上
求欧拉岛中欧拉回路的算法 Fleury算法,能不走桥就不走桥 (1)任取v∈V(G,令P=v。 (2)设Pi=ve1v1e2…!已经行遍,按下面方法来从 E(G-{e1,e2,…,el}中选取e1 (a)er1与v相关联; (b)除非无别的边可供行遍,否则e1不应该为 G;=G-{e1,e2,…,t}中的桥。 (3)当(2)不能再进行时,算法停止。 说明可以证明,当算法停止时所得简单回路 2-Voe1v1e2 为G中一条欧拉回路
求欧拉图中欧拉回路的算法 Fleury算法，能不走桥就不走桥 (1) 任取v0∈V(G)，令P0＝v0。 (2) 设Pi＝v0e1v1e2…eivi已经行遍，按下面方法来从 E(G)-{e1,e2,…,ei}中选取ei+1： (a) ei+1与vi相关联； (b) 除非无别的边可供行遍，否则ei+1不应该为 Gi＝G-{e1,e2,…,ei}中的桥。 (3)当(2)不能再进行时，算法停止。 说明 可以证明，当算法停止时所得简单回路 Pm ＝v0e1v1e2…emvm(vm ＝v0) 为G中一条欧拉回路
Feuy算法示例
Fleury算法示例