迷茫的旅行商 图的哈密尔领性 一名旅行商要拜访多个地点时， 如何找到在拜访每个地点一次后再回到起点的最短路径？？ 很难吗？ 不信你试试！即使就只有33个地方，瞎走的话也许真的要走上至少200年！ 1
迷茫的旅行商 —— 图的哈密尔顿性 1
(一)、哈密尔顿图的概念 1、背景 1857年，哈密尔顿发明了一个游戏(Icosian Game). 它是由一个木制的正十二面体构成，在它的每个棱角 处标有当时很有名的城市。游戏目的是“环球旅行”。 为了容易记住被旅游过的城市，在每个棱角上放上一 个钉子，再用一根线绕在那些旅游过的城市上（钉子）， 由此可以获得旅程的直观表示
1、背景 (一)、哈密尔顿图的概念 2 1857年， 哈密尔顿发明了一个游戏(Icosian Game). 它是由一个木制的正十二面体构成，在它的每个棱角 处标有当时很有名的城市。游戏目的是“ ”。 为了容易记住被旅游过的城市，在每个棱角上放上一 个钉子，再用一根线绕在那些旅游过的城市上(钉子), 由此可以获得旅程的直观表示
哈密尔顿把该游戏以25英镑的价格买给了 J.Jacques and Sons公司（该公司如今以制造国际象棋 设备而著名)，1859年获得专利权。但商业运作失败了。 该游戏促使人们思考点线连接的图的结构特征。 这就是图论历史上著名的哈密尔领问题。 哈密尔顿(1805--1865)，爱尔兰数学家。个人生活 很不幸，但兴趣广泛：诗歌、光学、天文学和数学无 所不能。他的主要贡献是在代数领域，发现了四元数 (第一个非交换代数)，他认为数学是最美丽的花朵
哈密尔顿把该游戏以 的价格买给了 J.Jacques and Sons公司 (该公司如今以制造国际象棋 设备而著名) ，1859年获得专利权。但商业运作失败了。 该游戏促使人们思考点线连接的图的 。 这就是图论历史上著名的 。 3
2、哈密尔顿图与哈密尔顿路 定义1如果图G的一个圈C含有G的所有顶点，则称C 为图G的哈密尔顿圈，简称哈圈或者H-圈
2、哈密尔顿图与哈密尔顿路 定义1 如果图G的一个圈C含有G的所有顶点，则称C 为图G的哈密尔顿圈, 简称哈圈或者H-圈
定义2如果图G的一条路P含有G的所有顶点，则称P 为图G的哈密尔顿路，简称哈路或者H-路
定义2 如果图G的一条路P含有G的所有顶点，则称P 为图G的哈密尔顿路, 简称哈路或者H-路。 u v