第 15章 欧拉图与哈密顿图离 散 数 学哈尔滨理工大学本科生课程计算机系本章内容
15.1 欧拉图
15.2 哈密顿图
15.3 带权图与货郎担问题基本要求作业
15.1 欧拉图
历史背景－－哥尼斯堡七桥问题
欧拉图是一笔画出的边不重复的回路 。
欧拉图定义 15.1 通过图（无向图或有向图）中 所有边一次且仅一次行遍图中所有顶点的通路称为 欧拉通路,通过图中所有边一次并且仅一次行遍所有顶点的 回路 称为 欧拉回路 。具有欧拉回路的图称为 欧拉图,具有欧拉通路而无欧拉回路的图称为 半欧拉图 。
说明 欧拉通路是图中经过所有边的简单的生成通路 (经过所有顶点的通路称为生成通路 )。
欧拉回路是经过所有边的简单的生成回路。
举例欧拉图 半欧拉图 无欧拉通路欧拉图 无欧拉通路 无欧拉通路无向欧拉图的判定定理定理 15.1 无向图 G是欧拉图当且仅当 G是连通图，且 G中没有奇度顶点。
证明 若 G是平凡图，结论显然成立。
下面设 G为非平凡图，设 G是 m条边的 n阶无向图，
并设 G的顶点集 V＝ {v1,v2,…,vn}。
必要性 。因为 G为欧拉图，所以 G中存在欧拉回路，
设 C为 G中任意一条欧拉回路,?vi,vj∈ V,vi,vj都在 C上，
因而 vi,vj连通，所以 G为连通图。
又?vi∈ V,vi在 C上每出现一次获得 2度，
若出现 k次就获得 2k度，即 d(vi)＝ 2k，
所以 G中无奇度顶点。
定理 15.1的证明充分性 。由于 G为非平凡的连通图可知,G中边数 m≥1 。
对 m作归纳法。
(1)m＝ 1时，由 G的连通性及无奇度顶点可知，
G只能是一个环，因而 G为欧拉图。
(2)设 m≤ k(k≥1) 时结论成立，要证明 m＝ k+1时，结论也成立。
由 G的连通性及无奇度顶点可知,δ( G)≥2 。
无论 G是否为简单图，都可以用扩大路径法证明 G中必含圈。
定理 15.1的证明设 C为 G中一个圈，删除 C上的全部边，得 G的生成子图 G?，
设 G?有 s个连通分支 G?1,G?2,…,G?s，
每个连通分支至多有 k条边，且无奇度顶点，
并且设 G?i与 C的公共顶点为 v*ji,i＝ 1,2,…,s，
由归纳假设可知,G?1,G?2,…,G?s都是欧拉图，
因而都存在欧拉回路 C?i,i＝ 1,2,…,s。
最后将 C还原（ 即将删除的边重新加上 ），
并从 C上的某顶点 vr开始行遍，每遇到 v*ji,就行遍 G?i中的欧拉回路 C?i,i＝ 1,2,…,s,最后回到 vr，
得回路 vr… v*j1… v*j1… v*j2… v*j2… v*js… v*js… vr，
此回路经过 G中每条边一次且仅一次并行遍 G中所有顶点，
因而它是 G中的欧拉回路（ 演示这条欧拉回路 ），
故 G为欧拉图。
定理 15.2 无向图 G是半欧拉图当且仅当 G是连通的，且 G中恰有两个奇度顶点。
证明 必要性 。设 G是 m条边的 n阶无向图，因为 G为半欧拉图，
因而 G中存在欧拉通路 (但不存在欧拉回路 )，
设 Г ＝ vi0ej1vi1… vim-1ejmvim为 G中一条欧拉通路,vi0≠ vim。
v∈ V(G),若 v不在 Г 的端点出现，显然 d(v)为偶数，
若 v在端点出现过，则 d(v)为奇数，
因为 Г 只有两个端点且不同，因而 G中只有两个奇数顶点。
另外,G的连通性是显然的。
半欧拉图的判定定理定理 15.2 无向图 G是半欧拉图当且仅当 G是连通的，且 G中恰有两个奇度顶点。
证明 充分性 。设 G的两个奇度顶点分别为 u0和 v0，
对 G加新边（ u0,v0）,得 G?＝ G∪( u0,v0)，
则 G?是连通且无奇度顶点的图，
由定理 15.1可知,G?为欧拉图，
因而存在欧拉回路 C?,而 C＝ C?-(u0,v0)为 G中一条欧拉通路，
所以 G为半欧拉图。
半欧拉图的判定定理有向欧拉图的判定定理定理 15.3 有向图 D是欧拉图当且仅当 D是强连通的且每个顶点的入度都等于出度。
定理 15.4 有向图 D是半欧拉图当且仅当 D是单向连通的，且 D中恰有两个奇度顶点，其中一个的入度比出度大 1，另一个的出度比入度大 1，而其余顶点的入度都等于出度。 (举例 )
定理 15.5 G是非平凡的欧拉图当且仅当 G是连通的且为若干个边不重的圈的并。
例 15.1
例 15.1 设 G是非平凡的且非环的欧拉图，证明：
(1)λ( G)≥2 。
(2)对于 G中任意两个不同顶点 u,v,都存在简单回路 C含 u和 v。
证明 (1)由定理 15.5可知,?e∈ E(G),存在圈 C,e在 C中，
因而 p(G-e)＝ p(G),故 e不是桥。
由 e的任意性 λ( G)≥2,即 G是 2边 -连通图。
(2)?u,v∈ V(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形成的简单回路上。
求欧拉图中欧拉回路的算法
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)
为 G中一条欧拉回路。
Fleury算法示例例 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,但当时除桥外他无别的边可走，所以当时均走了桥，这是不会犯错误的。
15.2 哈密顿图
历史背景：哈密顿周游世界问题与哈密顿图哈密顿图定义 15.2 经过图（有向图或无向图）中 所有顶点一次且仅一次的通路 称为 哈密顿通路 。经过图中 所有顶点一次且仅一次的回路 称为 哈密顿回路 。具有哈密顿回路的图称为 哈密顿图,具有哈密顿通路但不具有哈密顿回路的图称为 半哈密顿图 。平凡图是哈密顿图。
说明 哈密顿通路是图中生成的初级通路，
哈密顿回路是生成的初级回路。
判断一个图是否为哈密顿图，就是判断能否将图中所有顶点都放置在一个初级回路 (圈 )上，但这不是一件易事。
与判断一个图是否为欧拉图不一样，到目前为止，人们还没有找到哈密顿图简单的充分必要条件。
例题
(1)(2)是哈密顿图。
(3)是半哈密顿图。
(4)既不是哈密顿图，也不是半哈密顿图。
定理 15.6
定理 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|。
说明 本定理的条件是哈密顿图的必要条件，但不是充分条件。
可以验证彼得松图满足定理中的条件，但不是哈密顿图。
若一个图不满足定理中的条件，它一定不是哈密顿图。
推论推论 设无向图 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
例 15.3
例 15.3 在下图中给出的三个图都是二部图。它们中的哪些是哈密顿图？哪些是半哈密顿图？为什么？
易知互补顶点子集
V1＝ {a,f}
V2＝ {b,c,d,e}
设此二部图为 G1,则 G1＝ <V1,V2,E>。
p(G1-V1)＝ 4>|V1|＝ 2，
由定理 15.6及其推论可知,G1不是哈密顿图，也不是半哈密顿图。
例 15.3
设图为 G2,则 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中一条哈密顿通路。
设图为 G3。 G3＝ <V1,V2,E>,其中
V1＝ {a,c,g,h,e},V2＝ {b,d,i,j,f}，
G3中存在哈密顿回路。
如 abcdgihjefa，
所以 G3是哈密顿图。
例 15.3的说明
哈密顿通路是经过图中所有顶点的一条初级通路。
哈密顿回路是经过图中所有顶点的初级回路。
对于二部图还能得出下面结论：
一般情况下，设二部图 G＝ <V1,V2,E>,|V1|≤| V2|,且 |V1|≥2
,|V2|≥2,由定理 15.6及其推论可以得出下面结论：
(1) 若 G是哈密顿图，则 |V1|＝ |V2|。
(2) 若 G是半哈密顿图，则 |V2|＝ |V1|+1。
(3) 若 |V2|≥| V1|+2,则 G不是哈密顿图，也不是半哈密顿图。
例 15.4 设 G是 n阶无向连通图。证明,若 G中有割点或桥，则 G不是哈密顿图。
证明 可用定理 15.6证明。
定理 15.7
定理 15.7 设 G是 n阶无向简单图，若对于 G中任意不相邻的顶点 vi,vj,均有
d(vi)+d(vj)≥ n-1 (15.1)
则 G中存在哈密顿通路。
证明 首先证明 G是连通图。
否则 G至少有两个连通分支，
设 G1,G2是阶数为 n1,n2的两个连通分支，
设 v1∈ V(G1),v2∈ V(G2),因为 G是简单图，所以
dG(v1)+dG(v2)＝ dG1(v1)+dG2(v2)≤ n1-1+n2-1≤ n-2
这与 (15.1)矛盾，所以 G必为连通图。
定理 15.7
下面证 G中存在哈密顿通路。
设 Г＝ v1v2… vl为 G中用,扩大路径法,得到的,极大路径,,
即 Г的始点 v1与终点 vl不与 Г外的顶点相邻。显然有 l≤ n。
(1)若 l＝ n,则 Г为 G中哈密顿通路。
(2)若 l＜ n,这说明 Г不是哈密顿通路，
即 G中还存在着 Г外的顶点。
但可以证明 G中存在经过 Г上所有顶点的圈 。
(a) 若 v1与 vl相邻，即 (v1,vl)∈ E(G)，
则 Г∪( v1,vl)为满足要求的圈。
定理 15.7
(b)若 v1与 vl不相邻，设 v1与 Г上的 vi1＝ v2,vi2,…,vik相邻 (k≥2)
(否则 d(v1)+d(vl)≤1+ l-2=l-1<n-1,这与 (15.1)矛盾 )
此时,vl至少与 vi2,…,vik相邻的顶点 vi2-1,…,vik-1之一相邻
(否则 d(v1)+d(vl)≤ k+l-2-(k-1)＝ l-1<n-1)
设 vl与 vir -1相邻（ 2≤ r≤ k）,见下图所示。
于是，回路
C＝ v1v2… vir -1vlvlr -1… vi… virv1
过 Г上的所有顶点。
定理 15.7
(c)下面证明存在比 Г更长的路径。
因为 l<n,所以 C外还有顶点，由 G的连通性可知，
存在 vl+1∈ V(G)-V(C)与 C上某顶点 vt相邻，见下图所示。
删除边 (vt-1,vt)得路径 Г?＝ vt-1… v1vir… vlvir-1… vtvl+1比 Г长度大 1，
对 Г?上的顶点重新排序，使其成为 Г?＝ v1v2… vlvl+1，
对 Г?重复 (a)～ (c),在有限步内一定得到 G的哈密顿通路。
定理 15.7的推论推论 设 G为 n(n≥3) 阶无向简单图，若对于 G中任意两个不相邻的顶点 vi,vj,均有
d(vi)+d(vj)≥ n (15.2)
则 G中存在哈密顿回路，从而 G为哈密顿图。
证明 由定理 15.7可知,G中存在哈密顿通路，
设 Г＝ v1v2… vn为 G中一条哈密顿通路，
若 v1与 vn相邻，设边 e＝ (v1,vn),则 Г∪{ e}为 G中哈密顿回路。
若 v1与 vn不相邻，应用 (15.2)，同定理 15.7证明中的 (2)类似，可证明存在过 Г上各顶点的圈，
此圈即为 G中的哈密顿回路。
定理 15.8
定理 15.8 设 u,v为 n阶无向图 G中两个不相邻的顶点，且
d(u)+d(v)≥ n,则 G为哈密顿图当且仅当 G∪( u,v)为哈密顿图 ((u,v)是加的新边 )。
证明 (略 )。
例 15.5
例 15.5 在某次国际会议的预备会议中,共有 8人参加,他们来自不同的国家 。 已知他们中任何两个无共同语言的人中的每一个,与其余有共同语言的人数之和大于或等于 8,问能否将这 8个人排在圆桌旁,使其任何人都能与两边的人交谈 。
解答 设 8个人分别为 v1,v2,…,v8,作无向简单图 G＝ <V,E>，
其中 V＝ {v1,v2,…,v8},?vi,vj∈ V,且 i≠ j，
若 vi与 vj有共同语言，就在 vi,vj之间连无向边 (vi,vj)，
由此组成边集合 E,则 G为 8阶无向简单图，
vi∈ V,d(vi)为与 vi有共同语言的人数。
由已知条件可知,?vi,vj∈ V且 i≠ j,均有 d(vi)+d(vj)≥8 。
由定理 15.7的推论可知,G中存在哈密顿回路，
设 C＝ vi1vi2… vi8为 G中一条哈密顿回路，
按这条回路的顺序安排座次即可。
哈密顿图是能将图中所有顶点都能安排在某个初级回路上的图。
定理 15.9
定理 15.9 若 D为 n(n≥ 2)阶竞赛图,则 D中具有哈密顿通路 。
证明 对 n作归纳法。
n＝ 2时,D的基图为 K2,结论成立。
设 n＝ k时结论成立。现在设 n＝ k+1。
设 V(D)＝ {v1,v2,…,vk,vk+1}。
令 D1＝ D-vk+1,易知 D1为 k阶竞赛图，
由归纳假设可知,D1存在哈密顿通路，
设 Г1＝ v?1v?2… v?k为其中一条。
定理 15.9
下面证明 vk+1可扩到 Г1中去。
若存在 v?r(1≤ r≤ k),有 <v?i,vk+1>∈ E(D),i＝ 1,2,…,r -1，
而 <vk+1,v?r>∈ E(D),见左图所示，
则 Г＝ v?1v?2… v?r-1vk+1v?r… v?k为 D中哈密顿通路。
否则?i∈{1,2,…,k},均有 <v?i,vk+1>∈ E(D),见右图所示，
则 Г＝ Г?∪< v?i,vk+1>为 D中哈密顿通路。
例 15.6
下图所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？
(1)存在哈密顿回路，所以 (1)为哈密顿图。
(2)取 V1＝ {a,b,c,d,e},从图中删除 V1得 7个连通分支，
由定理 15.6和推论可知，不是哈密顿图，也不是半哈密顿图。
(3)取 V1＝ {b,e,h},从图中删除 V1得 4个连通分支，由定理 15.6可知，它不是哈密顿图。但存在哈密顿通路，所以是半哈密顿图。
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>。
)E(G'e W (e)
)E(G'e W (e)
设 GG,称 W(e)为 G?的权，并记作 W(G?)，
即 W(G?)＝
带权图应用的领域是相当广泛的，许多图论算法都是针对带权图的。
货郎担问题
设有 n个城市，城市之间均有道路，道路的长度均大于或等于
0，可能是 ∞ （对应关联的城市之间无交通线）。一个旅行商从某个城市出发，要 经过每个城市一次且仅一次,最后回到出发的城市，问他如何走才能使他 走的路线最短？
这就是著名的 旅行商问题 或 货郎担问题 。
这个问题可化归为如下的图论问题。
设 G＝ <V,E,W>,为一个 n阶完全带权图 Kn,各边的权非负，
且有的边的权可能为 ∞ 。 求 G中一条最短的哈密顿回路,这就是货郎担问题的数学模型。
此问题中不同哈密顿回路的含义：
将图中生成圈看成一个哈密顿回路，即不考虑始点 (终点 )的区别以及顺时针行遍与逆时针行遍的区别。
例 15.7
例 15.7 下图为 4阶完全带权图 K4。 求出它的不同的哈密顿回路，并指出最短的哈密顿回路。
解答 由于货郎担问题中不同哈密顿回路的含义可知，求哈密顿回路从任何顶点出发都可以。下面先求出从 a点出发，考虑顺时针与逆时针顺序的不同的哈密顿回路。
C1＝ abcda C2＝ abdca C3＝ acbda
C4＝ acdba C5＝ adbca C6＝ adcba
带权图的说明
n阶完全带权图中共存在 (n-1)!/2种不同的哈密顿回路，经过比较，可找出最短哈密顿回路。
n＝ 4时,有 3种不同哈密顿回路。
n＝ 5时,有 12种，
n＝ 6时,有 60种，
n＝ 7时,有 360种,…,
n＝ 10时，有 5× 9!=1 814 400种,… 。
由此可见货郎担问题的计算量是相当大的。
对于货郎担问题，人们一方面还在寻找好的算法，另一方面也在寻找各种近似算法。
中国邮递员问题
一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局。如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程。
这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在 1960年首次提出的，因此在国际上称之为中国邮递员问题。
用图论的述语，在一个连通的赋权图 G(V,E)中，要寻找一条回路，使该回路包含 G中的每条边至少一次，且该回路的权数最小。也就是说要从包含 G的每条边的回路中找一条权数最小的回路。
基本要求
深刻理解欧拉图与半欧拉图的定义及判别定理。
会用 Fleury算法求出欧拉图中的欧拉回路。
深刻理解哈密顿图及半哈密顿图的定义。
会用破坏哈密顿图应满足的某些必要条件的方法判断某些图不是哈密顿图。
会用满足哈密顿图的充分条件的方法判断某些图是哈密顿图。
严格地分清哈密顿图必要条件和充分条件，千万不能将必要条件当充分条件，同样地，也不能将充分条件当成必要条件。
作业习题十五 2,11,14,15,20
归纳法证明示意图例 15.4
例 15.4 设 G是 n阶无向连通图。证明：若 G中有割点或桥，则 G不是哈密顿图。
证明 (1)证明 若 G中有割点，则 G不是哈密顿图。
设 v为连通图 G中一个割点，则 V?＝ {v}为 G中的点割集，而
p(G-V?)≥2 ＞ 1＝ |V?|
由定理 15.6可知 G不是哈密顿图。
(2)证明 若 G中有桥，则 G不是哈密顿图。
设 G中有桥,e＝ (u,v)为其中的一个桥。
若 u,v都是悬挂边，则 G为 K2,K2不是哈密顿图。
若 u,v中至少有一个，比如 u,d(u)≥2,由于 e与 u关联,e为桥
，所以 G-u至少产生两个连通分支，于是 u为 G中割点。
由 (1)的讨论可知,G不是哈密顿图。
15.1 欧拉图
15.2 哈密顿图
15.3 带权图与货郎担问题基本要求作业
15.1 欧拉图
历史背景－－哥尼斯堡七桥问题
欧拉图是一笔画出的边不重复的回路 。
欧拉图定义 15.1 通过图（无向图或有向图）中 所有边一次且仅一次行遍图中所有顶点的通路称为 欧拉通路,通过图中所有边一次并且仅一次行遍所有顶点的 回路 称为 欧拉回路 。具有欧拉回路的图称为 欧拉图,具有欧拉通路而无欧拉回路的图称为 半欧拉图 。
说明 欧拉通路是图中经过所有边的简单的生成通路 (经过所有顶点的通路称为生成通路 )。
欧拉回路是经过所有边的简单的生成回路。
举例欧拉图 半欧拉图 无欧拉通路欧拉图 无欧拉通路 无欧拉通路无向欧拉图的判定定理定理 15.1 无向图 G是欧拉图当且仅当 G是连通图，且 G中没有奇度顶点。
证明 若 G是平凡图，结论显然成立。
下面设 G为非平凡图，设 G是 m条边的 n阶无向图，
并设 G的顶点集 V＝ {v1,v2,…,vn}。
必要性 。因为 G为欧拉图，所以 G中存在欧拉回路，
设 C为 G中任意一条欧拉回路,?vi,vj∈ V,vi,vj都在 C上，
因而 vi,vj连通，所以 G为连通图。
又?vi∈ V,vi在 C上每出现一次获得 2度，
若出现 k次就获得 2k度，即 d(vi)＝ 2k，
所以 G中无奇度顶点。
定理 15.1的证明充分性 。由于 G为非平凡的连通图可知,G中边数 m≥1 。
对 m作归纳法。
(1)m＝ 1时，由 G的连通性及无奇度顶点可知，
G只能是一个环，因而 G为欧拉图。
(2)设 m≤ k(k≥1) 时结论成立，要证明 m＝ k+1时，结论也成立。
由 G的连通性及无奇度顶点可知,δ( G)≥2 。
无论 G是否为简单图，都可以用扩大路径法证明 G中必含圈。
定理 15.1的证明设 C为 G中一个圈，删除 C上的全部边，得 G的生成子图 G?，
设 G?有 s个连通分支 G?1,G?2,…,G?s，
每个连通分支至多有 k条边，且无奇度顶点，
并且设 G?i与 C的公共顶点为 v*ji,i＝ 1,2,…,s，
由归纳假设可知,G?1,G?2,…,G?s都是欧拉图，
因而都存在欧拉回路 C?i,i＝ 1,2,…,s。
最后将 C还原（ 即将删除的边重新加上 ），
并从 C上的某顶点 vr开始行遍，每遇到 v*ji,就行遍 G?i中的欧拉回路 C?i,i＝ 1,2,…,s,最后回到 vr，
得回路 vr… v*j1… v*j1… v*j2… v*j2… v*js… v*js… vr，
此回路经过 G中每条边一次且仅一次并行遍 G中所有顶点，
因而它是 G中的欧拉回路（ 演示这条欧拉回路 ），
故 G为欧拉图。
定理 15.2 无向图 G是半欧拉图当且仅当 G是连通的，且 G中恰有两个奇度顶点。
证明 必要性 。设 G是 m条边的 n阶无向图，因为 G为半欧拉图，
因而 G中存在欧拉通路 (但不存在欧拉回路 )，
设 Г ＝ vi0ej1vi1… vim-1ejmvim为 G中一条欧拉通路,vi0≠ vim。
v∈ V(G),若 v不在 Г 的端点出现，显然 d(v)为偶数，
若 v在端点出现过，则 d(v)为奇数，
因为 Г 只有两个端点且不同，因而 G中只有两个奇数顶点。
另外,G的连通性是显然的。
半欧拉图的判定定理定理 15.2 无向图 G是半欧拉图当且仅当 G是连通的，且 G中恰有两个奇度顶点。
证明 充分性 。设 G的两个奇度顶点分别为 u0和 v0，
对 G加新边（ u0,v0）,得 G?＝ G∪( u0,v0)，
则 G?是连通且无奇度顶点的图，
由定理 15.1可知,G?为欧拉图，
因而存在欧拉回路 C?,而 C＝ C?-(u0,v0)为 G中一条欧拉通路，
所以 G为半欧拉图。
半欧拉图的判定定理有向欧拉图的判定定理定理 15.3 有向图 D是欧拉图当且仅当 D是强连通的且每个顶点的入度都等于出度。
定理 15.4 有向图 D是半欧拉图当且仅当 D是单向连通的，且 D中恰有两个奇度顶点，其中一个的入度比出度大 1，另一个的出度比入度大 1，而其余顶点的入度都等于出度。 (举例 )
定理 15.5 G是非平凡的欧拉图当且仅当 G是连通的且为若干个边不重的圈的并。
例 15.1
例 15.1 设 G是非平凡的且非环的欧拉图，证明：
(1)λ( G)≥2 。
(2)对于 G中任意两个不同顶点 u,v,都存在简单回路 C含 u和 v。
证明 (1)由定理 15.5可知,?e∈ E(G),存在圈 C,e在 C中，
因而 p(G-e)＝ p(G),故 e不是桥。
由 e的任意性 λ( G)≥2,即 G是 2边 -连通图。
(2)?u,v∈ V(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形成的简单回路上。
求欧拉图中欧拉回路的算法
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)
为 G中一条欧拉回路。
Fleury算法示例例 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,但当时除桥外他无别的边可走，所以当时均走了桥，这是不会犯错误的。
15.2 哈密顿图
历史背景：哈密顿周游世界问题与哈密顿图哈密顿图定义 15.2 经过图（有向图或无向图）中 所有顶点一次且仅一次的通路 称为 哈密顿通路 。经过图中 所有顶点一次且仅一次的回路 称为 哈密顿回路 。具有哈密顿回路的图称为 哈密顿图,具有哈密顿通路但不具有哈密顿回路的图称为 半哈密顿图 。平凡图是哈密顿图。
说明 哈密顿通路是图中生成的初级通路，
哈密顿回路是生成的初级回路。
判断一个图是否为哈密顿图，就是判断能否将图中所有顶点都放置在一个初级回路 (圈 )上，但这不是一件易事。
与判断一个图是否为欧拉图不一样，到目前为止，人们还没有找到哈密顿图简单的充分必要条件。
例题
(1)(2)是哈密顿图。
(3)是半哈密顿图。
(4)既不是哈密顿图，也不是半哈密顿图。
定理 15.6
定理 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|。
说明 本定理的条件是哈密顿图的必要条件，但不是充分条件。
可以验证彼得松图满足定理中的条件，但不是哈密顿图。
若一个图不满足定理中的条件，它一定不是哈密顿图。
推论推论 设无向图 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
例 15.3
例 15.3 在下图中给出的三个图都是二部图。它们中的哪些是哈密顿图？哪些是半哈密顿图？为什么？
易知互补顶点子集
V1＝ {a,f}
V2＝ {b,c,d,e}
设此二部图为 G1,则 G1＝ <V1,V2,E>。
p(G1-V1)＝ 4>|V1|＝ 2，
由定理 15.6及其推论可知,G1不是哈密顿图，也不是半哈密顿图。
例 15.3
设图为 G2,则 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中一条哈密顿通路。
设图为 G3。 G3＝ <V1,V2,E>,其中
V1＝ {a,c,g,h,e},V2＝ {b,d,i,j,f}，
G3中存在哈密顿回路。
如 abcdgihjefa，
所以 G3是哈密顿图。
例 15.3的说明
哈密顿通路是经过图中所有顶点的一条初级通路。
哈密顿回路是经过图中所有顶点的初级回路。
对于二部图还能得出下面结论：
一般情况下，设二部图 G＝ <V1,V2,E>,|V1|≤| V2|,且 |V1|≥2
,|V2|≥2,由定理 15.6及其推论可以得出下面结论：
(1) 若 G是哈密顿图，则 |V1|＝ |V2|。
(2) 若 G是半哈密顿图，则 |V2|＝ |V1|+1。
(3) 若 |V2|≥| V1|+2,则 G不是哈密顿图，也不是半哈密顿图。
例 15.4 设 G是 n阶无向连通图。证明,若 G中有割点或桥，则 G不是哈密顿图。
证明 可用定理 15.6证明。
定理 15.7
定理 15.7 设 G是 n阶无向简单图，若对于 G中任意不相邻的顶点 vi,vj,均有
d(vi)+d(vj)≥ n-1 (15.1)
则 G中存在哈密顿通路。
证明 首先证明 G是连通图。
否则 G至少有两个连通分支，
设 G1,G2是阶数为 n1,n2的两个连通分支，
设 v1∈ V(G1),v2∈ V(G2),因为 G是简单图，所以
dG(v1)+dG(v2)＝ dG1(v1)+dG2(v2)≤ n1-1+n2-1≤ n-2
这与 (15.1)矛盾，所以 G必为连通图。
定理 15.7
下面证 G中存在哈密顿通路。
设 Г＝ v1v2… vl为 G中用,扩大路径法,得到的,极大路径,,
即 Г的始点 v1与终点 vl不与 Г外的顶点相邻。显然有 l≤ n。
(1)若 l＝ n,则 Г为 G中哈密顿通路。
(2)若 l＜ n,这说明 Г不是哈密顿通路，
即 G中还存在着 Г外的顶点。
但可以证明 G中存在经过 Г上所有顶点的圈 。
(a) 若 v1与 vl相邻，即 (v1,vl)∈ E(G)，
则 Г∪( v1,vl)为满足要求的圈。
定理 15.7
(b)若 v1与 vl不相邻，设 v1与 Г上的 vi1＝ v2,vi2,…,vik相邻 (k≥2)
(否则 d(v1)+d(vl)≤1+ l-2=l-1<n-1,这与 (15.1)矛盾 )
此时,vl至少与 vi2,…,vik相邻的顶点 vi2-1,…,vik-1之一相邻
(否则 d(v1)+d(vl)≤ k+l-2-(k-1)＝ l-1<n-1)
设 vl与 vir -1相邻（ 2≤ r≤ k）,见下图所示。
于是，回路
C＝ v1v2… vir -1vlvlr -1… vi… virv1
过 Г上的所有顶点。
定理 15.7
(c)下面证明存在比 Г更长的路径。
因为 l<n,所以 C外还有顶点，由 G的连通性可知，
存在 vl+1∈ V(G)-V(C)与 C上某顶点 vt相邻，见下图所示。
删除边 (vt-1,vt)得路径 Г?＝ vt-1… v1vir… vlvir-1… vtvl+1比 Г长度大 1，
对 Г?上的顶点重新排序，使其成为 Г?＝ v1v2… vlvl+1，
对 Г?重复 (a)～ (c),在有限步内一定得到 G的哈密顿通路。
定理 15.7的推论推论 设 G为 n(n≥3) 阶无向简单图，若对于 G中任意两个不相邻的顶点 vi,vj,均有
d(vi)+d(vj)≥ n (15.2)
则 G中存在哈密顿回路，从而 G为哈密顿图。
证明 由定理 15.7可知,G中存在哈密顿通路，
设 Г＝ v1v2… vn为 G中一条哈密顿通路，
若 v1与 vn相邻，设边 e＝ (v1,vn),则 Г∪{ e}为 G中哈密顿回路。
若 v1与 vn不相邻，应用 (15.2)，同定理 15.7证明中的 (2)类似，可证明存在过 Г上各顶点的圈，
此圈即为 G中的哈密顿回路。
定理 15.8
定理 15.8 设 u,v为 n阶无向图 G中两个不相邻的顶点，且
d(u)+d(v)≥ n,则 G为哈密顿图当且仅当 G∪( u,v)为哈密顿图 ((u,v)是加的新边 )。
证明 (略 )。
例 15.5
例 15.5 在某次国际会议的预备会议中,共有 8人参加,他们来自不同的国家 。 已知他们中任何两个无共同语言的人中的每一个,与其余有共同语言的人数之和大于或等于 8,问能否将这 8个人排在圆桌旁,使其任何人都能与两边的人交谈 。
解答 设 8个人分别为 v1,v2,…,v8,作无向简单图 G＝ <V,E>，
其中 V＝ {v1,v2,…,v8},?vi,vj∈ V,且 i≠ j，
若 vi与 vj有共同语言，就在 vi,vj之间连无向边 (vi,vj)，
由此组成边集合 E,则 G为 8阶无向简单图，
vi∈ V,d(vi)为与 vi有共同语言的人数。
由已知条件可知,?vi,vj∈ V且 i≠ j,均有 d(vi)+d(vj)≥8 。
由定理 15.7的推论可知,G中存在哈密顿回路，
设 C＝ vi1vi2… vi8为 G中一条哈密顿回路，
按这条回路的顺序安排座次即可。
哈密顿图是能将图中所有顶点都能安排在某个初级回路上的图。
定理 15.9
定理 15.9 若 D为 n(n≥ 2)阶竞赛图,则 D中具有哈密顿通路 。
证明 对 n作归纳法。
n＝ 2时,D的基图为 K2,结论成立。
设 n＝ k时结论成立。现在设 n＝ k+1。
设 V(D)＝ {v1,v2,…,vk,vk+1}。
令 D1＝ D-vk+1,易知 D1为 k阶竞赛图，
由归纳假设可知,D1存在哈密顿通路，
设 Г1＝ v?1v?2… v?k为其中一条。
定理 15.9
下面证明 vk+1可扩到 Г1中去。
若存在 v?r(1≤ r≤ k),有 <v?i,vk+1>∈ E(D),i＝ 1,2,…,r -1，
而 <vk+1,v?r>∈ E(D),见左图所示，
则 Г＝ v?1v?2… v?r-1vk+1v?r… v?k为 D中哈密顿通路。
否则?i∈{1,2,…,k},均有 <v?i,vk+1>∈ E(D),见右图所示，
则 Г＝ Г?∪< v?i,vk+1>为 D中哈密顿通路。
例 15.6
下图所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？
(1)存在哈密顿回路，所以 (1)为哈密顿图。
(2)取 V1＝ {a,b,c,d,e},从图中删除 V1得 7个连通分支，
由定理 15.6和推论可知，不是哈密顿图，也不是半哈密顿图。
(3)取 V1＝ {b,e,h},从图中删除 V1得 4个连通分支，由定理 15.6可知，它不是哈密顿图。但存在哈密顿通路，所以是半哈密顿图。
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>。
)E(G'e W (e)
)E(G'e W (e)
设 GG,称 W(e)为 G?的权，并记作 W(G?)，
即 W(G?)＝
带权图应用的领域是相当广泛的，许多图论算法都是针对带权图的。
货郎担问题
设有 n个城市，城市之间均有道路，道路的长度均大于或等于
0，可能是 ∞ （对应关联的城市之间无交通线）。一个旅行商从某个城市出发，要 经过每个城市一次且仅一次,最后回到出发的城市，问他如何走才能使他 走的路线最短？
这就是著名的 旅行商问题 或 货郎担问题 。
这个问题可化归为如下的图论问题。
设 G＝ <V,E,W>,为一个 n阶完全带权图 Kn,各边的权非负，
且有的边的权可能为 ∞ 。 求 G中一条最短的哈密顿回路,这就是货郎担问题的数学模型。
此问题中不同哈密顿回路的含义：
将图中生成圈看成一个哈密顿回路，即不考虑始点 (终点 )的区别以及顺时针行遍与逆时针行遍的区别。
例 15.7
例 15.7 下图为 4阶完全带权图 K4。 求出它的不同的哈密顿回路，并指出最短的哈密顿回路。
解答 由于货郎担问题中不同哈密顿回路的含义可知，求哈密顿回路从任何顶点出发都可以。下面先求出从 a点出发，考虑顺时针与逆时针顺序的不同的哈密顿回路。
C1＝ abcda C2＝ abdca C3＝ acbda
C4＝ acdba C5＝ adbca C6＝ adcba
带权图的说明
n阶完全带权图中共存在 (n-1)!/2种不同的哈密顿回路，经过比较，可找出最短哈密顿回路。
n＝ 4时,有 3种不同哈密顿回路。
n＝ 5时,有 12种，
n＝ 6时,有 60种，
n＝ 7时,有 360种,…,
n＝ 10时，有 5× 9!=1 814 400种,… 。
由此可见货郎担问题的计算量是相当大的。
对于货郎担问题，人们一方面还在寻找好的算法，另一方面也在寻找各种近似算法。
中国邮递员问题
一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局。如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程。
这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在 1960年首次提出的，因此在国际上称之为中国邮递员问题。
用图论的述语，在一个连通的赋权图 G(V,E)中，要寻找一条回路，使该回路包含 G中的每条边至少一次，且该回路的权数最小。也就是说要从包含 G的每条边的回路中找一条权数最小的回路。
基本要求
深刻理解欧拉图与半欧拉图的定义及判别定理。
会用 Fleury算法求出欧拉图中的欧拉回路。
深刻理解哈密顿图及半哈密顿图的定义。
会用破坏哈密顿图应满足的某些必要条件的方法判断某些图不是哈密顿图。
会用满足哈密顿图的充分条件的方法判断某些图是哈密顿图。
严格地分清哈密顿图必要条件和充分条件，千万不能将必要条件当充分条件，同样地，也不能将充分条件当成必要条件。
作业习题十五 2,11,14,15,20
归纳法证明示意图例 15.4
例 15.4 设 G是 n阶无向连通图。证明：若 G中有割点或桥，则 G不是哈密顿图。
证明 (1)证明 若 G中有割点，则 G不是哈密顿图。
设 v为连通图 G中一个割点，则 V?＝ {v}为 G中的点割集，而
p(G-V?)≥2 ＞ 1＝ |V?|
由定理 15.6可知 G不是哈密顿图。
(2)证明 若 G中有桥，则 G不是哈密顿图。
设 G中有桥,e＝ (u,v)为其中的一个桥。
若 u,v都是悬挂边，则 G为 K2,K2不是哈密顿图。
若 u,v中至少有一个，比如 u,d(u)≥2,由于 e与 u关联,e为桥
，所以 G-u至少产生两个连通分支，于是 u为 G中割点。
由 (1)的讨论可知,G不是哈密顿图。
