运筹学 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 + ▌