《运筹学》课程PPT教学课件（Operations Research）第六章 图论（6.4）旅行售货员问题

运筹学 Operations Research §6.4旅行售货员问题 哈密尔顿路( Hamilton path):含有图的所有顶点的路 哈密尔顿圈( Hamilton cycle:含有图的所有顶点的圈 哈密尔顿图( Hamilton graph):含有哈密尔顿圈的图; 半哈密尔顿图( SemiHamilton graph):含有哈密尔顿路, 但不含有哈密尔顿圈的图; 非哈密尔顿图( nonHamilton graph): otherwise 风 K,(v≥3) 2021/2/20

2021/2/20 1 运 筹 学 Operations Research §6.4 旅行售货员问题 哈密尔顿路（Hamilton path）：含有图的所有顶点的路. 哈密尔顿圈（Hamilton cycle）：含有图的所有顶点的圈. 哈密尔顿图（Hamilton graph）：含有哈密尔顿圈的图； 半哈密尔顿图（SemiHamilton graph）：含有哈密尔顿路， 但不含有哈密尔顿圈的图； 非哈密尔顿图（nonHamilton graph）：otherwise. (  3) K

运筹学 Operations Research 2.3 半 Hamilton图: 非 Hamilton图: 树 Peterson图 2021/2/20 2

2021/2/20 2 运 筹 学 Operations Research ( 2) Kn,n n  半Hamilton图： 非Hamilton图：

运筹学 Operations Research 例1画出满足下列条件的有5个顶点的图: (1)不是 Hamilton图,也不是 Euler图 (2)是 Hamilton图,不是 Euler图; (3)不是 Hamilton图,是 Euler图; (4)是 Hamilton图,也是 Euler图 解 <风 (1) (3) 2021/2/20 3

2021/2/20 3 运 筹 学 Operations Research 例1画出满足下列条件的有5个顶点的图： (1)不是Hamilton图，也不是Euler图； (2)是Hamilton图，不是Euler图； (3)不是Hamilton图，是Euler图； (4)是Hamilton图，也是Euler图. 解： ▌

运筹学 Operations Research 与欧拉图不同,至今在理论上尚未找到判定 Hamilton 图的充要条件 mh(必要性)若图G是 Hamilton图,则v≠ScV,有o(G-S)≤S■ 注:可利用Th1的逆否命题来判断一个图不是 Hamilton图 如 O(7-S)=3>1=S,…7不是 Hamilton图 2021/2/20 4

2021/2/20 4 运 筹 学 Operations Research 与欧拉图不同，至今在理论上尚未找到判定Hamilton 图的充要条件. Th1(必要性)若图G是Hamilton 图，则  S V，有(G − S)  S . 注：可利用Th1的逆否命题来判断一个图不是Hamilton图. 如 ▌ (T − S) = 3 1= S，T不是Hamilton 图

运筹学 Operations Research 再如 ={,v G-S 0(G-S)=3>2=S,…G不是 hamilton图 Th2(充分性)设G是简单图,v≥3,若∨l,v∈V,L∈E, 有d(u)+d()≥v则G是 hamilton图囗 2021/2/20

2021/2/20 5 运 筹 学 Operations Research 再如 (G − S) = 3  2 = S，G不是Hamilton 图. ( ) ( ) amilton . 2 ( ) 3 , , 有 ，则 是 图 充分性 设 是简单图， ，若 ， d u d v G H Th G u v V uv E   +      ▌

运筹学 Operations Research or设G是简单图,p23,若2,则G是 hamilton图 证:∵:d(ul )+d(v)≥+6=28≥2.y 例2求证(1)若v≥3,则K是 hamilton图; (2)若n≥2,则K,是 Hamilton图 证():=-122(2):=n2n=2 2021/2/20 6

2021/2/20 6 运 筹 学 Operations Research amilton . 2 Cor 设G是简单图， 3，若 ，则G是H 图      . 2 ( ) ( ) 2 2   证：d u + d v   +  =    = ▌ (2) 2 amilton . 2 (1) 3 amilton 若 ，则 , 是 图 例 求证： 若 ，则 是 图； n K H K H  n n    . 2 ;(2) 2 (1) 1    证：  = −   = n  n = ▌

运筹学 Operations Research 环游世界问题:1859年,英, William hamilton 世界上的20个城市恰好构成一个正十二面体的顶点.某旅行者 欲从某一城市出发,经过每个城市恰好一次,再回到原出发城 市.问:这样的旅行路线是否存在? 12 15 3● 18 2021/2/20 7

2021/2/20 7 运 筹 学 Operations Research 环游世界问题：1859年，英，William Hamilton 世界上的20个城市恰好构成一个正十二面体的顶点.某旅行者 欲从某一城市出发，经过每个城市恰好一次，再回到原出发城 市.问：这样的旅行路线是否存在？

运筹学 Operations Research 14 环游世界问题在图G中 能否找到一个 Hamilton圈? 15 易见,图中存在一个 Hamilton圈:1,2,3,4 3 12,11,10,9,8,7,6, 15,16,17,18,19,20, 13,14,5 2021/2/20 8

2021/2/20 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.▌

运筹学 Operations Research 旅行售货员问题(旅行商问题,货郎担问题)(TSP, traveling salesman problem) 今有n个村庄,任两个村庄之间均有道路相通,道路的 长度已知.一个货郎欲从自己的家所在的村庄去另外的n个村 庄售货.问:这个货郎应如何选择行走路线,才能经过每个 村庄恰好一次,再回到原出发村庄,且总行程最短? 以n个顶点表示n个村庄,两个顶点之间有边相连当且仅 当两个村庄之间有道路相通,以道路的长度作为边的权,得 个赋权完全图G.于是,TSP求赋权完全图G的一个最小权 Hamilton圈. 至今尚未发现一个求解TSP的有效算法 下面是一个近似算法: 2021/2/20

2021/2/20 9 运 筹 学 Operations Research 旅行售货员问题（旅行商问题，货郎担问题）（TSP， traveling salesman problem）： 今有n个村庄，任两个村庄之间均有道路相通，道路的 长度已知.一个货郎欲从自己的家所在的村庄去另外的n个村 庄售货.问：这个货郎应如何选择行走路线，才能经过每个 村庄恰好一次，再回到原出发村庄，且总行程最短？ 以n个顶点表示n个村庄，两个顶点之间有边相连当且仅 当两个村庄之间有道路相通，以道路的长度作为边的权，得 一个赋权完全图G.于是，TSP求赋权完全图G的一个最小权 Hamilton圈. 至今尚未发现一个求解TSP的有效算法. 下面是一个近似算法：

运筹学 Operations Research 改进圈算法:1965年,Lin;1970,1971年,Held,Karp 基本思想:从某一个 Hamilton圈开始,不断修改之,以得 到一个最小权 Hamilton圈 2+1 +1 若v(vn,"1)+(vy,v)>v(v,”)+w(v+,vm), 则令C=C-{n1,””mH}+{,”1vH} 显然,(C)<v(C) 2021/2/20 10

2021/2/20 10 运 筹 学 Operations Research 改进圈算法：1965年，Lin；1970，1971年，Held，Karp 基本思想：从某一个Hamilton圈开始，不断修改之，以得 到一个最小权Hamilton圈. .. ( ) ( ). { , } { , } . ( , ) ( , ) ( , ) ( , ) 1 1 1 1 1 1 1 1 w C w C C C v v v v v v v v w v v w v v w v v w v v i i j j i j i j i i j j i j i j    = − + +  + + + + + + + + + 显然， 则令 若