判断所示两图是否为欧拉图、半欧拉图?
无向欧拉图与无向半欧拉图的判断方法
定理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中的桥。
离散数学15 欧拉图与哈密顿图
判断所示两图是否为欧拉图、半欧拉图?无向欧拉图与无向半欧拉图的判断方法定理15.1(无向欧拉图的判定)无向图G是欧拉图当且仅当G是连通图,且G中没有奇度顶点。定理15.2(无向半欧拉图的判定)无向图G是半欧拉图当且仅当G是连通图,且G中恰有两个奇度顶点。(1)(2)(3)有向欧拉图与有向半欧拉图的判断方法定理
推荐度:
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
点击下载文档文档为doc格式