- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
(续…)
15.1 欧拉图
(…接)
5
由归纳假设可知: G’1, G’2, …, G’s都是欧拉图, 因此, 都存 在欧拉回路C’i(i = 1..s)。 现在将C还原(即将删除的边重新加上), 并从C上的某顶点 vr开始进行遍历, 每遇到vji*, 就行遍G’i中的欧拉回路 C’i(i=1..s), 最后, 回到vr, 得回路C”: vr… vj1* … vj1* … vj2* … vj2* … vjs* … vjs* … vr。 此回路C”经过G中每条边一次且仅一次。因此, C”是G中 的欧拉回路(如右下图所示)。 故, G为欧拉图。
14
15.1 欧拉图
15
例15.2 下图(a)是给定的欧拉图G。有人用Fleury算法求G中 欧拉回路时, 获得简单回路: v2e2v3e3v4e14v9e10v2 e1v1e8v8e9v2之后, 无法遍历了, 试分析在哪步他犯了 错误?
解 此人行遍v8时犯 了 “能不走桥就不走 桥”的错误, 因此, 无 法获得欧拉回路。 当走到v8时, G - { e2, e3, e14, e10, e1, e8 }为图(b)所示。 此时e9为该图中的桥, 而e7,e11均不是桥, 因此不应选e9, 而应选 e7或e11, 所以, 在选择边时犯了错误。 注意, 在行遍历图时, 在v3遇到桥e3, v1处遇到桥e8, 但当时除桥 外他无别的边可走, 所以, 此时只能选择桥, 这不是犯错误。
1
第十五章 欧拉图与哈密顿图
15.1 欧拉图 15.2 哈密顿图 15.3 最短路问题与货郎担问题
15.1 欧拉图
定义15.1 包含图中所有边仅一次的通路称为欧拉通路; 包含图中所有边仅一次的回路称为欧拉回路; 具有欧拉回路的图称为欧拉图(Euler Graph); 具有欧拉通路, 但无欧拉回路的图称为半欧拉图。 规定: 平凡图(N1)是欧拉图。 图(a)是欧拉图, e1e2e3e4e5是欧拉回路 图(b)是半欧拉图, e1e2e3e4e5是欧拉通 路, 但不存在欧拉回路 图(c)不是欧拉图, 也不是半欧拉图, 其 既没有欧拉回路, 也没有欧拉通路 图(d)是欧拉图, e1e2e3e4是欧拉回路 图(e)和(f)中既没有欧拉回路, 也没有欧 拉通路
15.1 欧拉图
由定理15.3和15.4可知: 有向图(d)是欧拉图 图(e)和(f)没有半欧拉图
11
15.1 欧拉图
12
由定理15.1可知: 下图(a)图为欧拉图, 本图既可以看成由 圈v1v2v8v1, v2v3v4v2, v4v5v6v4和v6v7v8v6之并(如图(b)), 也可 看成圈v1v2v3v4v5v6v7v8v1与v2v4v6v8v2之并(如图(c))。
将图(a)分解成若干个边不重的圈, 并不是图(a)特有的性 质, 任何欧拉图都有这个性质。
15.1 欧拉图
定理15.5 G是非平凡的欧拉图, 当且仅当G是连通的, 且是若 干个边不重的圈之并。 可用归纳法证明之。
例15.1 设G是非平凡的且非环的欧拉图, 证明: (1) (G) 2 (2) u, v V(G), 都有包含u和v的简单回路
(续…)
3
15.1 欧拉图
(…接) 2). 充分性 由G为非平凡的连通图可知: G中边数m 1。对m作归纳。
4
(1) m = 1时, 由G的连通性和无奇度顶点可知: G只能是一个环, 因此, G为欧拉图。 (2) 设m k(k 1)时, 结论成立．要证明m = K+1时, 结论也成 立。 由G的连通性和无奇度顶点可知: (G) 2。 用扩大路径法可以证明G中存在长度大于或等于3的圈。 设C为G中一个圈, 删除C上的全部边, 得G的生成子图G’。 设G’有s个连通分支G’1, G’2, …, G’s, 每个连通分支至多有k条 边, 且无奇度顶点, 并且设G’i与C的公共顶点为vji*(i = 1..s)。
7
15.1 欧拉图
定理15.2 无向图G是半欧拉图, 当且仅当G是连通的, 且G中 恰有两个奇度顶点。 证 1). 必要性
设G是m条边的n阶无向图。
8
因为G为半欧拉图, 因而G中存在欧拉通路(但不存在欧拉回路)。 设 = vi0ej1vi1…vim-1ejmvim为G中一条欧拉通路, vi0 vim。显 然, G是连通性。 v V(G): 若v不在的端点出现, 显然d(v)为偶数 若v在端点出现过, 则d(v)为奇数 因为只有两个端点不同, 因此, G中只有两个奇数顶点。 (续…)
15.2 哈密顿图
18
定理15.6 设哈密顿图G = <V, E>, 对于V1 V, 且V1 , 均 有: p(G - V1) |V1|, 其中, p(G - V1)为G-V1的连通 分支数。 证 假设: C为G中的一条哈密顿回路。 当V1中顶点在C上均不相邻时, p(C-V1)达到最大值|V1|; 当V1中顶点在C上有彼此相邻的情况时, 均有: p(C-V1) < |V1|。 所以, 有: p(C-V1) |V1|。 又C是G的生成子图, 所以, 有: p(G-V1) p(C-V1) |V1|。
13
(1) 由定理15.5可知: e E(G), 存在圈C: e在C中。 因此, p(G-e) = p(G), 所以, e不是桥。 由e的任意性可知: (G) 2, 即G是2边-连通图。 (2) u, vV(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形成的简单回路上。 证
15.2 哈密顿图
定义15.2 经过图中所有顶点仅一次的通路称为哈密顿通路; 经过图中所有顶点仅一次的回路称为哈密顿回路; 具有哈密顿回路的图称为哈密顿图(Hamiltonian Graph), 平凡图是哈密顿图; 具有哈密顿通路, 但不具有哈密顿回路的图称为半 哈密顿图。
16
图(a)、(b)和(c)都有哈密顿回路, 它们 都是哈密顿图 图(d)具有哈密顿回路, 它是哈密顿图 图(e)只有哈密顿通路, 但无哈密顿回路, 它是半哈密顿图 图(f)既无哈密顿回路, 也没有哈密顿通 路, 它不是哈密顿图, 也不是半哈密顿图。
15.2 哈密顿图
例15.3 在下图中给出的三个图都是二部图。问: 哪些是哈密 顿图？哪些是半哈密顿图？为什么？
20
解 图(a)中, 子集V1 = { a, f }和V2 = { b, c, d, e }是互补的。 设此二部图为G1, 则G1 = <V1, V2, E>, p(G1-V1) = 4 > |V1| = 2。 由定理15.6和其推论可知: G1不是哈密顿图, 也不是半哈密顿图。 图(b)为G2 = <V1, V2, E>, 其中V1 = { a, g, h, i, c }, V2 = { b, e, f, j, k, d}, 显然, p(G2-V1) = |V2| = 6 > |V1| = 5。 由定理15.6可知: G2不是哈密顿图, 但G2是半哈密顿图, baegjckhfid是G2一条 哈密顿通路。 图(c)为G3 = <V1, V2, E>, 其中V1 = { a, c, g, h, e }, V2 = { b, d, i, j, f } G3中存在哈密顿回路, 如: abcdgihjefa, 所以, G3是哈密顿图。
15.2 哈密顿图
定理15.6的条件是哈密顿图的必要条 件, 不是充分条件。可以验证右图(彼得松 图)满足该定理的条件, 但它不是哈密顿图。 若一个图不满足定理中的条件, 那它 一定不是哈密顿图。
19
推论 设半哈密顿图G = <V, E>, 对于任意V1 V, 且V1 , 均 有: p(G-V1) |V1|+1。 证 设P是G中起于u终于v的哈密顿通路。 令G’ = G∪(u, v)(在G的顶点u,v之间加新边)。 显然, G’为哈密顿图。 由定理15.6可知: p(G’-V1) |V1|。 于是, 有: p(G-V1) = p(G’-V1-(u,v)) p(G’-V1)+1 |V1|+1。
5.1 欧拉图
设G为欧拉图, 通常情况下, G中存在若干条欧拉回路。 下面介绍两种求欧拉回路的算法。 1．Fleury算法 (1) 任取v0V(G), 令P0=v0 (2) 设Pi = v0e1v1e2…eivi已经遍历, 按下面方法从 E(G) - { e1, e2, …, ei }中选取ei+1: ei+1与vi相关联 ei+1不应取Gi = G - { e1, e2, …, ei }中的桥, 除非无 其它边可供行遍 (3) 重复步骤(2), 直到步骤(2)不能再进行为止。 可证明: 当算法停止时, 所得简单回路Pm = v0e1v1 e2 … emvm(vm=v0)为G中一条欧拉回路。
15.1 欧拉图
由定理15.2可知: 图(b)是半欧拉图 图(c)不是半欧拉图
10
定理15.3 有向图D是欧拉图, 当且仅当D是强连通的, 且每个 顶点的入度都等于出度。 本定理的证明类似于定理15.1。 定理15.4 有向图D是半欧拉图, 当且仅当D是单向连通的, 且 D中恰有两个奇度顶点, 其中一个的入度比出度大1, 另一个的出度比入度大1, 而其余顶点的入度都等于 出度。 本定理的证明从略。
15.1 欧拉图
定理15.2 无向图G是半欧拉图, 当且仅当G是连通的, 且G中 恰有两个奇度顶点。
9
(…接) 2). 充分性 设G的两个奇度顶点分别为u0和v0。 对G加新边(u0, v0), 得G’ = G∪(u0, v0), 则G’是连通的且 无奇度顶点的图。 由定理15.1可知: G’为欧拉图。 因此, 存在欧拉回路C, 于是, C - (u0, v0)为G中一条欧拉 通路。 所以, G为半欧拉图。
