哈密尔顿图的判定及应用论文

时间：2021-03-18 10:04:30 论文我要投稿

哈密尔顿图的判定及应用论文

　　引导语：哈密尔顿图的研究是图论中不可或缺的一部分，这个问题的研究已经应用到了各个领域。合理的利用哈密尔顿图的结论，不仅可以节约大量的时间，更可以降低发展的成本。因此很多学者致力于哈密尔顿图的问题研究，也得到了很多了不起的突破。

哈密尔顿图的判定及应用论文

　　1 引言

　　在查阅了大量资料后，可以发现哈密尔顿图在数学理论研究和现实应用中都具有重要的地位。哈密尔顿图的研究解决了大量的问题，但是还是有很多的问题还未得到解决。其中较为著名的就是关于货郎担问题的解决方案，至今还没有很好的答案。本文在综合了各种哈密尔顿图的判定方法之后，尝试用多种方法去解决货郎担问题，在比较后，找到一种相对较好的方法，也为将来的继续研究提供研究方向。

　　1.1 哈密尔顿图的起源

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

　　他发现的这个代数系统是和正则12 面体有关的。于是在1859 年他提出下列周游世界的游戏:

　　在正十二面体的二十个顶点上依次标记伦敦、巴黎、莫斯科、华盛顿、北京、东京等世界著名大城市; 正十二面体的棱( 边) 表示连接这些城市的路线。问: 能否在图中做一次旅行,从顶点到顶点, 沿着边行走, 经过每个城市恰好一次之后再回到出发点?曾经有很多人不断追寻这个游戏的答案。可以应用拓扑的思想，将这正十二面体“拉平”将会得到一个和它同构的平面图(如图1-1)，这样进行就可以将这个游戏转化为：要求必须沿着正十二面体的棱，怎样才能走完正则十二面体上的所有顶点，而且最后又回到起点的问题。

　　图1-1：哈密尔顿周游世界图

　　从此人们将这类图称作哈密尔顿图，哈密尔顿图的研究也开始慢慢建立起来。

　　1.2 研究背景和意义

　　哈密尔顿图是图论的重要的一部分，随着数学和科学技术的蓬勃发展，它的应用已经渗透到自然科学、社会科学的各个领域。然而其发展的时间并不长，所以还有很多的地方有待改进。

　　其在货郎担问题的研究上，更是进几十年才受到重视，然而他的应用却是非常广泛的，同样的方法，可以用以地震搜救，粮食分派，粮食运输，外出旅游等类似的各个方面。不仅能降低资源浪费，还可以最大化成果，对于受困的群众，多一分钟就可以多一分生存的希望。

　　研究哈密尔顿图的判定不仅仅在数学和科学领域具有很高的的研究价值，在现实应用中更是可以得到有价值的结果。因此，本文的研究方向是很具有现实意义。

　　1.3 哈密尔顿图判定方法的发展

　　1952年英国数学家狄拉克最早提出了判定哈密尔顿图的充分条件， n 阶连通图G, 若δ≥n/ 2, 则G 是哈密尔顿图。为哈密尔顿图的发展奠定了基础。

　　8年后即1960年美国著名的图论专家奥斯坦·奥勒推广狄拉克的工作，得到了更为广泛的结果--奥勒定理。：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。

　　1962年，匈牙利的一个叫博萨的少年发表了仅有一页长的论文，虽然论文很短，只有仅仅一页，但其结果却推广了奥勒定理。有一个n≥3的图G，它的D(G)满足不等式D(G)≥P(n)，那么图G就是哈密尔顿图。

　　这一结果无疑是非常具有价值的，所以在当时引起了很多的关注.在之后的几年中，很多人都尝试改进他的工作，使其有一个系统清晰的结果，最后终于有一个捷克的青年数学家萨瓦达得到了比他更为完整的结论。有一个n≥3的图G，而且D(G)=(a1,a2,...an)满足条件对于任何一个小于n/2的正整数i的不等式a1≥i+1，an-1≥n-i最少有一个是成立的那么图G就是哈密尔顿图。

　　1995 年赵俊和宋序平只研究了3 连通图( 还遗留2 连通的情况) 的邻域并条件N C+ δ≥n 的哈密尔顿连通图, 得到:

　　3 连通n 阶图G, 若N C+ δ≥n, 则是哈密尔顿连通图或例外图。

　　2001年2月广西大学计算机与信息工程学院的罗示丰提出了一种判别哈密第2 步: 找出图G = ( V, E) 度数最大的顶点X k; 第3 步: 删去X k 以及与

　　X k 关联的所有边; 第4 步: V←V-{X k} , E←E-{边与X k关联的边} ,

　　第2 步。这种方法为计算机的判别提供了一个清晰的方向。

　　时至今日，无论国内还是国外都已经发现了哈密尔顿图的'巨大作用，很多研究者也把目光放在了哈密尔顿图的判定问题的解决上，相信不久的将来，就会有更加重大的突破。

　　1.4 本文的研究方向

　　从哈密尔顿图的问题出现以来，无数的学者进行了多方面的研究，也发现了无数哈密尔顿图的性质，从而对其进行判定。然而问题的复杂性让我们的研究时间还是显得非常的短暂，哈密尔顿图的判定问题至今也没有一个确定的最好的方法。而根据哈密尔顿图的判定条件的不同，选用的方法也不尽相同。

　　本文主要介绍哈密尔顿图判定的狄拉克定理、奥勒定理、博萨定理、萨瓦达定理。对这些定理进行详细的介绍及实例演示。在这些演示的基础上，再补充定理，以完善这些定理中的缺陷。最后将这些方法应用到著名的货郎担问题上来进行应用。在本文中其他定理及应用由于篇幅原因就不一一赘述了。

　　2 哈密尔顿图的判定

　　2.1 哈密尔顿图的定义

　　设G 是一个图，包含图G中的每个顶点的路就称为哈密尔顿路。通过图G 中每个顶点有且仅有一次的通路就称为哈密尔顿通路。通过图G中的每个顶点有且仅有一次的回路就称为哈密尔顿回路。一个图假如含有哈密尔顿回路，则这个图就是哈密尔顿图。

　　2.2 哈密尔顿图的集中判定方法

　　那么当我们拿到一个图的时候，怎么样去判断它是不是一个哈密尔顿图呢?如果是一个顶点较少的图，那么有时候我们可以通过简单的尝试和错误的方法来判定。但是当顶点较多、通路较复杂的情况下，这种方法就会让我们感到焦头烂额，同时准确率也会大大下降。于是很多数学家开始尝试找到一种判定哈密尔顿的充分必要条件。遗憾的是至今为止还没有一种判定的充分必要条件，事实上，想要找到一个完全充分适用的判定方法几乎是没有可能的。但是数学家们依然没有放弃寻找一种简单的判定哈密尔顿图的方法，这就形成了图论上一个著名的哈密尔顿问题。

　　虽然目前得到的判定方法大多是存在一些充分不必要或者必要不充分的条件，但是对于平时问题的解决和简单的应用来说，在很多时候还是能起到简单判定的作用。下面将解析几种相对好的方法：由于对于任意一个图来说，如果它是哈密尔顿图，它的基础简单图一定是哈密尔顿图，所以在判定的时候我们只要考虑简单图。

　　2.2.1 狄拉克定理和奥勒定理

　　最早提出判定哈密尔顿图的是英国的数学家狄拉克。狄拉克定理需要做的是记录每个顶点X上有多少条通路，记通过顶点X的通路个数为D(X)，当图的每个的顶点的D(X)相当大时，这个图就是哈密尔顿图。

　　定理1(狄拉克定理)：对于任意给定的一个图，如果这个图的顶点数n≥3，而且D(X)≥n/ 2，那么这个图就是哈密尔顿图。

　　狄拉克发现上述定理的八年后，经过不断的尝试和总结，著名的美国图论学家奥斯坦·奥勒继续了狄拉克的工作，推广了狄拉克定理，得到了一个判定哈密尔顿图的基础结论，为后面的研究打开了一个方向。

　　定理2(奥勒定理)：对于任意给定的一个图，如果这个图的顶点数n≥3，对于任意的两个顶点x、y有D(x)+D(y)≥n，那么这个图一定是哈密尔顿图。

　　2.2.2 博萨定理和萨瓦达定理

　　在奥勒定理被发现以后，一个叫博萨的匈牙利少年用一篇仅有一页长的论文对奥勒定理进行了推广，得到了一个重要的定理，引起了数学界的广泛关注。

　　为了能更好的理解博萨定理的结论，我们可以引入一些记号：对于任意的一个图G，x1,x2,,xn 在这里分别表示图G的所有顶点，且序列数是由小到大排列的，我们用D(G)表示序列(D(x1),D(x2),,D(xn)),即存在关系有D(x1)≤D(x2) ≤≤D(xn)。再假设有两个序列其具有相同个数的数字：

　　X=(x1，x2，，xn);

　　Y=(y1，y2，，yn)。

　　我们用X≥Y表示当且仅当对于每一个i=1、2、、n，j=1、2、、n，都满足xi≥yj。

　　例如：X=(1，2，3，4);

　　Y=(5，6，7，8);

　　Z=(6，4，5，3)。

　　我们可以得到Y≥X,但是Z≥X却是错误的。

　　然后我们定义每一个n≥3的的整数得到一个序列P(n)：

　　当n是奇数时，我们可以将P(n)定义成整数列：

　　n-5n-3n-1n-1n+1n+1P(n)=(1,2,3,4，，，，，，，，)，一共包含222222n个数。

　　当n是偶数时，我们可以将P(n)定义成整数列：

　　nnnnnP(n)=(1,2,3,4，，-2，-1，，，，)一共包含n个数。 22222

　　根据定义我们可以得到：

　　P(3)= (1，2，2);

　　P(4)= (1，2，2，2);

　　P(5)= (1，2，2，3，3);

　　P(6)= (1，2，3，3，3，3);

　　P(7)= (1，2，3，3，4，4，4);

　　P(8)= (1，2，3，4，4，4，4，4);

　　有了上面这些基础说明，我们就能很清楚的阐述博萨的重要发现了：

　　定理3(博萨定理)，任意一个n≥3的图，它的D(G)满足关系式有D(G)≥P(n),那么图G就是哈密尔顿图。

　　博萨定理解决了很大一部分的哈密尔顿图的判定问题，但是依然还存在一定的问题，不满足博萨定理的图不一定不是哈密尔顿图，很多人不断思索如何改进，很多数学家提出了很多种改进方案，但是经过比较之后，捷克的数学家萨瓦达的结论脱颖而出。目前为止，萨瓦达定理依旧是一种较好的哈密尔顿图的判定方法。他的结论如下。

　　定理4(萨瓦达定理)任意一个n≥3的图G，且D(G)=(a1,a2,,an)满足鞋面n的条件：对于每一个小于的整数i的两个不等式a1≥i+1，an-1≥n-i，至少2

　　有一个是成立的，那么图G就一定是哈密尔顿图。

　　2.2.3补充的一个必要定理

　　萨瓦达定理对哈密尔顿图的判定做出了很大的改进，让我们又多了一种简单的方法，但是依然存在哈密尔顿图不满足萨瓦达定理。这个时候我们需要用到一个哈密尔顿图的必要条件。这个条件叙述如下：

　　定理5(一个判定的必要条件)：设一个无向图G=(V,E)是一个哈密尔顿图，V1是V的一个非空子集，则有P(G-V1)≤|V1|。其中P(G-V1)表示从G中删除V1得到的连同分支数。

　　这个条件的必要性可以由一下方法证明：

　　证明：假设C是图G中的一条哈密尔顿回路。

　　若V1当中的顶点是在C上彼此相邻的顶点，那么显然有：

　　P(C-V1)=1≤|V1|;

　　(2) 若V1中的顶点是在C上存在m个互不相邻，那么就有：

　　P(C-V1)=m≤|V1|

　　所以无论V1中的顶点在C上是相邻或是不相邻，或者兼有，都可以得到结论

　　P(C-V1)≤|V1|

　　同时由于C是图G的生成子图，所以可以得到：

　　P(C-V1)≤P(G-V1) ≤|V1|

　　一般时候定理5可以用来判定一个图是非哈密尔顿图。

　　判定哈密尔顿图的方法还有很多，但是最为常用的就是上述的五种方法，当然，时至今日，不乏有比这五种方法更为准确全面的方法，但是在这里就不一一介绍了。

　　2.3 实例解析

　　为了能够让读者更好的了解前文介绍的几种方法，下面举几个实例来进行验证。

　　图2-1：图G1、G2

　　在上图中的两个图G1、G2可以简单的应用定理1(狄拉克定理)得到，G1中的每个顶点x都有D(x)=3，而n=4，所以有D(x)=3≥4/2=2。同样图G2中，

　　任何一个顶点都有D(x)=4，而n=6，所以有D(x)=3≥6/2=3。由此可以判定图G1、G2是哈密尔顿图。

　　这两个图的判定同样可以应用奥勒定理进行判定，在图G1中任意两点x、y，有D(x)+D(y)=6≥4;在图G2中任意两点x、y，有D(x)+D(y)=8≥6，同样可以判定图G1、G2是哈密尔顿图。

　　图2-2：图G3、G4

　　为了更好的体现博萨定理和萨瓦达定理的优越性，可以使用图G3来进行比较。应用狄拉克定理时，明显n=5且D(x)=2≤5/2=n/2，不能判定它是哈密尔顿图。同样使用奥勒定理时min(D(x)+D(y))=4≤5/2=n/2，也不能判定。但是简单的观察就可以发现图G3是一个哈密尔顿图。这个时候我们就可以用博萨定理进行判定。

　　根据博萨定理有D(G3)=(2，2，3，3，4)，而P(5)=(1，2，2，3，3)，根据比较就有D(G3)≥P(5)，从而可以得到图G3是哈密尔顿图。

　　同样也可以根据萨瓦达定理来进行判定，因为n=5，所以小于n/2的i有i=1、2。

　　当i=1时，a1=2≥2=i+1，成立;

　　当i=2时，an-1=3≥3=n-i，成立;

　　同样可以判定图G3是哈密尔顿图。

　　然而博萨定理和萨瓦达定理同样是不完善的，这一点图G4给我们作出了很好的例子。在应用博萨定理时D(G4)=(3，3，3，3，3，3，3，3)，P(8)= (1，2，3，4，4，4，4，4);此时我们是不能说D(G4)≥P(8)的，没办法判定G4是哈密尔顿图。

　　萨瓦达定理也对这个问题表示无能为力，在图G4中n=8，所以小于n/2的正整数i=1、2、3。当i=3时，a1=3≥4=i+1，不成立;an-1=3≥5=n-i，不成立，此时违反萨瓦达定理，所以也不能判定G4是哈密尔顿图。

　　然而简单观察后就可以发现图G4是一个哈密尔顿图，所以博萨定理和萨瓦达定理是有一定的缺陷的。

　　图G4为我们的进一步研究提供了方向，让我们能够不断的深入。相信在不久的将来会有一种简单的方法可以帮助我们得出结论。

　　3 哈密尔顿图的判定在货郎担问题中的应用

　　3.1货郎担问题的由来和在现实中的应用

　　货郎担问题是由德国的著名数学家肯·蒙那哥在1932年提出来的，80年来一直是哈密尔顿图的应用中的最典型的例子，无数人对其进行废寝忘食的研究。这个问题可以表述为：假设一个售货员需要在n个城市之间进行销售，现在我们已经知道了这n个城市中任意的两个城市之间的距离，现在售货员需要选择一条路线使得从出发的城市开始，经过其他的城市有且仅有一次，最后回到出发点，问这个售货员应该怎么样选择路线呢。

　　将上述的问题进行数学提炼后所求的问题可以转化为，在一个加附了权值的完全图中，寻找一个权值最小的哈密尔顿回路。看似简单，但实际上却是非常复杂的问题，至今任何一种简化的解决方法都能够带来无法想象的价值。因为生活中需要遇到货郎担问题的地方实在是太多了，例如：

　　(1)当我们外出旅游的时候，提前安排好路程最短的路线，不仅可以节省交通上的成本，还可以得到更多的时间来参观。

　　(2)当地震等天灾发生时，我们需要组建搜救队伍对受灾区域进行救援，在受灾程度相近的情况下，安排合适的搜救路线，不仅可以挽回很多的经济损失，更重要的是可以挽救更多的生命。

　　(3)再假设当我们出差坐飞机时，由于各地的情况不同导致各个地方之间的价格会不一样。我们选择合适的城市顺序，可以让我们得到大幅度的节约成本。为公司创造更多的利润。

　　这类的问题还有很多，而这些问题都可以归结为货郎担问题。所以货郎担问题的研究是与生活直接相关的，是非常具有现实意义的。

　　3.2货郎担问题解决方法

　　那么到底应该怎样去解决货郎担问题呢，遗憾的是直到目前为止，虽然无数人为止奋斗，也得到了一些正确的结论，但是还是没有一种能够简单的解决哈密尔顿图的方法。美国的《管理科学》中有一篇讨论“货郎担问题”的文章，该文中提到：人类由于他的计算能力的限制，在解决货郎担问题上并不好。所以，现在人们对于这个问题的研究已经开始借助电子计算机来进行实现。1979年11月7日《纽约时报》上出现了一篇很有影响力的文章，它的标题为《苏联的发现震动数学界》，这篇文章虽然有一定的夸大成分存在，但是他所说的把货郎担问题的解决和计算机联系起来的思想确实没有错的。2001年广西大学计算机与信息工程学院的罗示丰提出了用计算机判定哈密尔顿图的方法。虽然这个方法还未应用到货郎担问题的解决上，但是却也坚定了很多人继续往这个方向研究的信心，在不久的将来这个问题一定可以获得更大的突破。

　　德国是一个非常严谨的国家，德国的波恩大学的一位数学家很好的发挥了这一特点，当他知道西德有120个有铁路穿过的城市后，就准备找到一个最短路程的回路，应该怎么样去跑。他费尽心血从铁路局找到了准确的城市间铁路的长度，把整个问题变成了一个有7140个变数，120个方程及96个不等式的线性规划问

　　题，人类的大脑已经对这样的问题表示无能为力了，最后不得不用电子计算机去算，才得到了最短的回路是6942公里。结果见图3-1。

　　图3-1：西德120个城市最短路线图

　　3.3树的搜索法

　　那么在一般情况下我们可以借用什么方法来解决货郎担问题呢?在这里介绍一种较为简单的方法--------树的搜索法。

　　为了更好的理解这个方法，在这里我们举一个例子加以说明：设共有A、B、

　　C、D、E五个城市，我们需要从A出发经过B、C、D、E四个城市有且仅有一次，最后再回到A。A、B、C、D、E五座城市之间的距离由下表进行表出：

　　图3-2：五个城市之间的连通情况

　　我们选择从点A出发，先写A(0)，0表示最初没有出发路线是的路程长度是0，然后我们可以列出下一步可能到达的城市，分别由B、C、D、E，可以得到四个节点为AB(10)、AC(20)、AD(50)、AE(70)。见图3-3。

　　图3-3：树的搜索法第一步

　　现在我们可以看到由城市B可能到达的城市有C、D、E，把节点AB(10)划掉，我们可以得到三个新的节点ABC(10+20)、ABD(10+50)、ABE(10+60)后面的20、50、60分别表示BC、BD、BE的长度，以此类推我们还可以得到的新节点有ACB(40)、ACD(70)、ACE(100)、ADB(100)、ADC(100)、ADE(80)、AEB(130)、AEC(150)、AED(100)九个节点。见图3-4。

　　图3-4：树的搜索法第二步

　　根据上述法则继续推广，就可以知道，假设是ABC的路径，那么到达C城以后，就只剩下了两种可能路径：ABCDEA和ABCEDA，于是我们划掉节点ABC(30)，得到两个新的节点ABCDEA(180)和ABCEDA(190)。以此类推，我们可以得到其他的二十二个节点ABDCEA(260)、ABDECA(190)、ABECDA(250)、ABEDCA(170)、ACBDEA(190)、ACBEDA(180)、ACDBEA(250)、ACDEBA(170)、ACEBDA(260)、ACEDBA(190)、ADBCEA(270)、ADBECA(260)、ADCBEA(250)、ADCEBA(250)、ADEBCA(180)、ADECBA(190)、AEBCDA(250)、AEBDCA(250)、AECBDA(270)、AECDBA(260)、AEDBCA(190)、AEDCBA(180)。见图3-5。

　　图3-5：树的搜索法第三步

　　根据图我们可以发现，在5个城市之间我们一共可以得到二十四条回路，其中最短的两条为ABEDCA(170)和ACDEBA(170)。由此我们得到了在五个城市之间销售的最佳路线。

　　做完这全部的工作后，我们回过头去看这个方法，可以发现在最后一步的计算时，一部分的工作是可以省略的。比如当我们找到第一条回路ABCDEA时，我们可以知道这条路径的长度是180，那么在之后的计算中，一旦发现路径的长度明显大于180，或者上一层的节点的数值已经大于180了，那么我们直接可以用“≥180”来代替具体的数值。当计算到ABEDCA这条路径时，我们发现数值是170，那么之后的数值如明显大于170，那么久可以用“≥170”来替代，这样可以节省一定的计算时间，加快得出结果的速度。

　　在上面方法展示的过程中我们可以发现，这样的搜索方法在地点数量较少的时候还比较试用，一旦地点数量达到十个，那么我们的计算量将变的吓人，甚至可以说是超过了人脑的计算能力，我们会感到十分的繁琐。如果十个地点还可以

　　勉强算出来，那么地点数量达到300个或者500个呢?那时候的计算量是我们无法想象的，而这种情况对于像中国这样的大国来说，是非常现实的问题。这个时候我们就不得不借助计算机的力量。

　　计算机到底可以提升多少的计算速度呢?一个例子能够很好的说明问题：在美国工作的华籍数学家Lin Shen及Hong Saman等人在1977年的时候用电子计算器计算得到了一个有关于318个城市的货郎担问题。这个问题一旦化成线性规划问题，那么就要处理有50403个变数的方程式及不等式，人脑对于这样的问题虽然不能说完全不能解决，但是所需要的时间将是难以想象的。而当时的Lin Shen等人借助了一台IBM的370—168式的电子计算机后，仅用了28.38分钟就得到了一个最优解，纳闷对于电子技术日新月异的今天，我们可能需要的时间已经不足一分钟。两者互相对比，让我们不得不承认，以后的发展方向将更多的借助计算机技术。

　　4 结论

　　哈密尔顿图相可以应用的范围已经越来越广阔，从工业铺路到农业灌溉，航空路线到海底勘探，从国家的发展到公司的运输，都可以用到哈密尔顿图的知识。哈密尔顿图的研究已经显得越来越重要，在效率第一的当今社会，恰当的应用哈密尔顿图的研究结果可以可以大大提高工作的效率和节约发展成本，为可持续发展提供不可或缺的支持。本文借鉴总结了大量前人的结论，着重介绍了哈密尔顿图判定上的五种方法和结论，并初步对这五种方法的应用范围进行了分类。在哈密尔顿图的应用方面，着重介绍了货郎担问题的研究。在解决方法上又介绍了树的搜索法，同时也说明了解决方法的未来发展方向。

【哈密尔顿图的判定及应用论文】相关文章：

波动图象与振动图象的综合应用练习题05-29

学年判定总结03-13