PDF《欧拉图与哈密顿图》

6 IntroductionToCS--Xiaofeng Gao 证明(2) 证明(3) G1可能是非连通图,每个顶点的度保持为 可能是非连通图,每个顶点的度保持为 可能是非连通图,每个顶点的度保持为 可能是非连通图,每个顶点的度保持为 偶数.这时, 偶数.这时, 偶数.这时, 偶数.这时,G1中一定存在某个度非 中一定存在某个度非 中一定存在某个度非 中一定存在某个度非零的 零的 零的 零的 节点 节点 节点 节点vi,同时也是 ,同时也是 ,同时也是 ,同时也是C中顶点.否则 中顶点.否则 中顶点.否则 中顶点.否则C的顶点 的顶点 的顶点 的顶点 与与与与G1的的的的顶点之间无边相连,与 顶点之间无边相连,与 顶点之间无边相连,与 顶点之间无边相连,与G是连通图矛 是连通图矛 是连通图矛 是连通图矛 盾.同理,从盾.同理,从盾.同理,从盾.同理,从vi出发, 出发, 出发, 出发,G1中所在的连通分量 中所在的连通分量 中所在的连通分量 中所在的连通分量 内存在一条 内存在一条 内存在一条 内存在一条简单回路 简单回路 简单回路 简单回路C1. . . .C ∪ ∪ ∪ ∪ C1仍然是 仍然是 仍然是 仍然是G 的一条 的一条 的一条 的一条简单回路,但 简单回路,但 简单回路,但 简单回路,但它包括的边数比 它包括的边数比 它包括的边数比 它包括的边数比C多. 多. 多. 多. 继续构造,最终有 继续构造,最终有 继续构造,最终有 继续构造,最终有C'

=C ∪ ∪ ∪ ∪ C1 ∪ ∪ ∪ ∪… ∪ ∪ ∪ ∪ Ck是是是是一条 一条 一条 一条欧拉回路. 欧拉回路. 欧拉回路. 欧拉回路. 2016/12/6

7 IntroductionToCS--Xiaofeng Gao 范例 【 【 【 【例例例例】 】 】 】 判断下图是否欧拉图: 判断下图是否欧拉图: 判断下图是否欧拉图: 判断下图是否欧拉图: a b c d e G a b c d H 2016/12/6

8 IntroductionToCS--Xiaofeng Gao 【 【 【 【例例例例】 】 】 】试找出下图的一条欧拉回路. 试找出下图的一条欧拉回路. 试找出下图的一条欧拉回路. 试找出下图的一条欧拉回路. 2016/12/6

9 IntroductionToCS--Xiaofeng Gao 范例(2) 【 【 【 【解解解解】 】 】 】从任一点出发,比如 从任一点出发,比如 从任一点出发,比如 从任一点出发,比如 v1开始,可构造简单回路 开始,可构造简单回路 开始,可构造简单回路 开始,可构造简单回路 C=(e1,e8,e6,e7,e2). . . . G1=GD D D DC中的 中的 中的 中的v

2、 、 、 、v5度非零 度非零 度非零 度非零 且是 且是 且是 且是C中的节点.从 中的节点.从 中的节点.从 中的节点.从v2开始 开始 开始 开始G1 中有简单回路 中有简单回路 中有简单回路 中有简单回路C1=(e3,e5,e4), , , , 因此 因此 因此 因此 C∪ ∪ ∪ ∪C1=(e1,e3,e5,e4,e8,e6,e7,e2) 包含了 包含了 包含了 包含了G的所有边,是 的所有边,是 的所有边,是 的所有边,是G的欧 的欧 的欧 的欧 拉回路. 拉回路. 拉回路. 拉回路. 2016/12/6

10 IntroductionToCS--Xiaofeng Gao 解2016/12/6

11 IntroductionToCS--Xiaofeng Gao 其他解法 有向连通图的欧拉回路 【 【 【 【推论 推论 推论 推论】 】 】 】若有向连通图 若有向连通图 若有向连通图 若有向连通图G中各节点的正负度 中各节点的正负度 中各节点的正负度 中各节点的正负度 相等 相等 相等 相等,则则则则G中存在有向欧拉回路 中存在有向欧拉回路 中存在有向欧拉回路 中存在有向欧拉回路. 证明方法类似之前定理,由 证明方法类似之前定理,由 证明方法类似之前定理,由 证明方法类似之前定理,由G是有穷图且每 是有穷图且每 是有穷图且每 是有穷图且每 个节点正负度相等可以断定从 个节点正负度相等可以断定从 个节点正负度相等可以断定从 个节点正负度相等可以断定从G的任一节点 的任一节点 的任一节点 的任一节点 v0出发一定存在 出发一定存在 出发一定存在 出发一定存在G的一条简单回路 的一条简单回路 的一条简单回路 的一条简单回路C.若 .若 .若 .若 C=E(G),则得证.否则在 ,则得证.否则在 ,则得证.否则在 ,则得证.否则在G中删去 中删去 中删去 中删去C的各 的各 的各 的各 边,找到新的简单回路 边,找到新的简单回路 边,找到新的简单回路 边,找到新的简单回路C1,并添加至 ,并添加至 ,并添加至 ,并添加至C中. 中. 中. 中. 重复该步骤直至 重复该步骤直至 重复该步骤直至 重复该步骤直至C成为欧拉回路为止. 成为欧拉回路为止. 成为欧拉回路为止. 成为欧拉回路为止. 2016/12/6