迷茫的旅行商图哈密尔顿性.ppt

迷茫的旅行商 —— 图的哈密尔顿性 * 1、背景 (一)、哈密尔顿图的概念 * * 2、哈密尔顿图与哈密尔顿路 定义1 如果图G的一个圈C含有G的所有顶点，则称C为图G的哈密尔顿圈, 简称哈圈或者H-圈。 定义2 如果图G的一条路P含有G的所有顶点，则称P为图G的哈密尔顿路, 简称哈路或者H-路。 u v 定义3 如果图G含有哈密尔顿圈，则称G为哈密尔顿图 例1、正十二面体是H图。 例2 下图G是非H图。 图G u v (二)、性质与判定 1、性质 证明：设C是G的H圈，则对V(G)的任意非空子集S, 容易知道: 所以，有： * 注：不等式为G是H图的必要条件，即不等式不满足时，可断定对应图是非H图。 证明：取S=｛u, v, w｝,则有： 所以由定理1知，G为非H图。 * 例3 求证右图是非H图。 注意：满足定理1不等式的图不一定是H图。 * 例如：著名的彼德森图是非H图，但它满足定理1的不等式。 彼得森是一位出色的名教师。他讲课遇到推理困难时，总是说：“这是显而易见的”，并让学生自己查阅他的著作。同时，他是一位有经验的作家，论述问题很形象，讲究形式的优雅。 1891年，彼得森发表了一篇奠定他图论历史地位的长达28页的论文。这篇文章被公认是第一篇包含图论基本结论的文章。同时也是第一次在文章中使用“图”术语。 1898年，彼得森又发表了一篇只有3页的论文，在这篇文章中，为举反例构造了著名的彼得森图。 * 2、判定 图的H性判定是NP-困难问题。到目前为止，有关的定理有300多个，但没有一个是理想的。拓展H图的实用特征仍然被图论领域认为是重大而没有解决的问题。 图的哈密尔顿问题和四色问题被谓为挑战图论领域150年智力极限的总和。三位数学“诺奖”获得者Erd?s、Whitney 、 Lovász 以及Dirac、Ore等在哈密尔顿问题上有过杰出贡献。 下面，介绍一个著名的定理。 * 那么G是H图。 * 所以，在G中存在起点为u而终点为v的H路P。 不失一般性，设起点为u而终点为v的H路P为： v=vn vn-1 vi+1 vi v3 v2 u=v1 P 令： *