下载文档原格式
必要条件充分条件其它方法应用特殊图哈密顿图周游世界问题1859年英国数学家威廉·哈密顿爵士发明了一个小玩具，这个小玩具是一个木刻的正十二面体，每面系正五角形，共有20个顶点，每个顶点标有世界上一个重要城市。
他提出一个问题：要求沿正十二面体的边寻找一条路通过20个城市，而每个城市只通过一次，最后返回原地。
哈密顿将此问题称为周游世界问题。
Definition设G是一个无向或有向图，若存在一条通路(回路)，经过图中每个结点一次且仅一次，则称此通路(回路)为该图的一条哈密顿通路(回路)。
具有哈密顿回路的图称为哈密顿图(Hamiltonian graph)。
注意规定：平凡图为哈密顿图；哈密顿通路是经过图中所有结点的通路中长度最短的通路；哈密顿回路是经过图中所有结点的回路中长度最短的回路。
Examplev1v2v3v4(a)哈密顿图(哈密顿回路)v1v2v3v4v5(b)存在哈密顿通路v1v2v3v4v5v6v7(c)无哈密顿通路v1v2v3v4(d)哈密顿图(哈密顿回路)v1v2v3v4(e)v1v2v3v4(f)引子定义必要条件充分条件其它方法应用哈密顿图的必要条件Theorem设无向图G=<V,E>是哈密顿图，V1是V的任意非空子集，则p(G−V1)⩽|V1|，其中p(G−V1)是从G中删除V1后所得到图的连通分支数。
Proof.设C是G中的一条哈密顿回路，V1是V的任意非空子集。
下面分两种情况讨论：（1）V1中结点在C中均相邻，删除C上V1中各结点及关联的边后，C−V1仍是连通的，但已非回路，因此p(C−V1)=1⩽|V1|。
（2）V1中结点在C上存在r(2⩽r⩽|V1|)个互不相邻，删除C上V1中各结点及关联的边后，将C分为互不相连的r段，即p(C−V1)=r⩽|V1|。
一般情况下，V1中的结点在C中即有相邻的，又有不相邻的，因此总有p(C−V1)⩽|V1|。
离散数学-图论-哈密顿图及其应⽤哈密顿图⼀、定义概念1.哈密顿通路设G=<V,E>为⼀图（⽆向图或有向图）.G中经过每个顶点⼀次且仅⼀次的通路称作哈密顿通路2.哈密顿回路G中经过每个顶点⼀次且仅⼀次的回路（通路基础上+回到起始点）称作哈密顿回路3.哈密顿图若G中存在哈密顿回路，则称它是哈密顿图4.定义详解：（1）存在哈密顿通路（回路）的图⼀定是连通图；（2）哈密顿通路是初级通路，哈密顿回路是初级回路；（3）若G中存在哈密顿回路，则它⼀定存在哈密顿通路，反之不真（看课本的话，是必要条件，⽽不是充分条件，故不可反推！）（4）只有哈密顿通路，⽆哈密顿回路的图不叫哈密顿图；即，哈密顿图是回路⼆、判定定理注意：⽬前还没有找到哈密顿图的简单的充要条件（1）设⽆向图G=<V,E>为哈密顿图，V1是V的任意真⼦集，则（注：n阶xx图指的是n个顶点，不要迷！）p(G-V1)<=|V1|其中，p(G-V1)为G中删除V1后的所得图的连通分⽀数⽬，|V1|为V1集合中包含的顶点个数。
【哈密顿图存在的必要条件】推论：有割点的图⼀定不是哈密顿图设v是图中的割点，则p(G-v)>=2,由上述定理知G不是哈密顿图（2）设G是n(n>=3)阶⽆向简单图，若对于G中的每⼀对不相邻的顶点u,v,均有d(u)+d(v)>=n-1则G中存在哈密顿通路。
⼜若d(u)+d(v)>=n则G中存在哈密顿回路，即G为哈密顿图。
【哈密顿图存在的充分条件，不是必要条件】其中d(u),d(v)分别代表顶点u,v的度数。
推论：设G是n(n>=3)阶⽆向简单图，若G的最⼩度>=n/2,则G是哈密顿图。
由推论知，对于完全图Kn,当n>=3时，是哈密顿图，完全⼆部图Kr,s当r==s>=2时是哈密顿图。
（3）在n(n>=2)阶有向图D=<V,E>中，如果略去所有有向边的⽅向，所得⽆向图中含⽣成⼦图Kn,则D中存在哈密顿通路。
离散结构哈密顿图教学目标基本要求（1）哈密顿图的定义（2）哈密顿图的充分条件与必要条件（3）哈密顿图的应用重点难点（1）哈密顿图的判定（2）哈密顿图的应用1859年提出一个名叫“周游世界”的游戏，问题是：能否遍历正12面体的每个顶点一次且仅一次后回到原地。
？哈密顿（爱尔兰数学家）定义•哈密顿通路——经过图中所有顶点一次仅一次的通路.•哈密顿回路——经过图中所有顶点一次仅一次的回路.•哈密顿图——具有哈密顿回路的图.•半哈密顿图——具有哈密顿通路且无哈密顿回路的图.•几点说明：–平凡图是哈密顿图.–哈密顿通路是初级通路，哈密顿回路是初级回路.–环与平行边不影响哈密顿性.–哈密顿图的实质是能将图中的所有顶点排在同一个圈上实例在上图中，•(1),(2) 是哈密顿图;•(3)是半哈密顿图;•(4)既不是哈密顿图，也不是半哈密顿图，为什么？哈密顿图的必要条件•定理设无向图G =<V ,E >是哈密顿图，对于任意V 1⊂V 且V 1≠∅，均有p (G −V 1) ≤|V 1|•推论设无向图G=<V ,E>是半哈密顿图，对于任意的V 1⊂V 且V 1≠∅均有p (G −V 1) ≤|V 1|+1•几点说明–定理中的条件是哈密顿图的必要条件，但不是充分条件（例如彼得松图）–由定理可知，K r ,s 当s ≥r +1时不是哈密顿图. 易知K r ,r （r ≥2）时都是哈密顿图，K r ,r +1都是半哈密顿图.哈密顿图的充分条件•定理设G是n阶无向简单图，若对于任意不相邻的顶点v,v j，均有id(v i)+d(v j) ≥n−1则G 中存在哈密顿通路.,v j，均有•推论设G为n(n≥3) 阶无向简单图，若对于G中任意两个不相邻的顶点vid(v i)+d(v j) ≥n则G中存在哈密顿回路，从而G为哈密顿图.•几点说明–定理是半哈密顿图的充分条件，但不是必要条件. 长度为n−1（n≥4）的路径构成的图不满足条件，但它显然是半哈密顿图.–推论同样不是哈密顿图的必要条件，G为长为n的圈，不满足条件，但它当然是哈密顿图.例在给出的三个图中哪些是哈密顿图？哪些是半哈密顿图？为什么？例试判断下面在给出的图是欧拉图还是哈密顿图？判断某图是否为哈密顿图至今还是一个难题.哈密尔顿图的应用例：一只蚂蚁可否从立方体的一个顶点出发，沿着棱爬行，它爬过每一个顶点一次且仅一次，最后回到原出发点？试利用图作解释。
定义4.3.1 经过图G 的每个顶点恰一次的路称为G 的Hamilton 路，简称为H 路。
经过图G 的每个顶点恰一次的圈称为G 的Hamilton 圈，简称为H 圈。
具有Hamilton 圈的图称为Hamilton 图，简称为H 图。
Hamilton 图的研究起源于一种十二面体上的游戏。
1857 年，爱尔兰著名数学家William Rowan Hamilton 爵士（他也是第一个给出复数的代数描述的人）制作了一种玩具，它是一个木制的正十二面体，在正十二面体的每个顶点上有一个木栓，并标有世界著名城市的名字。
游戏者用一条细线从一个顶点出发，设法沿着十二面体的棱找出一条路，通过每个城市恰好一次，最后回到出发点。
这个游戏当时称为Icosian 游戏，也称为周游世界游戏。
将正十二面体从一个面剖开并铺展到平面上得到的图形如下图所示，称为十二面体图。
周游世界游戏用图论术语来说就是判断十二面体图是否Hamilton 图，并设法找出其Hamilton 圈。
其中一条Hamilton 圈如图中粗边所示。
十二面体图是H 图判断一个图是否Hamilton 图与判断一个图是否Euler 图似乎很相似，然而二者却有本质的不同。
目前为止尚没有找到判别一个图是否是Hamilton 图的有效充要条件。
这是图论和计算机科学中未解决的重要难题之一。
本节给出一些经典的充分条件和必要条件。
一、必要条件定理4.3.1 设G 是二部图，若G 是H 图，则G 必有偶数个顶点。
证明：设G = (X, Y ) ，由于G 的边全在X 和Y 之间，因此如果G 有Hamilton 圈C，则G的所有顶点全在C 上，且必定是X 的点和Y 的点交替在C 上出现，因此G 必有偶数个顶点。
证毕。
这个定理给出了一个二部图不是Hamilton 图的简单判断条件：如果一个二部图有奇数个顶点，则它必定不是Hamilton 图。
例如，下列Herschel 图是二部图，但有奇数个顶点，故不是H 图。
图论中的哈密顿图与欧拉图图论是数学的一个分支，研究图的性质及其应用。
在图论中，哈密顿图和欧拉图是两个重要的概念。
本文将介绍哈密顿图和欧拉图的定义、性质和应用，并探讨它们在现实生活中的实际应用。
一、哈密顿图的定义与性质哈密顿图是指一种包含了图中所有顶点的路径的图。
具体来说，哈密顿图是一个简单图，其中任意两个不同的顶点之间都存在一条路径，使得该路径经过图中的每个顶点且不重复。
哈密顿图具有以下的性质：1. 哈密顿图是一个连通图，即图中的每两个顶点之间都存在通路。
2. 图中每个顶点都是度数大于等于2的点，即每个顶点都至少连接着两条边。
二、欧拉图的定义与性质欧拉图是指一种可以通过图中每条边恰好一次的路径来穿越图的图。
具体来说，欧拉图是一个简单图，其中经过图中每条边且路径不重复的路径称为欧拉路径，而形成闭合回路的欧拉路径称为欧拉回路。
欧拉图具有以下的性质：1. 每个顶点的度数都是偶数，即每个顶点都连接着偶数条边。
2. 欧拉图中至少有两个连通分量，即图中有至少两个不同的部分可以从一部分通过路径到达另一部分。
三、哈密顿图与欧拉图的应用哈密顿图和欧拉图在实际生活中有广泛的应用，下面将分别介绍它们的应用领域。
1. 哈密顿图的应用：哈密顿图在旅行商问题中有着重要的应用。
旅行商问题是指一个旅行商要依次拜访若干个城市，然后返回起始城市，而要求找到一条最短的路径使得每个城市都被访问一次。
哈密顿图可以解决这个问题，通过寻找一条哈密顿路径来确定最短的路径。
2. 欧拉图的应用：欧拉图在电路设计和网络规划中发挥着重要的作用。
在电路设计中，欧拉图可以帮助我们确定如何安排电线的布线以最大程度地减少电线的长度和复杂度。
在网络规划中，欧拉图可以用于确定如何正确地连接不同的网络节点以实现高效的信息传输。
四、结论哈密顿图和欧拉图是图论中的两个重要概念。
哈密顿图是一种包含了图中所有顶点的路径的图，而欧拉图是一种可以通过图中每条边恰好一次的路径来穿越图的图。
定义4.3.1 经过图G 的每个顶点恰一次的路称为G 的Hamilton 路，简称为H 路。
经过图G 的每个顶点恰一次的圈称为G 的Hamilton 圈，简称为H 圈。
具有Hamilton 圈的图称为Hamilton 图，简称为H 图。
Hamilton 图的研究起源于一种十二面体上的游戏。
1857 年，爱尔兰著名数学家William Rowan Hamilton 爵士（他也是第一个给出复数的代数描述的人）制作了一种玩具，它是一个木制的正十二面体，在正十二面体的每个顶点上有一个木栓，并标有世界著名城市的名字。
游戏者用一条细线从一个顶点出发，设法沿着十二面体的棱找出一条路，通过每个城市恰好一次，最后回到出发点。
这个游戏当时称为Icosian 游戏，也称为周游世界游戏。
将正十二面体从一个面剖开并铺展到平面上得到的图形如下图所示，称为十二面体图。
周游世界游戏用图论术语来说就是判断十二面体图是否Hamilton 图，并设法找出其Hamilton 圈。
其中一条Hamilton 圈如图中粗边所示。
十二面体图是H 图判断一个图是否Hamilton 图与判断一个图是否Euler 图似乎很相似，然而二者却有本质的不同。
目前为止尚没有找到判别一个图是否是Hamilton 图的有效充要条件。
这是图论和计算机科学中未解决的重要难题之一。
本节给出一些经典的充分条件和必要条件。
一、必要条件定理4.3.1 设G 是二部图，若G 是H 图，则G 必有偶数个顶点。
证明：设G = (X, Y ) ，由于G 的边全在X 和Y 之间，因此如果G 有Hamilton 圈C，则G的所有顶点全在C 上，且必定是X 的点和Y 的点交替在C 上出现，因此G 必有偶数个顶点。
证毕。
这个定理给出了一个二部图不是Hamilton 图的简单判断条件：如果一个二部图有奇数个顶点，则它必定不是Hamilton 图。
例如，下列Herschel 图是二部图，但有奇数个顶点，故不是H 图。
Herschel 图不是H 图定理4.3.2 若G 是H 图，则对V(G)的每个非空真子集S，均有：连通分支数W(G－S) ≤| S |。
证明：设C 是G 的H 圈，则对V(G)的每个非空真子集S，均有W(C－S) ≤| S |.由于C－S 是G－S 的生成子图，故W(G－S)≤W(C－S)≤| S |. 证毕。
利用定理4.3.2 可判断下面(1)中的图不是H 图。
事实上，令S={u, v, w}，则W(G－S) = 4 > | S |。
但无法用该定理给出的必要条件来判断(2)中的Petersen 图不是H 图。
二、充分条件（1）度型条件定理4.3.3(Dirac, 1952) 若G是简单图，且ν≥3，δ≥v/2，则G 是Hamilton 图。
证明用反证法：假定定理不真。
令A = {G |G的顶点数为V≥3，δ≥v/2 ，且G 是非Hamilton 图}。
从A中取出边最多的一个，记为G。
因ν≥3，故不是完全图（否则G是Hamilton 图）。
设u 和v 是G 的不相邻顶点。
由G 的选择，G＋uv 是Hamilton 图。
因G 是非Hamilton 图，故G＋uv 的H 圈必经过e = uv。
于是G 中存在以u 为起点v 为终点的Hamilton 路νv1v2.。
v 。
这里v = u ，v v = v 令S={V i|uv i+1∈E}和T={v|v i v∈E}。
由于v v∉S ∪T ，故| S ∪T |<ν，并且| S ∩T |= 0（因为若∃v i∉S ∪T，则G将包含H圈v1v2…v i v v v i-1…v i+1v1，矛盾）。
故d(u) + d(v) =| S | + | T |=| S ∪T | + | S ∩T |<ν，这与δ≥v/2 的前提矛盾。
证毕。
(2) 闭包型条件Ore 注意到，上述Dirac 定理的证明过程中，条件δ≥v/2 仅仅用来证明对不相邻顶点u,v，有d(u) + d(v) ≥ν成立。
因此可以将图存在Hamilton 圈的条件由δ≥v/2 弱化为d(u) + d(v) ≥ν。
这样便得到下述定理。
定理4.3.4（Ore，1960）[1] 设G是简单图，u 和v 是G中不相邻的顶点，且d(u) + d(v) ≥ν，则G 是Hamilton 图当且仅当G＋uv 是Hamilton 图。
证明：必要性是显然的。
充分性：若G＋uv 是Hamilton 图而G 不是，则与定理4.3.3 一样可推出矛盾。
证毕。
Bondy 和Chvátal 用更一般的形式表述了Ore 观察到的实质，得到了图存在长度为k的圈和其它子图的充分条件( k =υ时便是Hamilton 圈)[2]。
他们用到了闭包的概念。
定义：图G 的闭包（closure）是指由如下方法所得之图：反复连接G 中度之和不小于ν的不相邻顶点对，直到没有这样的顶点对为止。
图G 的闭包通常记为C(G)。
例如，对下列两图，前一个图的闭包是它自己，后一个图的闭包是完全图K5。
定理4.3.5 G 的闭包C(G)是唯一确定的。
证明：设G1,G2是按闭包构成方法从G所得的两个闭包。
用e1，e 2, …e m和f1, f 2…f n分别表示在构作G1,G2过程中给G 添加边的序列。
我们用反证法来证明每个e i一定是G2 的边，且每个f j一定是G1的边。
假设e1，e 2, …e m中有不属于G 的边，取序列中第一条不属于G2 的边设为e k =uv ，令H=G+{e1，e 2, …e k+1}由G1的定义知，d H(u) + d H (v) ≥ν。
但H也是G2的子图，因此由d H(u) + d H (v) ≥ν知，d G2(u) + d G 2(v) ≥ν。
而由e k的选择，u、v 在G2中是不相邻的，这与G2是闭包矛盾。
故每条e i都必是G2的边。
同理可证，每条j f 一定是1 G 的边。
这说明图G 的闭包是唯一的。
证毕。
定理4.3.6（Bondy & Chvátal,1976）[2] 一个简单图是Hamilton 图当且仅当它的闭包是Hamilton 图。
证明：在构作闭包过程中，反复运用定理4.3.4 即可。
证毕。
根据该定理，下一个结论是显然的。
推论4.3.1 设G是ν≥3的简单图。
若C(G)是完全图，则G是Hamilton 图。
定理4.3.2 后的例子改动一条边后所得的如下图，可以检验它的闭包是完全图，因而是Hamilton 图。
（3）度序列条件Chvátal 发现，如果图G 满足：若有某些顶点的度比较小，则就有相应另一些顶点的度 足够大，那么G 就会成为Hamilton 图。
具体来说，设简单图G 的顶点度为d 1≤d 2≤…≤d v 如果对任意正整数m>v/2 ，要么d m > m ，要么d v -m<v-m ，则G 是Hamilton 图。
这个结论正式叙述如下。
定理 4.3.7 (Chvátal,1972)[3] 设 G 至少含有3 个顶点的简单图，其度序列为(d 1,d 2…d v 这里d 1≤d 2≤…≤d v 。
若不存在小于v/2的m 使得d m ≤ m 和d v-m <v-m 同时成立，则 G 是Hamilton 图。
证明：设 G 满足定理条件。
我们来证明G 的闭包C(G)是完全图。
用反证法。
假设 C(G)不是完全图。
设u 、v 是C(G)中两个不相邻顶点，满足d (u ) ≤ d (v )，且 d (u ) + d (v )尽可能大。
（d (v )表示v 在C(G)中的度）。
由C(G)的定义，d (u ) +d (v )<υ 。
令N (u ) = {w ∈V \ {u } | w 在C(G)中与u 不相邻};N (v ) = {w ∈V \ {v } | w 在C(G)中与v 不相邻};则()u d N v ----=1||| N (u ) |=υ −1−d (u )，|N (v ) |=υ−1−d (v )。
记d (u ) = m ，则|N (u ) |=υ −1− m ，|N (v ) |=υ −1− d (v ) >υ −1− (υ − d (u )) = m −1(1)另外，由u 、v 的选择（d (u ) + d (v )尽可能大）知，N (u ) ∪{u }中每个顶点在C(G)中的度 不超过d (v )（否则，设v ′∈ N (u )，d (v ′) >d (v )，则d (u ) + d (v ′) > d (u ) + d (v )，当初应当选择u 和v ′）。
同理，N (v )中每个顶点在C(G)中的度不超过d (u )。
结合（1）式可知：C(G)中至少有ν−m个顶点，其度≤d (v) <ν−m ，（比如N(u) ∪{u}中的顶点）；C(G)中至少有m 个顶点，其度≤m，（比如N(v)中的顶点）；由于G 是C(G)的子图，故上述结论对G 也成立。
按照度序列的排列方式，便有d m ≤m 和d v-m>v-m，并且m <v/2（因d (u) ≤d (v)及d (u) + d (v) <ν）。
这与定理的条件矛盾。
该矛盾说明C(G)确实是完全图。
由推论4.3.1，G 是Hamilton 图。
证毕。
§4.4 旅行商问题(Travelling Salesman Problem,TSP)旅行商问题：有n 个城镇。
一个旅行商从某一城镇出发，欲经过其余n −1个城镇一次且仅一次，最后回到出发点。
他应该如何设计旅行路线，才能使所走路程最短？图论描述：将城镇作为顶点，两顶点连边当且仅当对应的两城镇能直达，每条边上以道路的里程作为权。
从而获得一个赋权图G。
旅行商问题现在可以叙述为：给定赋权图G，求G 的一个权最小的Hamilton 圈。
这一问题看似简单，实际上含有两个困难的问题：（1）如何判定G 是否有Hamilton 圈；（2）在已知G 是Hamilton 图的情况下，如何求出一个权最小的Hamilton 圈来。
这两个问题目前尚未找到有效算法，甚至不知道这样的有效算法是否存在。
事实上它们是NPC 问题。
转化：给G 添加权为∞的边，化为赋权完全图。
问题化为：对赋权完全图n K ，求其最小权Hamilton 圈，这样的圈称为最小Hamilton 圈。
在n K 中，共有1/2（n-1）！个不同的Hamilton 圈（v 到其余顶点有n −1条边）。
如果一计算各Hamilton 圈的长度，再逐个比较出权最小的一个，则计算量太大。
当n 较大时无法实现。
对这样的NPC 问题，一般解决方法是设计较好的近似算法，求其近似最优解。
