15 欧拉图与哈密顿图
小结
同欧拉图不同,到目前为止,还没有找到 哈密顿图的简单充分必要条件。对哈密顿图 来讲,只有充分条件或必要条件。 如果在图中能找到哈密顿回路或者满足某 充分性定理的条件,则该图为哈密顿图。 人们可以根据哈密顿图的某些必要条件判断 某些图不是哈密顿图。 欧拉图和哈密顿图的区别在于欧拉图是生 成简单回路,而哈密顿图是生成初级回路。
14
弗罗莱(Fleury)算法
图示动态过程
15
15.2 哈密顿图
历史背景:哈密顿周游世界问题与哈密顿图
16
哈密顿图
定义15.2 经过图(有向图或无向图)中所有顶点一 次且仅一次的通路称为哈密顿通路。经过图中所有 顶点一次且仅一次的回路称为哈密顿回路。具有哈 密顿回路的图称为哈密顿图,具有哈密顿通路但不 具有哈密顿回路的图称为半哈密顿图。 规定:平凡图是哈密顿图。 说明:哈密顿通路是图中生成的初级通路, 哈密顿回路是生成的初级回路。
v3 (v1, ∞) (v1, 7) (v2, 5)** (v2, 5)* (v2, 5)* (v2, 5)* (v2, 5)*
v4 (v1, ∞) (v1, 5) (v1, 5) (v1, 5)** (v1, 5)* (v1, 5)* (v1, 5)*
v5 (v1, ∞) (v1, ∞) (v2, 9) (v3, 8) (v3, 8) (v3, 8)** (v3, 8)*
离散数学
第15章 欧拉图与哈密顿图
1
本章内容
15.1 欧拉图 15.2 哈密顿图 15.3 最短路问题与货郎担问题 基本要求 作业
2
15.1 欧拉图
历史背景--哥尼斯堡七桥问题
欧拉图是一笔画出的边不重复的回路。
3
欧拉图
定义15.1 通过图(无向图或有向图)中所有边一次 且仅一次行遍图中所有顶点的通路称为欧拉通路, 通过图中所有边一次并且仅一次行遍所有顶点的回 路称为欧拉回路。具有欧拉回路的图称为欧拉图, 具有欧拉通路而无欧拉回路的图称为半欧拉图。 规定:平凡图是欧拉图。 说明:欧拉通路是图中经过所有边的生成的简单通路 (经过所有顶点的通路称为生成通路)。 欧拉回路是经过所有边的生成的简单回路。
例15.5
下图所示的三个图中哪些是哈密顿图?哪些是半哈密顿图?
(1)存在哈密顿回路,所以(1)为哈密顿图。 (2)取V1={a,b,c,d,e},从图中删除V1得7个连通分支, 由定理15.6和推论可知,不是哈密顿图,也不是半哈密顿图。 (3)取V1={b,e,h},从图中删除V1得4个连通分支,由定理15.6可 32 知,它不是哈密顿图。但存在哈密顿通路,所以是半哈密顿图。
有欧拉通路 半欧拉图
无欧拉通路
有欧拉通路 半欧拉图
9
有向欧拉图的判定定理
定理15.5 G是非平凡的欧拉图当且仅当G是连通的 且为若干个边不重的圈的并。
10
求欧拉图中欧拉回路的算法
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)
17
例题
(1)(2)是哈密顿图。 (3)是半哈密顿图。 (4)既不是哈密顿图,也不是半哈密顿图。
18
哈密顿图的充要条件
判断一个图是否为哈密顿图,就是判断能否将图中所 有顶点都放置在一个初级回路(圈)上,但这不是一件 易事。 与判断一个图是否为欧拉图不一样,到目前为止,人 们还没有找到哈密顿图简单的充分必要条件。
33
欧拉图遍历边,而哈密顿图遍历顶点,它 们之间没有联系。 有的图只是欧拉图,有的只是哈密顿图, 有的两者都是,有的两者皆不是。 有割点或桥的图不是哈密顿图。 彼得松图既不是欧拉图也不是哈密顿图
34Biblioteka 都不是哈密顿图欧拉图
35
哈密顿图,欧拉图
15.3 最短路问题与货郎担问题
定义15.3 给定图G=<V,E>(G为无向图或有向图),设W: E→R(R为实数集),对G中任意的边e=(vi,vj)(G为有向图 时,e=<vi,vj>),设W(e)=wij,称实数wij为边e上的权,并 将wij标注在边e上,称G为带权图,此时常将带权图G记作 <V,E,W>。 设P是G中的一条通路 ,P 中所有边的权之和称为P的长度. 并记作W(P), 即 W(P)=
v6 (v1, ∞) (v1, ∞) (v1, ∞) (v1, ∞) (v4, 7)** (v4, 7)* (v4, 7)*
7
无欧拉通路
有向欧拉图的判定定理
定理15.3 有向图D是欧拉图当且仅当D是连通的且每个 顶点的入度都等于出度。 定理15.4 有向图D是半欧拉图当且仅当D是连通的,且 D中恰有两个奇度顶点,其中一个的入度比出度大1 ,另一个的出度比入度大1,而其余顶点的入度都等 于出度。
8
实例
欧拉图
无欧拉通路
无欧拉通路
29
(15.1)
例 有7个人,A会讲英语,B会讲英语和汉语,C会讲 英语、意大利语和俄语,D会讲日语和汉语,E会讲 德语和意大利语,F会讲法语、日语和俄语,G会讲 法语和德语。问能否将他们沿圆桌安排就坐成一圈 ,使得每个人都能与两旁的人交谈? 解 作无向图, 每人是一个顶点, 2人之间有边⇔他们有共同的语言. ACEGFDBA是一条哈密顿回 路,按此顺序就坐即可.
21
实例
验证彼得松图满足此条件,但不是哈密顿图。 右图满足 p(G-V1)≤|V1| 证明下述各图不是哈密顿图: 只要证不满足 p(G-V1)≤|V1|
彼得松图
(a)
(b)
22
(c)
推论(了解)
推论 设无向图G=<V,E>是半哈密顿图,对于任意的 V1⊂V且V1≠∅,均有 p(G-V1)≤|V1|+1
v2
2 2 7 3 3 6 5 3 3 2
v5
v1
1 5
v3
8 2
7
v7
4
v4
37
2 6
v6
问题:求从v1到其余各点的最短路径和距离?
v2
3 2 2 7 3 3 6 5 3
v5
2
start v1 1
5
v3
8 2
7
v7
4
2 6
v4
38
v6
Dijkstra(迪杰斯特拉)算法
步骤 1 ∞
2 3 2 7 3 3 6 3
e∈ E(P)
∑
W (e)
类似地,可定义回路C 的长度W(C)。 带权图应用的领域是相当广泛的,许多图论算法都是针 对带权图的。
36
最短路问题
G=<V,E>(无向图或有向图),其中每一条边 e的权W(e)为非 负实数。 u,v之间的短程线的长度称为u,v之间的距离,记作 d(u,v)。 约定d(u,u)=0.当u,v不连通时,d(u,v)=∞。 最短路问题:给定带权图G=<V,E,W>及顶点u,v ,其中每一 条边e的权W(e)为非负实数,求u到v的最短路径。 Dijkstra(迪杰斯特拉)算法:是典型最短路算法,用于计算一 个节点到其他所有节点的最短路径。主要特点是以起始点为 中心向外层层扩展,直到扩展到终点为止。
4
举例
无向图
欧拉图 有向图
半欧拉图
无欧拉通路
欧拉图
半欧拉图
5
无欧拉通路
无向欧拉图的判定定理
定理15.1 无向图G是欧拉图当且仅当G是连通图, 且G中没有奇度顶点。
定理15.2 无向图G是半欧拉图当且仅当G是连通的 ,且G中恰有两个奇度顶点。
6
实例
无欧拉通路
欧拉图
欧拉图
有欧拉通路 半欧拉图
有欧拉通路 半欧拉图
二合一:无 分开单独:有 只考虑:无向图
19
哈密顿图的必要条件 单个:有 具体内容:如下页
20
定理15.6
定理15.6 设无向图G=<V,E>是哈密顿图,对于任意 V1⊂V,且V1≠∅,均有 p(G-V1)≤|V1| 其中,p(G-V1)为G-V1的连通分支数。 说明 本定理是哈密顿图的必要条件,但不是充分条件。 若一个图不满足此条件,它一定不是哈密顿图。
哈密顿图的充分条件 单个:有 具体内容:如下页
28
定理15.7及推论
定理15.7(了解) 设G是n阶无向简单图,若对于G 中任意不相邻的顶点u,v,均有 d(u)+d(v)≥n-1 则G中存在哈密顿通路。 推论(掌握) 设G为n(n≥3)阶无向简单图,若对于 G中任意两个不相邻的顶点u,v,均有 d(u)+d(v)≥n (15.2) 则G中存在哈密顿回路,从而G为哈密顿图。
23
例15.3
例15.3 在下图中给出的三个图都是二部图。它们中 的哪些是哈密顿图?哪些是半哈密顿图?为什么? |V2|≥|V1|+2
易知互补顶点子集 V1={a,f } V2={b,c,d,e } 设此二部图为G1,则G1=<V1,V2,E > p(G1-V1)=4 > |V1|=2, 由定理15.6及其推论可知,G1不是哈 密顿图,也不是半哈密顿图。
11 为G中一条欧拉回路。
Fleury算法示例
12
Fleury算法示例
13
例15.2
下图是给定的欧拉图G。某人用Fleury算法求G中的欧拉回路时 ,走了简单回路v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后(观看他的 错误走法),无法行遍了,试分析在哪步他犯了错误? 解答 此人行遍v8时犯了能不走桥就不走桥 的错误,因而他没行遍出欧拉回路。 当他走到v8时,G-{e2,e3,e14,e10,e1,e8} 为下图所示。 此时e9为该图中的桥,而e7,e11均不是桥, 他不应该走e9,而应该走e7或e11,他没 有走,所以犯了错误。注意,此人在行 遍中,在v3遇到过桥e3,v1处遇到过桥 e8,但当时除桥外他无别的边可走,所 以当时均走了桥,这是不会犯错误的。