第9章 欧拉图和哈密顿图

10
例如，由定理可知，下图 (a)图为欧拉图，本图 既v成圈8 可圈画v6之v以在1并(看vc2)(成v中为3 圈v)清。4 vv晰1将5v起v2(6av见v)87分v，v1解8，将v成1v与42若个v圈3干圈vv42个画vv24边在，v6不(vb4v)8重v中5v2的v)之6，圈v并也4，的(可两v并6看个v7 不是(a)图特有性质，任何欧拉图都有这个性质。
9
定理9.1.2 设G=<V, E>是有向弱连通图，则 （1）当且仅当G的每个顶点的入度等于出度时， G是欧拉图。 （2）当且仅当G除两个顶点外，其它顶点的入度 等于出度，而除外的两个顶点，一个的入度比出度 多1，另一个的入度比出度少1时，G有欧拉通路。
定理9.1.1和定理9.1.2提供了欧拉通路与欧拉回 路的十分简便的判别准则。
v1
v2
v3
v8
v4
v1 v2 v2 v3
v8
v4
v8
v4
v1
v2
v3
v2
v8 v8
v4 v4
v6
v7
v6
v5
（a）
（b） v7 v6 v6 v5
v7 （vc6 ） v5
定理9.1.3 G是非平凡的欧拉图当且仅当G是连 通的且为若干个边不重的圈的并。
11
❖ 9.1.3 欧拉图的难点 对于欧拉图，需要大家注意以下几点： 1．仅有欧拉通路而无欧拉回路的图不是欧拉图。 2. 图中是否存在欧拉通路、欧拉回路的判定非常简单，
第四篇 图 论
1
第九章 欧拉图和哈密顿图
❖ 9.1 欧拉图 ❖ 9.2 哈密顿图
2
9.1 欧拉图
9.1.1 欧拉图的引入和定义 18世纪中叶，在东普鲁士哥尼斯堡城，有一条
贯穿全城的普雷格尔河，河中有两个岛，通过七座 桥彼此相连，如图9.1.1(a)所示。
（a）
b1 A
b3
图 9.1.1
D
b5
b2 b6
只要数一下图中节点的度数即可。
❖ 9.1.4 欧拉图的应用 一笔画问题 所谓“一笔画问题”就是画一个图形，笔不离纸，每条 边只画一次而不许重复地画完该图。“一笔画问题”本质上 就是一个无向图是否存在欧拉通路（回路）的问题。如果该 图为欧拉图，则能够一笔画完该图，并且笔又回到出发点； 如果该图只存在欧拉通路，则能够一笔画完该图，但笔回不 到出发点；如果该图中不存在欧拉通路，则不能一笔画完该 图。
此时仍有四条边不在圈C中，边(4, 6)不在C中 且与节点4相关联，由节点4出发经过边(4, 6)又可得 到一个简单圈C ’ ’ ：(4, 6, 5, 2, 4)，将C ’ ’并入C得 到一个更长的简单圈C：(1, 2, 3, 4, 6, 5, 2, 4, 5, 3, 1)。 可以看到，G中所有的边已全在C中了，故知此圈C 即为G中的一条欧拉圈。
14
将这个问题加以推广，即在任意连通图中是否 存在一条包含图中所有节点的基本通路或基本回路。
定义9.2.1 通过图中每个顶点一次且仅一次的 通路（回路）称为哈密顿通路（回路）。一个具有 哈密顿回路的图称为哈密顿图。
规定：平凡图为哈密顿图。
另外，以上定义既适合无向图，又适合有向图。
15
❖ 9.2.2 哈密顿图的判定
C
b4
b7
B（b）
3
定义9.1.1 设G是无孤立节点的图，若存 在一条通路(回路)，经过图中每边一次且仅一 次，则称此通路(回路)为该图的一条欧拉通路 (回路)。若存在一个圈，此圈通过G中每条边 一次且仅一次，则此圈成为欧拉圈。具有欧 拉回路的图称为欧拉图，具有欧拉通路但无 欧拉回路的图称为半欧拉图。
解：在6个图中，图 (a)和(d)是欧拉图；图 (b) 和(e)不是欧拉图，但存在欧拉通路；图 (c)和(f)不 存在欧拉通路。
6
9.1.2 欧拉图的判定 判断一个图（无向图或有向图）是否有欧拉通
路（回路），要考察所有边的所有全排列，几乎是 不可能的，所幸已有简单的判别法。
定理9.1.1 设无向图G=<V, E>是连通的，则 （1）当且仅当G的每个顶点都是偶顶点时，G是 欧拉图。 （2）当且仅当G除两个顶点是奇顶点外，其它 顶点都是偶顶点时，G有欧拉通路。
7
1
2
3
5
4
6
图 9.1.5
例9.1.2 图G如图9.1.5所示。问图G是否 为欧拉图？若是，求出其欧拉圈。
由于G中的六个节点均为偶顶点且G连通， 根据欧拉定理可知G为欧拉图。
8
在图9.1.5中任意找一简单圈C：(1, 2, 3, 1)；发 现还有七条边不在此圈中，边(3, 4)不在C中且在圈 中的节点3相关联，由节点3出发经过边(3, 4)可得到 一简单圈C ’(3, 4, 5, 3)，将C ’并入C得到了一个新的 更长的简单圈C：(1, 2, 3, 4, 5, 3, 1)。
尽管讨论哈密顿通路和哈密顿回路在形式上与欧
拉通路和欧拉回路非常相似，但遗憾的是到目前为止， 仍然没有找到一个合适的条件来作为判断哈密顿通路 或哈密顿回路存在的充要条件。不过，可以给出哈密 顿通路和哈密顿回路存在的充分条件或必要条件。
12
9.2 哈密顿图
❖ 9.2.1 哈密顿图的引入和定义
1859年威廉哈密顿爵士发明了一个小玩具，这 个小玩具是一个木刻的正十二面体，每面系正五角 形，三面交于一角，共有20个角，每角标有世界上 一个重要城市，如图9.2.1所示。他提出一个问题： 要求沿正十二面体的边寻找一条路通过20个城市， 而每个城市只通过一次，最后返回原地。哈密顿将 此问题称为周游世界问题。
4
规定：平凡图是欧拉图。 以上定义既适合无向图，又适合有向图。 例9.1.1 判断下图的6个图中，是否是欧拉图？是否存在欧拉通路。
v1
v4
v1
v4
v1
v4
v2
v3
(a)
v1
v4
v2
v3
(b)
v1
v4
v2
v3
(c)
v1Biblioteka v4v2 (d) v3v2 (e) v3
v2 (f) v3
5
分析：如果说图中存在欧拉通路（回路）， 具体找出一条经过图中每边一次且仅一次的通路 (回路)即可；如果说图中不存在欧拉通路(回路)， 则要试遍了边的所有全排列，它们都不能构成通 路（回路）。
13
1
2
20 13 12 19 18 14 15 11
5
6
17 7
16
8
10 9
3
4
图 9.2.1
上述周游世界问题可用图论语言描述为：能否在图9.2.1所 示的图中找到一条包含所有节点的基本回路。按照图中所给城 市的编号，容易找到一条从节点1到2，再到3，到4，……， 最后到达20，再回到1的包含图中每个节点的基本回路，即周 游世界是可行的。