2009-7-26 1
运 筹 学 Operations Research
§ 6.4 旅行售货员问题哈密尔顿路 （ Hamilton path）,含有图的所有顶点的路,
哈密尔顿圈 （ Hamilton cycle）,含有图的所有顶点的圈,
哈密尔顿图 （ Hamilton graph）,含有哈密尔顿圈的图；
半哈密尔顿图 （ SemiHamilton graph）,含有哈密尔顿路,
但不含有哈密尔顿圈的图 ；
非哈密尔顿图 （ nonHamilton graph）,otherwise.
)3(K
2009-7-26 2
运 筹 学 Operations Research
)2(,?nK nn
半 Hamilton图,非 Hamilton图：
2009-7-26 3
运 筹 学 Operations Research
例 1画出满足下列条件的有 5个顶点的图：
(1)不是 Hamilton图,也不是 Euler图；
(2)是 Hamilton图,不是 Euler图；
(3)不是 Hamilton图,是 Euler图；
(4)是 Hamilton图,也是 Euler图,
解：
▌
2009-7-26 4
运 筹 学 Operations Research
与欧拉图不同，至今在理论上尚未找到判定 Hamilton
图的充要条件,
.)(a m i l t o n)(1 SSGVSHGTh，有图，则是若图必要性注：可利用 Th1的逆否命题来判断一个图不是 Hamilton图,
如
▌
.a m i l t o n13)( 图不是,HTSST
2009-7-26 5
运 筹 学 Operations Research
再如
.a mi l t o n23)( 图不是,HGSSG
.a m i l t o n)()(
,,3)(2
图是，则有
，，若是简单图，设充分性
HGvdud
EuvVvuGTh

▌
2009-7-26 6
运 筹 学 Operations Research
.a m i lt o n23 图是，则，若是简单图，设 HGGC o r
.222)()( vdud?证,▌
.a m il t o n2)2(
a m il t o n3)1(2
,图是，则若图；是，则若求证：例
HKn
HK
nn?

.2)2(;21)1( nn证,▌
2009-7-26 7
运 筹 学 Operations Research
环游世界问题,1859年,英,William Hamilton
世界上的 20个城市恰好构成一个正十二面体的顶点,某旅行者欲从某一城市出发,经过每个城市恰好一次,再回到原出发城市,问：这样的旅行路线是否存在？
2009-7-26 8
运 筹 学 Operations Research
环游世界问题在图 G中能否找到一个 Hamilton圈？
易见,图 中 存在 一 个
Hamilton圈,1,2,3,4，
12,11,10,9,8,7,6，
15,16,17,18,19,20，
13,14,5,1.▌
2009-7-26 9
运 筹 学 Operations Research
旅行售货员问题 （ 旅行商问题,货郎担问题 ） （ TSP，
traveling salesman problem）,
今有 n个 村庄,任两个 村庄 之间均有道路相通,道路的长度已知,一个货郎欲从自己的家所在的 村庄 去另外的 n个 村庄 售货,问：这个货郎应如何选择行走路线,才能经过每个村庄 恰好一次,再回到原出发 村庄,且总行程最短？
以 n个顶点表示 n个村庄,两个顶点之间有边相连当且仅当两个村庄之间有道路相通,以道路的长度作为边的权,得一个赋权完全图 G.于是,TSP求赋权完全图 G的一个最小权
Hamilton圈,
至今尚未发现一个求解 TSP的有效算法,
下面是一个近似算法：
2009-7-26 10
运 筹 学 Operations Research
改进圈算法,1965年,Lin； 1970,1971年,Held,Karp
基本思想：从某一个 Hamilton圈开始，不断修改之，以得到一个最小权 Hamilton圈,
).()(..
}.,{},{
),(),(),(),(
1111
1111
CwCw
vvvvvvvvCC
vvwvvwvvwvvw
jijijjii
jijijjii





显然，
则令
，若
2009-7-26 11
运 筹 学 Operations Research
注,（ 1） 改进圈算法 最终得到的 Hamilton圈完全取决于选取的初始 Hamilton圈,故它未必最优,因此 改进圈算法 是一个近似算法,未必能求得最优 Hamilton圈,
（ 2）为求得一个,尽可能最优的,Hamilton圈，可在步骤
1选取若干不同的初始 Hamilton圈分别去求,最小权,Hamilton圈，再从中取权最小者为最优 Hamilton圈即可,
2009-7-26 12
运 筹 学 Operations Research
§ 6.4 over