哈密尔顿图的判定及应用毕业论文(编辑修改稿)

哈密尔顿图的判定及应用毕业论文(编辑修改稿)内容摘要：

一个图假如含有哈密尔顿回路，则这个图就是哈密尔顿图。 哈密尔顿图的集中判定方法 那么当我们拿到一个图的时候，怎么样去判断它是不是一个哈密尔顿图呢。 如果是一个顶点较少的图，那么有时候我们可以通过简单的尝试和错误的方法来判定。 但是当顶点较多、通路较复杂的情况下，这种方法就会让我们感到焦头烂额，同时准确率也会大大下降。 于是很多数学家开始尝试找到一种判定哈密尔顿的充分必要条件。 遗憾的是至今为止还没有一种判定的充分必要条件，事实上，想要找到一个完全充分适用的判定方法几乎是没有可能的。 但是数学家们依然没有放弃寻找一种简单的判定哈密尔顿图的方法，这就形成了图论上一个著名的哈密尔顿问题。 虽然目前得到的判定方法大多是 存在一些充分不必要或者必要不充分的条件 ，但是对于平时问题的解决和简单的应用来说，在很多时候还是能起到简单判定的作用。 下面 将解析几种相对好的方法：由于 对 于 任意一个图来说 ， 如果它是哈密尔顿图，它的基础简单图 一定 是哈密尔顿图，所以 在判定的时候 我们只要考虑简单图。 狄拉克定理 和奥勒定理 最早提出判定哈密尔顿图的是 英国的数学家狄拉克。 狄拉克定理需要做的是记录每个顶点 X 上有多少条通路，记通过顶点 X 的通路个数为 D(X)，当图的每个的顶点的 D(X)相当大时，这个图就是哈密尔顿图。 定理 1（ 狄拉克定理）： 对于 任意给定的一个图，如果这个图的顶点数 3n ，而且 ( ) n/ 2DX ， 那么这个图就是哈密尔顿图。 狄拉克发现上述定理的八年后，经过不断的尝试和总结，著名的美国图论学家奥斯坦奥勒继续了狄拉克的工作，推广了狄拉克定理，得到了一个判定哈密尔顿图的基础结论，为后面的研究打开了一个方向。 定理 2（奥勒定理） ： 对于任意给定的一个图，如果这个图的顶点数 3n ， 对于任意的两个顶点 x、 y有 ( ) ( )D x D y n，那么这个图一定是哈密尔顿图。 博萨定理 和萨瓦达定 理 5 在奥勒定理被发现以后，一个叫博萨德的匈牙利少年 用一篇仅有一页长的论文对奥勒定理 进行了推广，得到了一个重要的定理，引起了数学界的广泛关注。 为了能更好的理解博萨定理的结论，我们可以引入一些记号：对于 任意的一个图 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= „ 、 n， j= „ 、 n，都满足 xi≥ yj。 例如： X=（ 1， 2， 3， 4）； Y=（ 5， 6， 7， 8）； Z=（ 6， 4， 5， 3）。 我们可以得到 Y≥ X,但是 Z≥ X却是错误的。 然后我们定义每一个 3n 的的整数得到一个序列 P(n)： 当 n 是奇数时，我们可以将 P(n)定义成整数列： P(n)=（ 1,2,3,4， „ ， n52 ， n32 ， n12 ， n12 ， n+12 ， „ ， n+12 ），一共包含n个数。 当 n 是偶数时，我们可以将 P(n)定义成整数列： P(n)=（ 1,2,3,4， „ ， n 22 ， n12 ， n2 ， n2 ， „ ， n2 ） 一 共包含 n 个数。 根据定义我们可以得到： 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（ 博 萨定理），任意一个 3n 的图，它的 D(G)满足关系式有 D(G)≥ P(n),那么图 G就是哈密尔顿图。 博萨定理解决了很大一部分的哈密尔顿图的判定问题，但是依然还存在一定的问题，不满足博萨定理的图不一定不是哈密尔顿图，很多人不断思索如何改进，很多数学家提出了很多种改进方案，但是经过比较之后，捷克的数学家萨瓦达的结论脱颖而出。 目前为止，萨瓦达定理依旧是一种较好的哈密尔顿图的判定方法。 他的结论如下。 定理 4（萨瓦达定理）任意一个 3n 的图 G，且 D(G)=（ a1,a2,„ ,an）满足鞋面的条件：对于每一个小于 n2 的整数 i 的两个不等式 a1≥ i+1， an1≥ ni，至少 6 有一个是成立的，那么图 G就一定是哈密尔顿图。 补充的一个必要定理 萨瓦达定理对哈密尔顿图的判定做出了很大的改进，让我们又多了一种简单的方法，但是依然存在哈密尔顿图不满足萨瓦达定理。 这个时候我们需要用到一个哈密尔顿图的必要条件。 这个条件叙述如下： 定理 5（一个判定的必要条件） ：设一个无向 图 G=(V,E)是一个哈密尔顿图， V1是 V 的一个非空子集，则有 P(GV1)≤ |V1|。 其中 P(GV1)表示从 G 中删除 V1得到的连同分支数。 这个条件的必要性可以由一下方法证明： 证明 ：假设 C是图 G中的一条哈密尔顿回路。 若 V1 当中的顶点是在 C上彼此相邻的顶点，那么显然有： P(CV1)=1≤ |V1|； （ 2） 若 V1 中的顶点是在 C上存在 m个互不相邻，那么 就有： P(CV1)=m≤ |V1| 所以无论 V1 中的顶点在 C 上是相邻或是不相邻，或者兼有，都可以得到结论 P(CV1)≤ |V1| 同时由于 C 是图 G的生成子图，所以可以得到： P(CV1)≤ P(GV1) ≤ |V1| 一般时候定理 5 可以用来判定一个图是非哈密尔顿图。 判定哈密尔顿图的方法还有很多，但是最为常用的就是上述的五种方法，当然，时至今日，不乏有比这五种方法更为准确全面的方法，但是在这里就不一一介绍了。 实例 解析 为了能够让读者更好的了解前文介绍的几种方法，下面举几个实例来进行验证。 图 21：图 G G2 在上图中的两个图 G G2 可以简单的应用定理 1（狄拉克定理）得到， G1中的每个顶点 x 都有 D(x)=3，而 n=4，所以有 D(x)=3≥ 4/2=2。 同样图 G2 中， 7 任何一个顶点都有 D(x)=4，而 n=6，所以有 D(x)=3≥ 6/2=3。 由此可以判定图 GG2是哈密尔顿图。 这两个图的判定同样可以应用奥勒定理 进行判定 ，在图 G1 中任意两点 x、 y，有 D(x)+D(y)=6≥ 4；在图 G2 中任意两点 x、 y，有 D(x)+D(y)=8≥ 6，同样可以判定图 G G2 是哈密尔顿图。 图 22：图 G G4 为了更好的体现 博萨定理和萨瓦达定理的优越性，可以使用图 G3 来进行比较。 应用 狄拉克定理时， 明显 n=5 且 D(x)=2≤ 5/2=n/2，不能判 定它是哈密尔顿图。 同样 使用奥勒定理时 min（ D(x)+D(y)） =4≤ 5/2=n/2，也不能判定。 但是简单的观察就可以发现图 G3 是一个哈密尔顿图。 这个时候我们就可以。