9.3 哈密尔顿图

哈密顿图十二面体中的哈密顿路径哈密顿图（英语：Hamiltonian path，或Traceable path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。

在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶的路径称作哈密顿路径。

美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。

哈密尔顿回路问题与欧拉回路类似。

它是1859年哈密尔顿首先提出的一个关于12面体的数学游戏：能否在图10.4.9中找到一个回路，使它含有图中所有结点一次且仅一次？若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地呢？为此，这个问题也被称作周游世界问题（10.4.9）对图10.4.9 ，图中粗线给出了这样的回路。

定义10.4.3 给定图G，若有一条路通过G中每个结点恰好一次，则这样的路称为哈密尔顿路；若有一个圈，通过G个每个结点恰好一次，这样的圈称为哈密尔顿回路（或哈密尔顿圈）。

具有哈密尔顿回路的图称为哈密尔顿图。

尽管哈密尔顿回路与欧拉回路问题在形式上极为相似，但是到目前为止还不知道一个图为哈密尔顿图的充要条件，寻找该充要条件仍是图论中尚未解决的主要问题之一。

下面先给出一个简单而有用的必要条件。

定理10.4.4 设图G＝〈V ,E〉是哈密尔顿图，则对于V的每个非空子集S，均有W（G－S）≤|S| 成立，其中W（G－S）是图G－S的连通分支数。

证明: 设α是G的哈密尔顿回路，S是V的任一非空子集。

在G－S中，α最多被分为|S|段，所以W（G－S）≤|S|利用本定理可判别某些图不为哈密尔顿图。

如在图10.4.10中，若取S＝｛v1，v4｝，则G－S有3 个连通分支，故该图不是哈密尔顿图。

哈密尔顿图的判定及应用论文引导语：哈密尔顿图的研究是图论中不可或缺的一部分，这个问题的研究已经应用到了各个领域。

合理的利用哈密尔顿图的结论，不仅可以节约大量的时间，更可以降低发展的成本。

因此很多学者致力于哈密尔顿图的问题研究，也得到了很多了不起的突破。

1 引言在查阅了大量资料后，可以发现哈密尔顿图在数学理论研究和现实应用中都具有重要的地位。

哈密尔顿图的研究解决了大量的问题，但是还是有很多的问题还未得到解决。

其中较为著名的就是关于货郎担问题的解决方案，至今还没有很好的答案。

本文在综合了各种哈密尔顿图的判定方法之后，尝试用多种方法去解决货郎担问题，在比较后，找到一种相对较好的方法，也为将来的继续研究提供研究方向。

1.1 哈密尔顿图的起源哈密尔顿(Hamilton)是一位出生在爱尔兰的天文学家和数学家. 他的一生是很丰富多彩的，自从他发现“四元数”后，他又发现了另一种称之为“The Icosian Calculus”的代数系统，这个系统包含有乘法和加法的运算算子，但是乘法并不满换律(即xy-yx这个规律)。

他发现的这个代数系统是和正则12 面体有关的。

于是在1859 年他提出下列周游世界的游戏:在正十二面体的二十个顶点上依次标记伦敦、巴黎、莫斯科、华盛顿、北京、东京等世界著名大城市; 正十二面体的棱( 边) 表示连接这些城市的路线。

问: 能否在图中做一次旅行,从顶点到顶点, 沿着边行走, 经过每个城市恰好一次之后再回到出发点?曾经有很多人不断追寻这个游戏的答案。

可以应用拓扑的思想，将这正十二面体“拉平”将会得到一个和它同构的平面图(如图1-1)，这样进行就可以将这个游戏转化为：要求必须沿着正十二面体的棱，怎样才能走完正则十二面体上的所有顶点，而且最后又回到起点的问题。

图1-1：哈密尔顿周游世界图从此人们将这类图称作哈密尔顿图，哈密尔顿图的研究也开始慢慢建立起来。

1.2 研究背景和意义哈密尔顿图是图论的重要的一部分，随着数学和科学技术的蓬勃发展，它的应用已经渗透到自然科学、社会科学的各个领域。

哈密尔顿图的充分必要条件摘要图论在现实生活中有着较为广泛的应用, 到目前为止,哈密尔顿图的非平凡充分必要条件尚不清楚,事实上,这是图论中还没解决的主要问题之一,但哈密尔顿图在实际问题中,应用又非常广泛,因此哈密尔顿图一直受到图论界以及运筹学学科研究人员的大力关注.关键词:哈密尔顿图;必要条件;充分条件;1 引言 (4)2 哈密尔顿图的背景 (4)3 哈密尔顿图的概念 (5)4 哈密顿图的定义 (6)4．1定义 (6)4．2定义 (6)4．3哈密顿路是遍历图的所有点。

(7)4 哈密尔顿图的充分条件和必要条件的讨论 (8)5 结论 (9)参考文献 (9)指导老师 (10)1 引言图论是一门既古老又年轻的学科,随着科学技术的蓬勃发展,它的应用已经渗透到自然科学以及社会科学的各个领域之中,利用它我们可以解决很多实际生活中的问题,给你一个图,你怎么知道它是否是哈密尔顿图呢?当然如果图的顶点不多,你可以用最古老的”尝试和错误”的方法试试找哈密尔顿回路就可以解决和判断.但是,数学家们并不满足这样的碰得焦头烂额后才找到的真理方法.是否存在一组必要和充分的条件,使得我们能够简单轻易地判断一个图是否是哈密尔顿图?有许多智者通过各种方式去尝试过了,遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件.虽然有些充分非必要或必要非充分条件,但大部分还是采用尝试的办法,不过这些条件也是非常有用的.2 哈密尔顿图的背景美国图论数学家奥在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。

闭合的哈密顿路径称作哈密顿圈，含有图中所有顶的路径称作哈密顿路径.1857年，哈密尔顿发明了一个游戏(Icosian Game).它是由一个木制的正十二面体构成，在它的每个棱角处标有当时很有名的城市。

游戏目的是“环球旅行”。

为了容易记住被旅游过的城市，在每个棱角上放上一个钉子，再用一根线绕在那些旅游过的城市上(钉子),由此可以获得旅程的直观表示(如图1)。

13.2 哈密顿图13.2.1哈密顿图的定义与欧拉回路类似的是哈密顿回路问题。

它是1859年哈密顿首先提出的一个关于12面体的数学游戏：能否在下图中找到一个回路，使它含有图中所有结点一次且仅一次？若把每个结点看成一座城市，连接两个结点的边看成交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地呢？为此，这个问题也被称为周游世界问题。

定义13.3给定图G，若存在一条路经过图中的每一个结点恰好一次，这条路称作哈密顿（Hamilton）路。

若存在一条回路，经过图中的每一个结点恰好一次，这个回路称作哈密顿回路。

具有哈密顿回路的图称为哈密顿图。

具有哈密顿路但不具有哈密顿回路的图称为半哈密顿图。

(a)(b)(c)（a）中存在哈密顿路，不存在哈密顿回路，所以（a）是半哈密顿图，（b）中存在哈密顿回路，（b）是哈密顿图，（c）不是哈密顿图。

13.2.2哈密顿图的判定定理13.3（哈密顿回路的必要条件）若图G=<V, E>具有哈密顿回路，则对于结点集V的每一个非空子集S均有W(G−S)≤|S|成立。

其中W(G−S)是G−S中连通分支数。

定理13.4（奥尔定理，哈密顿路的充分条件）设G是具有n个结点的简单无向图，如果G中每一对不相邻顶点的度数之和大于等于n−1，则在G中存在一条哈密顿路。

例13.2某地有5个风景点。

若每个景点均有两条道路与其他景点相通，问是否可经过每个景点恰好一次而游完这5处？解将景点作为结点，道路作为边，则得到一个有5个结点的无向图。

由题意，对每个结点vi，有。

则对任意两点均有可知此图一定有一条哈密顿路，本题有解。

小结（1）深刻理解哈密顿图及半哈密顿图的定义；（2）分清哈密顿图的必要条件和充分条件，会用哈密顿图的必要条件证明某些图不是哈密顿图。

关于哈密顿图的思维形式注记图如图所示。

哈密顿图的判定方法哈密顿图的判定方法是指用来判断一个图是否是哈密顿图的方法。

哈密顿图是指一个图的所有顶点之间，每两个顶点之间只有一条路径，且路径上的边数正好为顶点数减一的图。

哈密顿图具有很多有用的性质，如旅行商问题、图论中最小连通子图等。

因此，判定一个图是否为哈密顿图是一个重要的问题。

哈密顿图的判定方法主要有以下两种：1.构造法：构造法是一种最直接也是最常用的判定哈密顿图方法。

对于一个有n个顶点的图G=(V,E)，判定它是否为哈密顿图的步骤如下：（1）构造一个新的n个顶点的图G'=(V',E')，其中V'=V，E'=∅。

（2）从G中选择一个顶点v1，将它加入到G'中，然后从G中选择v1的一个邻接顶点v2，把它也加入到G'中，同时把v1到v2之间的边加入到G'中，如此继续，直到G'中的顶点数达到n为止。

（3）若G'中的边数等于n-1，则说明G是一个哈密顿图；若不等于n-1，则说明G不是一个哈密顿图。

构造法有一个缺点，就是在构造过程中，如果构造的路径已经存在，会重复构造，浪费时间。

2.检验法：检验法是指先对给定的图进行检验，看看它是否为哈密顿图，而不是像构造法那样去构造它。

检验法的精髓就是要检验每个顶点的度数，即每个顶点有多少条边指向它，如果有多于一个顶点的度数大于等于n，则说明这个图不是一个哈密顿图。

否则，如果每个顶点的度数都小于n，则说明这个图是一个哈密顿图。

总之，哈密顿图的判定方法主要有构造法和检验法两种，构造法是最直接也是最常用的方法，但构造过程中会有重复构造而浪费时间；而检验法则是先对给定的图进行检验，看它是否为哈密顿图，其精髓是要检验每个顶点的度数。

定义4.3.1 经过图G 的每个顶点恰一次的路称为G 的Hamilton 路，简称为H 路。

经过图G 的每个顶点恰一次的圈称为G 的Hamilton 圈，简称为H 圈。

具有Hamilton 圈的图称为Hamilton 图，简称为H 图。

Hamilton 图的研究起源于一种十二面体上的游戏。

1857 年，爱尔兰著名数学家William Rowan Hamilton 爵士（他也是第一个给出复数的代数描述的人）制作了一种玩具，它是一个木制的正十二面体，在正十二面体的每个顶点上有一个木栓，并标有世界著名城市的名字。

游戏者用一条细线从一个顶点出发，设法沿着十二面体的棱找出一条路，通过每个城市恰好一次，最后回到出发点。

这个游戏当时称为Icosian 游戏，也称为周游世界游戏。

将正十二面体从一个面剖开并铺展到平面上得到的图形如下图所示，称为十二面体图。

周游世界游戏用图论术语来说就是判断十二面体图是否Hamilton 图，并设法找出其Hamilton 圈。

其中一条Hamilton 圈如图中粗边所示。

十二面体图是H 图判断一个图是否Hamilton 图与判断一个图是否Euler 图似乎很相似，然而二者却有本质的不同。

目前为止尚没有找到判别一个图是否是Hamilton 图的有效充要条件。

这是图论和计算机科学中未解决的重要难题之一。

本节给出一些经典的充分条件和必要条件。

一、必要条件定理 4.3.1 设G 是二部图，若G 是H 图，则G 必有偶数个顶点。

证明：设G = (X, Y ) ，由于G 的边全在X 和Y 之间，因此如果G 有Hamilton 圈C，则G的所有顶点全在C 上，且必定是X 的点和Y 的点交替在C 上出现，因此G 必有偶数个顶点。

证毕。

这个定理给出了一个二部图不是Hamilton 图的简单判断条件：如果一个二部图有奇数个顶点，则它必定不是Hamilton 图。

例如，下列Herschel 图是二部图，但有奇数个顶点，故不是H 图。

哈密尔顿图在实际中的应用
哈密尔顿图，也常被称为哈密尔顿圆，是按照所有学习进程中每段学习内容的
顺序进行组织的复杂图形，它具有非常强大的图形分析功能，能够有效地展示高校的课程结构与学习任务关系，为高校课程制定、教学设计及学习成功率分析等提供重要的参照依据，在高校和高等教育领域有着广泛的应用价值。

以深切的视角看待学生学习和获得教育，高校才能让学生受益良多，然而无论
学生如何学习，各门课程之间总是有某种相关性，而高校教育模式却没有很好地体现出这种相关性，哈密尔顿图能够聚焦这种相互作用，将各门课程链接起来，从而形成一种完整、精确、理性的大系统，为高校更有效地提升教育质量给出了多样的选择。

因此，在各个领域的高校和高等教育中，以哈密尔顿图的方式实施的学习模式
十分重要。

哈密尔顿图结合了内容、练习、考核等内容，将课程组织化，帮助学生就学习状态、学习方式、学习绩效进行定位和评估，不仅能够提升学生的学习效果，而且可以有效地检验高校教学管理模式。

此外，哈密尔顿图还能够帮助教育工作者有针对性的进行课程评估，重视学习个体差异、教学系统性以及推动学习创新的实践，从而改善和优化高校和高等教育的整体教学管理，确保学生的学习质量。

综上，哈密尔顿图有着多方面的实用价值，加强高校课程结构与学习模式的连接，形成强大的图形分析功能，为高校及高等教育服务，让学生拥有受益一生的学习质量，最终提升高等教育的可持续发展。