欧拉图与哈密顿图

欧拉通路、欧拉回路、欧拉图、半欧拉图的定义

定义15.1 通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路, 通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路. 具有欧拉回路的图称为欧拉图, 具有欧拉通路而无欧拉回路的图称为半欧拉图.

从定义不难看出, 欧拉通路是图中经过所有边的简单的生成通路（经过所有顶点的通路称为生成通路）, 类似地, 欧拉回路是经过所有边的简单的生成回路.

在这里做个规定, 即平凡图是欧拉图.

图15.1

在图15.1所示各图中, e1e2e3e4e5为（1）中的欧拉回路, 所以（1）图为欧拉图. e1e2e3e4e5为（2）中的一条欧拉通路, 但图中不存在欧拉回路（为什么？）, 所以（2）为半欧拉图. （3）中既没有欧拉回路, 也没有欧拉通路（为什么？），所以（3）不是欧拉图, 也不是半欧拉图. e1e2e3e4为（4）图中的欧拉回路, 所以（4）图为欧拉图. （5）,（6）图中都既没有欧拉回路, 也没有欧拉通路（为什么？）

判别定理

定理15.1 无向图G是欧拉图当且仅当G是连通图, 且G中没有奇度顶点.

证 若G是平凡图, 结论显然成立. 下面设G为非平凡图, 设G是m条边的n阶无向图，并设G的顶点集V={v1,v2,?,vn}.

必要性. 因为G为欧拉图, 所以G中存在欧拉回路, 设C为G中任意一条欧拉回路, vi,vj都在C上, 因而vi,vj连通, 所以G为连通图. 又次就获得2k度, 即d(vi)=2k, 所以G中无奇度顶点.

充分性, 由于G为非平凡的连通图可知, G中边数m≥1.对m作归纳法.

(1)m=1时, 由G的连通性及无奇度顶点可知, G只能是一个环, 因而G为欧拉图.

vi,vj∈V,

vi∈V, vi在C上每出现一次获得2度, 若出现k

(2)设m≤k(k≥1)时结论成立, 要证明m=K+1时, 结论也成立. 由G的连通性及无奇度顶点可知, δ(G)≥2.类似于例14.8, 用扩大路径法可以证明G中存在长度大于或等于3的圈, 设C为G中一个圈, 删除C上的全部边, 得G的生成子图G', 设G'有s个连通分支G'1,G'2,?,G's, 每个连通分支至多有k条边,

且无奇度顶点, 并且设G'i与C的公共顶点为, i=1,2,?,s, 由归纳假设可知, G'1,G'2,?,G's都是欧

拉图, 因而都存在欧拉回路C'i, i=1,2,?,s.最后将C还原（即将删除的边重新加上）, 并从C上的某顶

点vr开始行遍, 每遇到vr?

?

?

?

, 就行遍G'i中的欧拉回路C'i, i=1,2,?,s, 最后回到vr, 得回路

?

?

?vr, 此回路经过G中每条边一次且仅一次并行遍G中所

有顶点, 因而它是G中的欧拉回路 （演示这条欧拉回路）, 故G为欧拉图.

由定理15.1立刻可知, 图15.1中的三个无向图中, 只有（1）中无奇度顶点, 因而（1）是欧拉图, 而（2）、（3）都有奇度顶点, 因而它们都不是欧拉图.

定理15.2 无向图G是半欧拉图当且仅当G是连通的, 且G中恰有两个奇度顶点.

证 必要性. 设G是m条边的n阶无向图, 因为G为半欧拉图, 因而G中存在欧拉通路（但不存在欧拉回路）, 设Г=vi0ej1vi1?vim-1ejmvim为G中一条欧拉通路, vi0 ≠vim .奇数顶点. 另外, G的连通性是显然的.

充分性. 设G的两个奇度顶点分别为u0和v0, 对G加新边（u0,v0）, 得G'=G∪(u0,v0), 则G'是连通且无奇度顶点的图, 由定理15.1可知, G'为欧拉图, 因而存在欧拉回路C', 而C=C'- (u0,v0)为G中一条欧拉通路, 所以G为半欧拉图.

由定理15.2立即可知, 图15.1中（2）是半欧拉图, 但（3）不是半欧拉图. 定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度. 本定理的证明类似于定理15.1 .

定理15.4 有向图D是半欧拉图当且仅当D是单向连通的, 且D中恰有两个奇度顶点, 其中一个的入度比出度大1, 另一个的出度比入度大1, 而其余顶点的入度都等于出度.

v∈V(G), 若v不在Г的端点出现,

显然d(v)为偶数, 若v在端点出现过, 则d(v)为奇数, 因为Г只有两个端点且不同, 因而G中只有两个

本定理的证明留给读者.

由定理15.3和15.4立即可知, 图15.1中所示3个有向图中只有（4）是欧拉图, 没有半欧拉图.

图15.3

由定理15.1立即可知, 图15.3(1)图为欧拉图, 本图既可以看成圈v1v2v8v1, v2v3v4v2, v4v5v6v4, v6v7v8v6

之并（为清晰起见, 将4个圈画在（2）中）, 也可看成圈v1v2v3v4v5v6v7v8v1与圈v2v4v6v8v2之并（两个圈画在（3）中）. 将（1）分解成若干个边不重的圈的并不是（1）图特有的性质, 任何欧拉图都有这个性质.

定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并. 本定理的证明可用归纳法. （见练习题） 例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算法

设G为欧拉图, 一般来说G中存在若干条欧拉回路. 下面介绍求欧拉回路的两种算法中的第一种: Fleury算法.

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中一条欧拉回路. 例15.2 图15.4(1)是给定的欧拉图G. 某人用Fleury算法求G中的欧拉回路时, 走了简单回路v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后(观看他的错误走法), 无法行遍了, 试分析在哪步他犯了错误?

图15.4

解 此人行遍v8时犯了能不走桥就不走桥的错误, 因而他没行遍出欧拉回路. 当他走到v8时, G-{e2,e3,e14,e10,e1,e8}为图15.4(2)所示. 此时e9为该图中的桥, 而e7,e11均不是桥, 他不应该走e9, 而应该走e7或e11, 他没有走, 所以犯了错误. 注意, 此人在行遍中, 在v3遇到过桥e3, v1处遇到过桥e8, 但当时除桥外他无别的边可走, 所以当时均走了桥, 这是不会犯错误的.

求欧拉回路的逐步插入回路法

逐步插入回路法

设G为n阶无向欧拉图, V(G)={v1,v2,?,vn}, 求G中欧拉回路的逐步插入回路法的算法如下： 开始 i←0, v=v1, v=v1, P0=v1, G0=G.

1．在Gi中任取一条与v关联的边e=(v,v'), 将e及v'加入到Pi中得到Pi+1. 2．若v'=v, 转3, 否则i←i+1,v=v', 转1.

3．若E(Pi+1)=E(G), 结束, 否则, 令Gi+1=G-E(Pi+1), 在Gi+1中任取一条与Pi+1中某顶点vk关联的边e, 先将Pi+1改写成起点（终点）为vk的简单回路, 再置v=vk,v=vk, i←i+1,转1.

现在再考虑例15.2中图15.4中图（1）, 用逐步插入回路法可以走出多条欧拉回路. 现在走出一条来：演示

开始时, 置v=v1, v=v1, P0=v1, G0=G, 经过7步得 P7=v1e1v2e2v3e3v4e14v9e10v2e9v8e8v1,

P7是长度为7的简单回路, 见演示中红边所示.

在G7中有5条边与P7上的顶点相关联, 比如取v8与e7, 先将P7改写成以v8为起点（终点）的简单回路：

P7'=v8e8v1e1v2e2v3e3v4e14v9e10v2e9v8, 然后置v=v8, v=v8, 再经过4步得 P11=P'∪(v8e7v7e6v6e12v9e11v8), 后插入的回路为绿色的.

在G11中, e4,e3,e13均与P11上的顶点关联. 比如取v4与e13, 再将P11改写成以v4为起点（终点）的简单回路

P11'=v4e3v3e2v2e1v1e8v8e7v7e6v6e12v9e11v8e9v2e10v9e14v4 再置v=v4, v=v4, 再经过3步得 P14=P11'∪（v4e13v6e5v5e4v4）

又插入一个长度为3的回路, 见演示中蓝色所示. 则E(P14)=E(G), 故P14是G的一条欧拉回路.

*

*

*

*

*

*

哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图的定义

定义15.2 经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路. 经过图中所有顶点一次且仅一次的回路称为哈密顿回路. 具有哈密顿回路的图称为哈密顿图, 具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图. 平凡图是哈密顿图.

图15.1中所示的三个无向图都有哈密顿回路, 所以都是哈密顿图. 有向图中, （4）具有哈密顿回路, 因而它是哈密顿图. （5）只有哈密顿通路, 但无哈密顿回路, 因而它是半哈密顿图, 而（6）中既无哈密顿回路, 也没有哈密顿通路, 因而不是哈密顿图, 也不是半哈密顿图.

哈密顿图与半哈密顿图的一些必要条件

从定义可以看出, 哈密顿通路是图中生成的初级通路, 而哈密顿回路是生成的初级回路. 判断一个图是否为哈密顿图, 就是判断能否将图中所有顶点都放置在一个初级回路（圈）上, 但这不是一件易事. 与判断一个图是否为欧拉图不一样, 到目前为止, 人们还没有找到哈密顿图简单的充分必要条件. 下面给出的定理是哈密顿通路（回路）的必要条件. 定理15.6 设无向图G=是哈密顿图, 对于任意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|.

本定理的条件是哈密顿图的必要条件, 但不是充分条件. 可以验证彼得松图（图14.3中（1）所示）满足定理中的条件, 但它不是哈密顿图. 当然, 若一个图不满足定理中的条件, 它一定不是哈密顿图.

V, 且V1≠

, 均有

推论 设无向图G=是半哈密顿图, 对于任意的V1 p(G-V1)≤|V1|+1

V且V1≠均有

证 设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.6中给出的三个图都是二部图. 它们中的哪些是哈密顿图？哪些是半哈密顿图？为什么？

解 在（1）中, 易知互补顶点子集V1={a,f},V2={b,c,d,e}. 设此二部图为G1, 则G1=. p(G1-V1)=4>|V1|=2, 由定理15.6及其推论可知, G1不是哈密顿图, 也不是半哈密顿图.

设（2）中图为G2, 则G2=, 其中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中一条哈密顿通路（演示）.

设（3）中图为G3. G3=, 其中V1={a,c,g,h,e}, V2={b,d,i,j,f}, G3中存在哈密顿回路（演示）, 如abcdgihjefa, 所以G3是哈密顿图.

图15.6

通过本例, 清楚地看出, 哈密顿通路是经过图中所有顶点的一条初级通路, 而哈密顿回路是经过图中所有顶点的初级回路.

对于二部图还能得出下面结论：

一般情况下, 设二部图G=, |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 设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必为连通图.

下面证G中存在哈密顿通路. 设Г=v1v2?vl为G中用“扩大路径法”得到的“极大路径”, 即Г的始点v1与终点vl不与Г外的顶点相邻. 显然有l≤n.

(1)若l=n, 则Г为G中哈密顿通路.

(2)若l

(a)若v1与vl相邻, 即(v1,vl)∈E(G), 则Г∪(v1,vl)为满足要求的圈.

(b)若v1与vl不相邻, 设v1与Г上的相邻（k≥2, 否则

相邻的顶点

相邻（2≤r≤k）,

d(v1)+d(vl)≤1+l-2=l-1

之一相邻（否则, d(v1)+d(vl)≤k+l-2-(k-1)=l-1

见图15.7(1)所示. 于是, 回路C=

过Г上的所有顶点.

图15.7

(c)下面证明存在比Г更长的路径. 因为l

比Г长度大1, 对Г'上的顶点重新排序, 使其成为Г'=v1v2?vlvl+1,

对Г'重复（a）～（c）, 在有限步内一定得到G的哈密顿通路.

推论 设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 设u,v为n阶无向图G中两个不相邻的顶点, 且d(u)+d(v)≥n, 则G为哈密顿图当且仅当G∪(u,v)为哈密顿图（（u,v）是加的新边）.

本定理的证明留作习题.

例15.5 在某次国际会议的预备会议中, 共有8人参加, 他们来自不同的国家. 已知他们中任何两个无共同语言的人中的每一个, 与其余有共同语言的人数之和大于或等于8, 问能否将这8个人排在圆桌旁, 使其任何人都能与两边的人交谈.

解 设8个人分别为v1,v2,?,v8, 作无向简单图G=, 其中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, 且(vi,vj)?????均

为G中一条哈密顿

有d(vi)+d(vj)≥8.由定理15.7的推论可知, G中存在哈密顿回路, 设C=回路, 按这条回路的顺序安排座次即可.

从此例更可以看出, 哈密顿图是能将图中所有顶点都能安排在某个初级回路上的图. 定理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为其中一条. 下面证明vk+1可扩到Г1中去. 若存在v'r（1≤r≤k）, 有∈E(D), i=1,2,?,r-1, 而∈E(D), 见图15.8（1）所示, 则Г=v'1v'2?v'r-1vk+1v'r?v'k为D中哈密顿通路. 否则,

i∈{1,2,?,k}, 均有∈E(D), 见图15.8（2）所示, 则Г=Г'∪为D中哈密

顿通路.

图15.8

例15.6 图15.9所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？

图15.9

解 在（1）中, 存在哈密顿回路（演示）, 所以（1）为哈密顿图.

在（2）中, 取V1={a,b,c,d,e}, 从图中删除V1得7个连通分支, 由定理15.6和推论可知, (2)不是哈密顿图, 也不是半哈密顿图.

在（3）中, 取V1={b,e,h}, 从图中删除V1得4个连通分支, 由定理15.6可知, 它不是哈密顿图. 但（3）中存在哈密顿通路（演示）, 所以（3）是半哈密顿图.

从以上的讨论可知, 判断给定图是否为哈密顿图是个难题. 如果在图中能找出哈密顿回路, 或满足某充分性定理的条件, 则该图为哈密顿图, 但这样的定理是不多的. 另外, 人们可根据哈密顿图的某些必要条件判断某些图不是哈密顿图.

在本节的最后, 谈谈哈密顿图名称的来历. 1859年, 数学家哈密顿（Hamilton）提出一个问题：能否在正十二面体（见图15.9中的（1））上求一条初级回路, 使它含图中所有顶点？他形象地将每个顶点比作一个城市, 连接两个顶点之间的边看作城市之间的交通线. 于是原始问题就变成了所谓的周游世界问题：能否从某个城市出发沿交通线经过每个城市一次并且仅一次, 最后回到出发点？哈密顿自己做了肯定的回答. 后人为了纪念这位数学家, 将经过图中每个顶点一次且仅一次的回路称为哈密顿回路, 将有这种回路的图称为哈密顿图.

带权图

定义15.3 给定图G=（G为无向图或有向图）, 设W：E→R（R为实数集）, 对G中任意的边e=(vi,vj)（G为有向图时, e=）, 设W(e)=wij, 称实数wij为边e上的权, 并将wij标注在边e上, 称G为带权图, 此时常将带权图G记作. 设G'G, 称W(e)为G'的权, 并记作W(G'), 即

W(G')=

W(e).

货郎担问题

带权图应用的领域是相当广的, 许多图论算法也是针对带权图的. 下面介绍的货郎担问题就是针对n阶无向完全带权图的.

设有n个城市, 城市之间均有道路, 道路的长度均大于或等于0, 可能是∞（对应关联的城市之间无交通线）. 一个旅行商从某个城市出发, 要经过每个城市一次且仅一次, 最后回到出发的城市, 问他如何走才能使他走的路线最短？这就是著名的旅行商问题或货郎担问题. 这个问题可化归为如下的图论问题.

设G=, 为一个n阶完全带权图Kn, 各边的权非负, 且有的边的权可能为∞.求G中一条最短的哈密顿回路, 这就是货郎担问题的数学模型.

在讨论货郎担问题之前, 首先应该弄清楚, 在此问题中不同哈密顿回路的含义. 将图中生成圈看成一个哈密顿回路, 即不考虑始点（终点）的区别以及顺时针行遍与逆时针行遍的区别. 例15.7 图15.10(1)所示图为4阶完全带权图K4.求出它的不同的哈密顿回路, 并指出最短的哈密顿回路.

图15.10

解 由于货郎担问题中不同哈密顿回路的含义可知, 求哈密顿回路从任何顶点出发都可以. 下面先求出从a点出发, 考虑顺时针与逆时针顺序的不同的哈密顿回路.

C1=a b c d a C2=a b d c a C3=a c b d a C4=a c d b a C5=a d b c a C6=a d c b a

于是, 当不考虑顺（逆）时针顺序时, 可知C1=C6, 以C1为代表, W(C1)=8（见图15.10（2））. C2=C4, 以C2为代表, W(C2)=10（见图15.10（3））. C3=C5, 以C3为代表, W(C3)=12.经过比较可知, C1是最短的哈密顿回路.

由例15.7的分析可知, n阶完全带权图中共存在(n-1)!种不同的哈密顿回路, 经过比较, 可找出

最短哈密顿回路. n=4时, 有3种不同哈密顿回路, n=5时有12种, n=6时, 有60种, n=7时, 有360种, ?, n=10时, 有5×9!=1 814 400种, ?, 由此可见货郎担问题的计算量是相当大的. 对于货郎担问题, 人们一方面还在寻找好的算法, 另一方面也在寻找各种近似算法.

本文来源：https://www.bwwdw.com/article/xtmr.html