西安电子科技大学：《图论》课程教学课件（研讨课PPT）第二讲 迷茫的旅行商——图的哈密尔顿性

迷茫的旅行商 图的哈密尔领性 一名旅行商要拜访多个地点时， 如何找到在拜访每个地点一次后再回到起点的最短路径？？ 很难吗？ 不信你试试！即使就只有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

定义3如果图G含有哈密尔顿圈，则称G为哈密尔顿 图 例1、正十二面体是H图。 例2下图G是非H图。 图G

定义3 如果图G含有哈密尔顿圈，则称G为哈密尔顿 图 例1、正十二面体是H图。 例2 下图G是非H图。 图G u v

(二)、性质与判定 1、性质 定理1（必要条件） 若G为H图，则对V(G)的任一非空顶点子集S,有： o(G-S)≤1S 证明：设C是G的H圈，则对V(G)的任意非空子集S,容 易知道： o(C-S)≤|S o(G)表示 图G所含的连通分支的个数 所以，有： o(G-S)≤o(C-S)≤|S 7

(二)、性质与判定 1、性质 定理1 (必要条件) 若G为H图，则对V(G)的任一非空顶点子集S，有： ( ) G S S −  证明：设C是G的H圈，则对V(G)的任意非空子集S, 容 易知道: ( ) C S S −  所以，有：   ( ) ( ) G S C S S −  −  7 ω(G)表示 图G所含的连通分支的个数

注：不等式为G是H图的必要条件，即不等式不满足 时，可断定对应图是非H图。 例3求证右图是非H图。 证明：取S={u,y,w},则有：o(G-S)=4>S=3 所以由定理1知，G为非H图。 8

注：不等式为G是H图的必要条件，即不等式不满足 时，可断定对应图是非H图。 证明：取S=｛u, v, w｝,则有： ( ) 4 3 G S S − =  = 所以由定理1知，G为非H图。 8 例3 求证右图是非H图

注意：满足定理1不等式的图不一定是H图。 例如：著名的彼德森图是非H图，但它满足定理1的 不等式。 彼得森(1839-1910)，丹麦哥本哈根大学数学教授。 家境贫寒，因此而辍过学。但19岁就出版了关于对数的 专著。他当过中学教师，32岁获哥本哈根大学数学博士 学位，然后一直在该大学作数学教授。 9

注意：满足定理1不等式的图不一定是H图。 9 例如：著名的彼德森图是非H图，但它满足定理1的 不等式

彼得森是一位出色的名教师。他讲课遇到推理因难时， 总是说：“这是显而易见的”，并让学生自己查阅他的著 作。同时，他是一位有经验的作家，论述问题很形象，讲 究形式的优雅。 1891年，彼得森发表了一篇奠定他图论历史地位的长 达28页的论文。这篇文章被公认是第一篇包含图论基本结 论的文章。同时也是第一次在文章中使用“图”术语。 1898年，彼得森又发表了一篇只有3页的论文，在这篇 文章中，为举反例构造了著名的彼得森图

彼得森是一位出色的名教师。他讲课遇到推理困难时， 总是说：“这是显而易见的”，并让学生自己查阅他的著 作。同时，他是一位有经验的作家，论述问题很形象，讲 究形式的优雅。 1891年，彼得森发表了一篇奠定他图论历史地位的长 达28页的论文。这篇文章被公认是第一篇包含图论基本结 论的文章。同时也是第一次在文章中使用“图”术语。 1898年，彼得森又发表了一篇只有3页的论文，在这篇 文章中，为举反例构造了著名的彼得森图