第十五章 欧拉图与哈密顿图 主要内容 欧拉图 哈密顿图 带权图与货郎担问题

15.1 欧拉图 历史背景：哥尼斯堡七桥问题与欧拉图

欧拉图定义 定义15.1 (1) 欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路. (2) 欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路. (3) 欧拉图——具有欧拉回路的图. (4) 半欧拉图——具有欧拉通路而无欧拉回路的图. 几点说明： 规定平凡图为欧拉图. 欧拉通路是生成的简单通路，欧拉回路是生成的简单回路. 环不影响图的欧拉性.

欧拉图实例 上图中，(1) ,(4) 为欧拉图，(2),(5)为半欧拉图，(3),(6)既不是欧拉图，也不是半欧拉图. 在(3),(6)中各至少加几条边才能成为欧拉图？

无向欧拉图的判别法 定理15.1 无向图G是欧拉图当且仅当G连通且无奇度数顶点. 证 若G 为平凡图无问题. 下设G为 n 阶 m 条边的无向图. 必要性 设C 为G 中一条欧拉回路. (1) G 连通显然. (2) viV(G)，vi在C上每出现一次获2度，所以vi为偶度顶点. 由vi 的任意性，结论为真. 充分性 对边数m做归纳法（第二数学归纳法）. (1) m=1时，G为一个环，则G为欧拉图. (2) 设mk（k1）时结论为真，m=k+1时如下证明：

从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图3. PLAY

欧拉图的判别法 定理15.2 无向图G是半欧拉图当且仅当G 连通且恰有两个奇 度顶点. 证 必要性简单. 充分性（利用定理15.1） 证 必要性简单. 充分性（利用定理15.1） 设u,v为G 中的两个奇度顶点，令 G  =G(u,v) 则G  连通且无奇度顶点，由定理15.1知G 为欧拉图，因而 存在欧拉回路C，令 =C(u,v) 则 为 G 中欧拉通路.

有向欧拉图的判别法 定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶 点的入度都等于出度. 本定理的证明类似于定理15.1. 的出度比入度大1，而其余顶点的入度都等于出度. 定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干 个边不重的圈之并. 可用归纳法证定理15.5.

例题 例1 设G是欧拉图，但G不是平凡图，也不是一个环，则 (G)2. 证 只需证明G中不可能有桥（如何证明？） (1) (2) (1) (2) 上图中，(1),(2)两图都是欧拉图，均从A点出发，如何一次成功地走出一条欧拉回路来？

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算法走出上一页图(1),(2)从A出发（其实从任何一点 出发都可以）的欧拉回路各一条.

15.2 哈密顿图 历史背景：哈密顿周游世界问题与哈密顿图 (1) (2)

哈密顿图与半哈密顿图 定义15.2 (1) 哈密顿通路——经过图中所有顶点一次仅一次的通路. (2) 哈密顿回路——经过图中所有顶点一次仅一次的回路. (3) 哈密顿图——具有哈密顿回路的图. (4) 半哈密顿图——具有哈密顿通路且无哈密顿回路的图. 几点说明： 平凡图是哈密顿图. 哈密顿通路是初级通路，哈密顿回路是初级回路. 环与平行边不影响哈密顿性. 哈密顿图的实质是能将图中的所有顶点排在同一个圈上

实例 在上图中， (1),(2) 是哈密顿图; (3)是半哈密顿图; (4)既不是哈密顿图，也不是半哈密顿图，为什么？

无向哈密顿图的一个必要条件 定理15.6 设无向图G=<V,E>是哈密顿图，对于任意V1V且 V1，均有 p(GV1)  |V1| 证 设C为G中一条哈密顿回路 (1) p(CV1)  |V1| (2) p(GV1)  p(CV1)  |V1| （因为CG） 推论 设无向图G=<V,E>是半哈密顿图，对于任意的V1V且V1均有 p(GV1)  |V1|+1 证 令 uv为G中哈密顿通路，令G = G(u,v)，则G为哈密顿图. 于是 p(GV1) = p(GV1(u,v))  |V1|+1

几点说明 定理15.6中的条件是哈密顿图的必要条件，但不是充分条件（彼得松图） 由定理15.6立刻可知，Kr,s当sr+1时不是哈密顿图. 易知Kr,r（r2）时都是哈密顿图，Kr,r+1都是半哈密顿图. 常利用定理15.6判断某些图不是哈密顿图. 例2 设G为n阶无向连通简单图，若G中有割点或桥，则G不 是哈密顿图. 证 设v为割点，则 p(Gv)  2>|{v}|=1. K2有桥，它显然不是哈密顿图. 除K2外，其他有桥的图（连通的）均有割点. 其实，本例对非简单连通图也对.

无向哈密顿图的一个充分条件 定理15.7 设G是n阶无向简单图，若对于任意不相邻的顶点vi,vj，均有 d(vi)+d(vj)  n1 () 则G 中存在哈密顿通路. 证明线索： (1) 由()证G连通 (2)  = v1v2…vl 为G中极大路径. 若l = n, 证毕. (3) 否则，证G 中存在过上所有顶点的圈C，由(1) 知C外顶 点存在与C上某顶点相邻顶点，从而得比更长的路径，重 复(2) –(3) ，最后得G中哈密顿通路.

证明 证（着重关键步骤） (1) 由()及简单图的性质，用反证法证明G连通. (2)  = v1v2…vl 为极大路径，l  n, 若l = n（结束）. 下面讨论l<n的情况，即要证G中存在过上所有顶点的圈. ① 若(v1,vl)在G中，则(u,v)为G中圈 ② 否则，设v1与上 相邻，则k2 (否则由极大路径端点性质及()，会得到d(v1)+d(vl)1+l2<n1)， 又vl 至少与 左边相邻顶点之一相邻(写出理由)，设 与vl相邻，见图中(1) ，于是得G中回路C ((1)中图去掉边( ) )

证明 图(1) 图(2) (3) 由连通性，可得比 更长的路径（如图(2) 所示）， 对它再扩大路径，重复(2) ，最后得哈密顿通路.

推论 推论 设G为n (n3) 阶无向简单图，若对于G中任意两个 不相邻的顶点vi,vj，均有 d(vi)+d(vj)  n （） 则G中存在哈密顿回路，从而G为哈密顿图. 证明线索：由定理15.7得 = v1v2…vn 为G中哈密顿通路. 若(v1,vn)E(G)，得证. 否则利用（）证明存在过v1, v2, …, vn的圈(哈密顿回路). 定理15.8 设u,v为n阶无向简单图G中两个不相邻的顶点，且d(u)+d(v)n，则G为哈密顿图当且仅当G(u,v)为哈密顿图.

几点说明 定理15.7是半哈密顿图的充分条件，但不是必要条件. 长度 为n1（n4）的路径构成的图不满足（）条件，但它显 然是半哈密顿图. 定理15.7的推论同样不是哈密顿图的必要条件，G为长为n的 圈，不满足（）条件，但它当然是哈密顿图. 由定理15.7的推论可知，Kn（n3）均为哈密顿图.

无向哈密顿图的充分条件 n（n2）阶竞赛图中存在哈密顿通路 定理15.9 若D为n（n2）阶竞赛图，则D中具有哈密顿通路 做归纳. 只需观察下面两个图.

判断某图是否为哈密顿图方法 判断某图是否为哈密顿图至今还是一个难题. 总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法. 1. 观察出哈密顿回路. 例3 下图(周游世界问题) 是哈密顿图 易知 a b c d e f g h i j k l m n p q r s t a 为图中的一条哈密顿回路. 注意，此图不满足定理15.7 推论条件.

判断某图是否为哈密顿图方法 2．满足定理15.7推论的条件（）. 例4 完全图Kn (n3) 中任何两个顶点u,v，均有 d(u)+d(v) = 2(n1)  n（n3）， 所以Kn为哈密顿图. 3．破坏定理15.6的条件的图不是哈密顿图. 例5 在四分之一国际象棋盘（44方格组成）上跳马无解. 在国际象棋盘上跳马有解.

令V1={a, b, c, d}, 则 p(GV1) = 6 >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>. 设GG，称 为G的权，并记作W(G)，即

货郎担问题 设G=<V,E,W>为一个n阶完全带权图Kn，各边的权非负，且 是货郎担问题的数学模型. 完全带权图Kn（n3）中不同的哈密顿回路数 (1) Kn中有n! 条不同的哈密顿回路（定义意义下） (2) 完全带权图中有n! 条不同的哈密顿回路 (3) 用穷举法解货郎担问题算法的复杂度为n！，当n较大时，计算量惊人地大

例6 求图中(1) 所示带权图K4中最短哈密顿回路. (1) (2) 解 C1= a b c d a, W(C1)=10 C2= a b d c a, W(C2)=11 C3= a c b d a, W(C3)=9 可见C3 (见图中(2)) 是最短的，其权为9.

第十五章 习题课 主要内容 欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法 哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图 带权图、货郎担问题 基本要求 深刻理解欧拉图、半欧拉图的定义及判别定理 深刻理解哈密顿图、半哈密顿图的定义. 会用哈密顿图的必要条件判断某些图不是哈密顿图. 会用充分条件判断某些图是哈密顿图. 要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件.

练习1 1. 设G为n（n2）阶无向欧拉图，证明G中无桥(见例1思考题) 方法一：直接证明法. 命题 (*)：设C为任意简单回路，e为C上任意一条边，则Ce连通. 证 设C为G中一条欧拉回路，任意的eE(C)，可知Ce是Ge的子图，由()知 Ce 连通，所以e不为桥. 方法二：反证法. 利用欧拉图无奇度顶点及握手定理的推论. 否则，设e=(u,v)为G中桥，则Ge产生两个连通分支G1, G2，不妨设u在G1中，v在G2中. 由于从G中删除e时，只改变u,v 的度数(各减1)，因而G1与G2中均只含一个奇度顶点，这与握手定理推论矛盾.

练习 2 2. 证明下图不是哈密顿图. (破坏必要条件) 方法一. 利用定理15.6， 方法一. 利用定理15.6， 取 V1 = {a, c, e, h, j, l}，则 p(GV1) = 7 > |V1| = 6 方法二. G为二部图，互补顶点子集 V1 = {a, c, e, h, j, l}, V2 = {b, d, f, g, i, k, m}， |V1| = 6  7 = |V2|. 方法三. 利用可能出现在哈密顿回路上的边至少有n(n为阶数) 条——这也是哈密顿图的一个必要条件，记为（）. 此图中，n = 13，m = 21. 由于h, l, j 均为4度顶点，a, c, e为3 度顶点，且它们关联边互不相同. 而在哈密顿回路上， 每个顶点准确地关联两条边，于是可能用的边至多有21(32+31) = 12. 这达不到（）的要求.

练习 3 3．某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？ 解 图是描述事物之间关系的最好的手段之一. 做无向图G=<V,E>, 其中 V={v| v为与会者}， E={(u,v) | u,vV且u与v有共同语言，且u  v}. 易知G为简单图且vV, d(v)4，于是，u,vV, 有d(u)+d(v)  8，由定理15.7 的推论可知G为哈密顿图. 服务员在G中找一条哈密顿回路C，按C中相邻关系安排座位即可. 由本题想到的：哈密顿回图的实质是能将图中所有的顶点排在同一个圈中.

练习 4 4. 距离(公里) 如图所示. 他如何走行程最短？ 最短的路为ABCDA，距离为36公里，其余两条各为多少？