离散数学15 欧拉图与哈密顿图

判断所示两图是否为欧拉图、半欧拉图？

无向欧拉图与无向半欧拉图的判断方法

定理15.1（无向欧拉图的判定）无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。

定理15.2（无向半欧拉图的判定）无向图G是半欧拉图当且仅当G是连通图，且G中恰有两个奇度顶点。

（1）（2）（3）

有向欧拉图与有向半欧拉图的判断方法

定理15.3（有向欧拉图的判定）有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。

定理15.4（有向半欧拉图的判定）有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。

（4）（5）（6）

由两判定定理，立即可知（4）为欧拉图，

（5）、（6）即不是欧拉图，也不是半欧拉图。

例15.2（P296）

v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2

?

Fleury算法

??

?

（1）任取v0?V(G)，令P0=v0。

（2）设Pi=v0e1v1e2…..eivi已经行遍，则按下面方法来从E(G)-{e1,e2,….,ei}中选取ei+1：（a）ei+1与vi相关联；

（b）除非无别的边可供选择，否则eG-{ei+1不应该为1,e2,….,ei}中的桥。

（3）当（2）不能再进行时，算法停止，得到的Pn=v0e1v1e2…..envn为G中的一条欧拉回路。

桥：设e?E(G)，若p(G-e)>p(G)，则称e为G中的桥。