哈密尔顿图的充分必要条件

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

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

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

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

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

16
二、哈密尔顿图
例5. 证明下图中没有汉密尔顿路径。 图中，3个顶点标记为A，5个顶点 A 标记为B，相差2个，不可能存在 一条汉密尔顿路径。 B B 如果在标记过程中，遇到相邻结 点出现相同标记时，如果有一个 结点的度数为2，可在此对应边上 A A 增加一个结点，并标上相异标 A 记。 B B B B B
11
二、哈密尔顿图
定理3：若无向图G=<V,E>是哈密尔顿图， V1是V的任意非空 真子集，则 ω(G- V1)≤| V1 |。 证明：设C是G的一条哈密尔顿回路，对于V的每个非空真子集 V1有：ω(C-V1) ≤|V1|
ω(C- V1)是C删去V1中所有顶点及关联的边后所得图
的连通分支数。 又因为C - V1是G - V1的生成子图，故有
13
二、哈密尔顿图
定义3：若无向图G＝<V,E>的顶点集合V可以划分成两个子集X 和Y，使G中的每一条边e的一个端点在X中，另一个端点 在Y中，则称G为二部图或偶图。二部图可记为 G＝<X,E,Y>，X和Y称为互补结点子集。 二部图不会有自回路。
14
二、哈密尔顿图
定理4：设二部图G=<X, E, Y>，设|X|=m，|Y|=n。若m≠n，则G 必不是汉密尔顿图。 证明：方法1. 用汉密尔顿图的性质证明。 因为|X|≠|Y|，不妨设|X|<|Y|。 显然有ω(G-X)=|Y|>|X|， 这与汉密尔顿图的必要条件ω(G-X)≤|X|矛盾。 因此G必不是汉密尔顿图。
定理2：一个有向连通图具有欧拉路径，当且仅当它 的每个顶点的引入次数等于引出次数，可能 有两个顶点除外，其中一个的引入次数比它 的引出次数大1，另一个的引入次数比它的 引出次数小1。 推论： 一个有向连通图具有欧拉回路，当且仅当它 的每个顶点的引入次数等于引出次数。

非哈密尔顿图G中 存在一条从 到 的哈密尔顿链 的哈密尔顿链u 非哈密尔顿图 中，存在一条从u到v的哈密尔顿链 v1v2 … vmv
令
S={vi|[u, vi+1] ∈ E}，T={vi|[vi, v] ∈ E} ，
可知： 可知：S ∩ T= ∅，即|S ∩ T|= 0 又因为v 又因为 ∉ S ∪ T，故|S ∪ T|< n ， 所以： 所以：d(u)+d(v)=|S|+|T|=|S ∪ T|+|S ∩ T|< n 故 δ (G) ≤(d(u)+d(v))/2 < n/2 ， u v1 v2 vi vi+1 vm-1 vm 与δ (G) ≥ n/2矛盾 矛盾 故定理得证 v
货郎问题： 货郎问题：
哈密尔顿图
一个货郎要去n个城市卖货，希望开始于 最后回到v 一个货郎要去 个城市卖货，希望开始于v1，最后回到 1 个城市卖货 每两个城市之间都有一条直接通路， 的距离是W(vi,vj) 每两个城市之间都有一条直接通路，记vi到vj的距离是 问题是：如何找到一条最短路径？ 问题是：如何找到一条最短路径？ 将该问题用图论描述为： 个结点的无向完全图， 将该问题用图论描述为：G=<V,E,W>是n个结点的无向完全图， 是 个结点的无向完全图 对于V中任意三点 对于 中任意三点u, v, k，满足：W(u, v)+W(v, k) ≥ W(u,k) 中任意三点 ，满足： 求G中最短的哈密尔顿图 中最短的哈密尔顿图 至今没有精确有效的算法对货郎问题求解， 至今没有精确有效的算法对货郎问题求解，但是有若干近似算法
公务员考试中的“欧拉图”
三段论是古希腊的亚里士多德发现的推理规律， 三段论是古希腊的亚里士多德发现的推理规律，基本理论 及证明近乎完美。但在公务员的考试中， 及证明近乎完美。但在公务员的考试中，一般只考查直言 三段论，三段论是一种具有固定格式的推理形式，如： 三段论，三段论是一种具有固定格式的推理形式，

1-tough条件下哈密尔顿图的一个充分条件的开题报
告
哈密尔顿图是一种特殊的图，指包含一条经过所有节点的路径（即
哈密尔顿路径）的无向图。

而对于哈密尔顿路径的研究，则可以得到哈
密尔顿回路，即由哈密尔顿路径组成的闭合路径。

在实际应用中，哈密尔顿图在计算机科学中扮演着重要的角色，如
在旅行推销员问题、电路设计、图形路由、自动化制造等领域中都有广
泛应用。

然而，在某些情况下，哈密尔顿图的计算问题变得异常困难。

例如，在NP难问题条件下，哈密尔顿图的求解可能会变得不可行。

因此，研究哈密尔顿图的充分条件可以帮助我们理解其计算难度并找到更高效的解
决方法。

在该项目中，我们将探讨哈密尔顿图的充分条件之一：tough条件。

tough条件是由图论家F.T. Leighton于1979年首次提出的，它被定义为：
对于任意无向图G，设L(G)表示其最长路径的长度，n表示其节点数，则G满足tough条件当且仅当：
对于所有2 <= k <= n/2，有：
k <= L(G)/(n-k+1)
即对于每个k，一个由图上取任意k个节点组成的子集，不会比大于n-k+1个节点的子集短得太多。

tough条件是充分而非必要条件，即如果一个图满足tough条件，则它一定是哈密尔顿图；但如果一个图不满足tough条件，则不能确定它
是不是哈密尔顿图。

因此，我们将研究一些样例并比较它们是否满足tough条件和是否是哈密尔顿图，以更深入地理解这个条件的特性和重要性。

最后，我们将讨论tough条件的实际应用以及与其他哈密尔顿图条件的关系，以展示该充分条件对于哈密尔顿图研究的价值和意义。

②与度数为2的顶点有关的方法：如果图G中某些与度数为2的顶点的关联边构成一个初级回路，但该回路没有包含所有顶点，则此回路不是哈密尔顿回路，那么G不是哈密尔顿图。
③与哈密尔顿回路的长度有关的方法：设G=<V,E>,|V|=n, |E|=m.若G中有两两互不相邻的r个顶点 ，满足d( )>2,1≤i≤r,则至少有 条边不能在哈密尔顿回路上，能在哈密尔顿回路上的最多有m- =m+2r- 条边。当m- =m+2r- <n时，G不是哈密尔顿图。
当一个图的顶点和边都较少时，如果找到了一个哈密尔顿回路，那么就可判定它是一个哈密尔顿图;而当顶点和边较多时，我们可以判断不是哈密尔顿图，下面是几种常用方法和例子。
（1） 常用方法：
①与点割集有关的方法：如果存在G中顶点的非空真子集 使得w(G- )>| |,则G不是哈密尔顿图。特别地，如果G中有割点，则G不是哈密尔顿图；如果G中有割边，则G不是哈密尔顿图。
由定义容易知到，当n≥3时，完全图 是哈密尔顿图。
定理1当n≥3时，完全图 是哈密尔顿图。
证明：设完全图 的顶点为 ， 为连接 与 的边，其中i=1,2,…n-1, 为连接 与 的边，则回路 是哈密尔顿回路，至此，命题得证。
2.2 哈密尔顿图的性质
（1）哈密尔顿图一定是连通图。
因为哈密尔顿回路一定是初级回路，因此也一定是简单回路，这就保证了图中点与点之间的连通性。
（B）若 与 不相邻，设 与Г上的 = ， 相邻（k≥2,否则d( )+d( )≤ +l-2= -1<n-1,此与d( )+d( )≥n-1矛盾），而此时 至少与 相邻的顶点 之一相邻（否则，d( )+d( )≤k+ -2-(k-1)= -1<n-1,又矛盾）。设 与 相邻（2≤r≤k）,如图2示，于是，回路C= 过Г上的所有顶点。

离散结构哈密顿图教学目标基本要求（1）哈密顿图的定义（2）哈密顿图的充分条件与必要条件（3）哈密顿图的应用重点难点（1）哈密顿图的判定（2）哈密顿图的应用1859年提出一个名叫“周游世界”的游戏，问题是：能否遍历正12面体的每个顶点一次且仅一次后回到原地。

？哈密顿（爱尔兰数学家）定义•哈密顿通路——经过图中所有顶点一次仅一次的通路.•哈密顿回路——经过图中所有顶点一次仅一次的回路.•哈密顿图——具有哈密顿回路的图.•半哈密顿图——具有哈密顿通路且无哈密顿回路的图.•几点说明：–平凡图是哈密顿图.–哈密顿通路是初级通路，哈密顿回路是初级回路.–环与平行边不影响哈密顿性.–哈密顿图的实质是能将图中的所有顶点排在同一个圈上实例在上图中，•(1),(2) 是哈密顿图;•(3)是半哈密顿图;•(4)既不是哈密顿图，也不是半哈密顿图，为什么？哈密顿图的必要条件•定理设无向图G =<V ,E >是哈密顿图，对于任意V 1⊂V 且V 1≠∅，均有p (G −V 1) ≤|V 1|•推论设无向图G=<V ,E>是半哈密顿图，对于任意的V 1⊂V 且V 1≠∅均有p (G −V 1) ≤|V 1|+1•几点说明–定理中的条件是哈密顿图的必要条件，但不是充分条件（例如彼得松图）–由定理可知，K r ,s 当s ≥r +1时不是哈密顿图. 易知K r ,r （r ≥2）时都是哈密顿图，K r ,r +1都是半哈密顿图.哈密顿图的充分条件•定理设G是n阶无向简单图，若对于任意不相邻的顶点v,v j，均有id(v i)+d(v j) ≥n−1则G 中存在哈密顿通路.,v j，均有•推论设G为n(n≥3) 阶无向简单图，若对于G中任意两个不相邻的顶点vid(v i)+d(v j) ≥n则G中存在哈密顿回路，从而G为哈密顿图.•几点说明–定理是半哈密顿图的充分条件，但不是必要条件. 长度为n−1（n≥4）的路径构成的图不满足条件，但它显然是半哈密顿图.–推论同样不是哈密顿图的必要条件，G为长为n的圈，不满足条件，但它当然是哈密顿图.例在给出的三个图中哪些是哈密顿图？哪些是半哈密顿图？为什么？例试判断下面在给出的图是欧拉图还是哈密顿图？判断某图是否为哈密顿图至今还是一个难题.哈密尔顿图的应用例：一只蚂蚁可否从立方体的一个顶点出发，沿着棱爬行，它爬过每一个顶点一次且仅一次，最后回到原出发点？试利用图作解释。

哈密尔顿图的一个充分条件
一个哈密尔顿图中有一个充分条件，即所有顶点都必须有一条边指向它。

这意味着如果要构建一个哈密尔顿图，我们必须确保所有的顶点都有一条指向它的边。

换句话说，在哈密尔顿图中，每一个顶点必须至少有一条入边，而它不能有任何出边。

这样可以确保哈密尔顿图是没有回路的，因为如果有一条返回边，那么就会产生一个环。

此外，要构建一个哈密尔顿图，所有的顶点必须是连通的，也就是说，所有的顶点都必须可以从一个顶点到达另一个顶点，而不会有任何顶点被孤立。

这就要求在建立哈密尔顿图时，必须确保所有的顶点都存在一条路径，使得从一个顶点可以到达另一个顶点。

总之，哈密尔顿图的一个充分条件是所有顶点都必须至少有一条入边，而且所有顶点都必须是连通的。

这样，我们就可以确保哈密尔顿图是没有回路的，并且所有的顶点都可以从一个顶点到达另一个顶点。

摘
要 ： ａ ｄｅ Ｆ ｕ ｒｅ等在 １ ９ 年 得到 ＮＣ≥ ｎ一 条件下熟知的哈 密尔顿性结果 ， ９１ 其后 ， 一些论文研
究 ＮＣ ≥ 一 占的哈密尔顿图性 ． 本文进一步研究更好条件 ＮＣ≥ ｎ～ 占一 ｌ 的情 况 ， 得结论 下 所 仅 比 Ｆ ｕ ｒｅ 的结 论多 ３个结构清楚的熟悉的例外图． ａ ｄｅ 等 关 键词 ：哈密尔顿 图ｆ ２邻域并 ｆ最小度 中图分 类号 ０１ ７ ５ ５ ． 文献 标识 码 ：Ａ
其 余记号 、 念参 见文献 ［ ，］ 概 １２． １９ 年 ，ａｄｅ 等 在文献 ［］中得 到熟 知结 果 ； ９ １ Ｆ ｕ ｒｅ ３ 定理 １ ２连通 阶图 Ｇ， 口 ＮＣ≥ — ｄ 则 Ｇ是哈 密尔顿 图（ ， 简称 Ｈ 图 ） ． Ｆ ｕ ｒｅ等在 文献 ［］中还提 出下面 猜想 ： ａｄｅ ３ 猜想０ ２连通 阶图 Ｇ， ＮＣ≥ — ｄ＋ Ｉ则 Ｇ是 点泛 圈图． 若 ，
定 理 ２ｓ ２ 【 连通 ｎ阶图 Ｇ， 。 ＮＣ ≥ — ｄ 则 Ｇ是 Ｈ 图． ，
现在， 进一 步研 究改进 上面 定理 条件 的情况 ：
定 理 ３ ２连 通 阶 图 Ｇ， ＮＣ ≥ — ｄ一 １ 则 Ｇ是 Ｈ 图或 Ｇ ∈ ｛ ｃ ， Ｋ （ ｍ ＋ Ｋ（ ｍ ＋ Ｋｆ ｎ ）这 里 Ｋ２ Ｋ（ ）（ ＂仅是 ２阶 图） ． 为 了证 明定 理 ３ 需 要 下面几个 引理 ． ，
和 Ｘ＋ ， 均 不 相邻． ｛ ， ｉ “ 若 川 ， ， 中点 “ 和 川 相 邻时 ， … 五） 则 和 Ⅲ ， “均不 相 邻． 又
维普资讯
第３ ８卷 第 ２期
２ Ｏ２年 ４月 Ｏ
兰 州 大 学 学 报 （自 然 科 学 版 ）
Ｊｕ ｎ ｌ ｆＬ ｎ ｈ ｕ Ｕｎｖ ｒ ｉ Ｎａｕ ａ ｃｅ ｃ ｓ ｏ ｒ ａ ａ ｚ ｏ ｉ ｅｓｔ ｏ ｙＳＧ 分别是图 Ｇ和一点 “时， ｃ“ 表示为 Ｎ（）Ⅳｔ（）＝ 当 ， Ｎ （） ｕ， “

p(G-V1)≤V1.
其中, p(G-V1)为从G中删除V1(删除V1中 各顶点及关联的边)后所得图的连通分支 数.
证明:设C为G中的一条哈密尔顿回路. (1)若V1中的顶点在C上彼此相邻,则 p(C-V1)=1≤ V1 (2)设V1中的顶点在C上存在r(2≤r≤ V1) 个互不相邻,则 p(C-V1)= r≤V1
定理(充分条件1)设G＝<V，E>是简单无向 图。如果对任意两个不相邻的结点u， vV，均有： deg(u)+deg(v)|V|-1， 则G中存在哈密尔顿通路；
如果对任意两个不相邻的结点u， vV，均有：deg(u)+deg(v)|V|， 则G中存在哈密尔顿回路，即G是哈 密尔顿图。
例
在图中，任意两个结点的度数之和为4，结点 数为6，即有46，，但它仍然是哈密尔顿图。
定理6. G有n个顶点，m条边，如果
1 2 m （n －3n＋6） ，则G是Hamilton图。 2
证明.任取不相邻的两个顶点u，v∈G， G中去掉u，v后导出子图G’,G’有n－2个 顶点，至多 (n－2)(n－3) 条边.U,v到G’ C ＝ 2 的边数有 n －3n＋6 (n－2)(n－3) m－C － ＝n 2 2 D(u)+D(v)≥n. 由充分条件1得，G是Hamilton图。
8.3哈密尔顿图
哈密尔顿通路(回路)、哈密尔顿图
经过图中每个顶点一次且仅一次 的通路(回路)称为哈密尔顿通路 (回路).存在哈密尔顿回路的图称 为哈密尔顿图.
是不是哈密尔顿图?
图中 (1), (3),不是哈密尔顿图,(2) 为哈密尔顿图.
哈密尔顿图的判定
定理(必要条件1) 设无向图G=<V,E>是 哈密尔顿图,V1是V的任意的非空子集,

– –
(1) G的每条边在G*至多重复一次；
(2) G的每个(初级)圈在G*重复边权的和不超过该圈 权的一半。

算法过程
–
1．用Dijstra算法求所有奇度顶点对之间的最短路径。 (若G是欧拉图，直接用Fleury算法) 2．以G中所有奇度顶点构造带权完全图G2k, 每边的 权是两端点间最短路径长度。
1
2
20
17
19
18Biblioteka 义： 图G中的一圈，若它通过G中每个顶 点恰好一次，则该圈称为哈密尔顿圈，具 有哈密尔顿圈的图称为哈密尔顿无向图。 完全图必是哈密尔顿图。
从定义可知，一个图的Hamilton圈与
Euler环游是很相似的，差别在于Hamilton
圈是环游G的所有顶点圈（点不重，当然
边也不重），而Euler环游是环游G的所
道的交叉点，街道长度用相应边的权表示。 则问题的解对应于G中包含所有边的权最小 的圈，称为最优圈(注意：未必是简单圈)。 当G是欧拉图，则最优圈即欧拉圈。 若G不是欧拉图，则通过加边来消除G中的 奇度顶点，要求使加边得到的欧拉图G'中重复边
的权和最小。
C是带正权无向连通图G中的最优圈当且仅当对 应的欧拉图G*满足：
边外,,每经过G中顶点xi(包括a和b),都为顶点xi
贡献2度,而C的第一边为a贡献1度,C的最后一条
边为b贡献1度.因此,a和b的度数均为奇数,其余
结点度数均为偶数.
充分性:设连通图G恰有两个奇数度结点,
不妨设为a和b,在图G中添加一条边e={a,b} 得G’,则G’的每个结点的度数均为偶数,因 而G’中存在欧拉圈,故G中必存在欧拉路.
J K
例3 一张纸上画有如下图所示的图，你能否用剪刀 一次连续剪下图中的三个正方形和两个三角形？

「学习笔记」哈密尔顿通路哈密尔顿回路感想在有限的 OIer ⽣涯中应该再也不会去研究这种东西了。

在 OI 界太冷门了。

艹，清北学堂国庆的Day4T4好像和哈密尔顿通路有关，我是毒奶？概念哈密尔顿通路：图G中⼀条从S到T的路径不重不漏地经过了每个点，那么这条路径称为哈密尔顿通路。

哈密尔顿回路：图G中⼀条从S到S的路径不重不漏地经过了除S外每个点并且S只经过过两次，那么这条路径称为哈密尔顿回路。

哈密尔顿图：若图G中存在哈密尔顿回路则称G为哈密尔顿图。

N阶竞赛图：含有N个顶点的有向图，且每对顶点之间都有⼀条边（不限定⽅向）。

⽆向简单图：不含重边和⾃环的⽆向图。

求解⽅法求解哈密尔顿通路充分条件：设 G 是有n个点的⽆向简单图（n≥2），若G中任意不相邻的两点u,v都满⾜d(u)+d(v)≥n−1，则G有哈密尔顿通路。

是下⾯涉及到的Ore定理的推论。

可以转化成求哈密尔顿回路：枚举哈密尔顿通路的起点S和终点T，在S和T之间加⼀条边，判断是否存在哈密尔顿通路。

N(N≥2)阶竞赛图中⼀定存在哈密尔顿通路证明：很显然N=2 时成⽴（⾃⼰画图看看就⾏）。

N=k时是成⽴的，去证明N=k+1 时是成⽴的。

设N=k时存在的哈密尔顿通路为v1,v2,…,v k。

（下标只是代表在⾛的时候经过的顺序）从i=k∼1 去看v i和v k+1的联通情况。

若存在v i指向v k+1的边，那么存在v1,…,v i,v k+1,v i+1,…,v k这样⼀条通路。

否则存在v k+1,v1,v2,…,v k这样⼀条通路。

证毕。

在竞赛图中找哈密尔顿通路的代码（就是模拟上述过程）：//感觉时间复杂度是 O(n ^ 3)#include <cstdio>#include <cstring>#include <string>#include <iostream>#include <algorithm>#define M 6180int n, m, now, ans[M];bool p[M][M];void ins(int pos, int x) {int temp;++now;for (int i = pos; i <= now; ++i) {temp = ans[i], ans[i] = x, x = temp;}}void hamilton() {now = 2, ans[1] = 1;for (int i = 2; i <= n; ++i) {bool okay = false;for (int j = now - 1; j >= 1; --j) {if (p[ans[j]][i]) {okay = true;ins(j + 1, i);break;}if (!okay) ins(1, i);}}int main() {scanf("%d", &n);m = n * (n - 1) / 2;for (int i = 1, u, v; i <= m; ++i) {scanf("%d %d", &u, &v);if (u < v) p[u][v] = 1;}hamilton();for (int i = 1; i <= n; ++i) printf("%d\n",ans[i]);return 0;}求解哈密尔顿回路是个NP-完全问题，好像没什么好的求解⽅法，都是根据⼀些充分条件/必要条件去构造的鸭⼦。

必要条件的应用
举例
c
a
b
将图中点a, b, c的集合记为S, G-S有4个 连通分支,而|S|=3. G不是Hamilton图.
举例
Kh
Kh
Kn-2h
下图给出的是 C2,7的具体图 (h=2,n=7)
必要条件的局限性

必要条件只能判定一个图不是哈密尔顿图

Petersen图满足上述必要条件，但不是哈密尔顿图。
Ore定理的延伸

引理. 设G是有限图，u, v是G中不相邻的两个顶点， 并且满足：d(u)+d(v) |G|，则
G是Hamilton图 G∪{uv}是Hamilton图.

证明：类似于Ore定理的证明.

G的闭合图, 记为C(G): 连接G中不相邻的并且其度之 和不小于 |G| 的点对, 直到没有这样的点对为止.
哈密尔顿图
离散数学─图论
南京大学计算机科学与技术系
内容提要


哈密尔顿通路
哈密尔顿回路 哈密尔顿图的必要条件 哈密尔顿图的充分条件 哈密尔顿图的应用 竞赛图与有向哈密尔顿通路
周游世界的游戏

沿着正十二面体的棱寻找一条旅行路线, 通过每个顶 点恰好一次又回到出发点. (Hamilton 1857)

Hamilton回路的存在性问题
K3 K4
Kn(n3)有Hamilton回路 b a c a b c a b
c
e
d
e
d
e
d
一个基本的必要条件

如果图G=(V, E)是Hamilton图，则对V的任一非空子 集S，都有
P(G-S) |S|

15.1 欧拉图 欧拉(1707-1783)：瑞士著名的数学家。13岁进入 欧拉 ：瑞士著名的数学家。 岁进入 巴塞尔大学， 岁取得哲学硕士学位 岁取得哲学硕士学位。 巴塞尔大学，16岁取得哲学硕士学位。1736年， 年 他证明了欧拉定理， 他证明了欧拉定理，并解决了哥尼斯堡桥的问 从而成为图论的创始人。 题，从而成为图论的创始人。 定义15.1 通过图（无向图或有向图）中每一条边 通过图（无向图或有向图） 定义 一次且仅一次行遍图中所有顶点的通路称为欧 拉通路。通过图（无向图或有向图） 拉通路。通过图（无向图或有向图）中每一条 边一次且仅一次行遍图中所有顶点的回路称为 欧拉回路。具有欧拉回路的图称为欧拉图， 欧拉回路。具有欧拉回路的图称为欧拉图，具 有欧拉通路而无欧拉回路的图称为半欧拉图。 有欧拉通路而无欧拉回路的图称为半欧拉图。
16
15.欧拉图与哈密顿图 欧拉图与哈密顿图
15.2 哈密顿图
到目前为止， 到目前为止，还没有找到哈密尔顿通路存在的充 分必要条件。下面介绍一个必要定理。 分必要条件。下面介绍一个必要定理。 定理15.6：设无向图 Ｇ＝＜Ｖ ， Ｅ＞ 是哈密尔顿 Ｇ＝＜Ｖ， 定理 ： 设无向图Ｇ＝＜Ｖ Ｅ＞是哈密尔顿 图，则对V的每个非空真子集 均成立： 则对 的每个非空真子集S均成立： 的每个非空真子集 均成立 w(G-S) ≤|S| 其中， 中的顶点数， 表示G删去 其中， |S| 是S中的顶点数， w(G-S)表示 删去 中的顶点数 表示 删去S 顶点集后得到的图的连通分图的个数。 顶点集后得到的图的连通分图的个数。
9
15.欧拉图与哈密顿图 欧拉图与哈密顿图
例：用定理解决哥尼斯堡桥的问题
15.1 欧拉图
个结点为奇次数， 有４个结点为奇次数， ∴不存在欧拉回路，也不存在欧拉路径。 不存在欧拉回路，也不存在欧拉路径。 故要从一点出发经过桥一次且仅一次的路径， 故要从一点出发经过桥一次且仅一次的路径 ， 再回到出发点是不可能的。 再回到出发点是不可能的。

穿过每一道门，通过所有房间？
15.2 哈密顿图
1859年，爱尔兰数学家威廉·哈密尔顿发明 了一个旅游世界的游戏。将一个正十二面体的 20个顶点分别标上世界上大城市的名字，要求 玩游戏的人从某城市出发沿12面体的棱，通过 每个城市恰一次，最后回到出发的那个城市。
哈密尔顿游戏是在左图中如何 找出一个包含全部顶点的圈。
定义（哈密顿通路和哈密顿回路） 经过图（有向图或无向图）每个顶点一次
且仅一次的通路称为哈密顿通路。 经过图每个结点一次且仅一次的回路（初
级回路）称为哈密顿回路。 定义（哈密顿图和半哈密顿图）
存在哈密顿回路的图称为哈密顿图。 存在哈密顿通路但不存在哈密顿回路的图 称为半哈密顿图。 平凡图是哈密顿图。
由两判定定理，立即可知 （4）为欧拉图， （5）、（6）即不是欧拉图，也不是半欧拉图。
例15.2（P296） v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2
◼ Fleury算法
◼ （1）任取v0V(G)，令P0=v0。 ◼ （2）设Pi=v0e1v1e2…..eivi已经行遍，则按下面
判断所示两图是否为欧拉图、半欧拉图？
无向欧拉图与无向半欧拉图的判断方法
定理15.1（无向欧拉图的判定）无向图G是欧拉图当 且仅当G是连通图，且G中没有奇度顶点。
定理15.2（无向半欧拉图的判定）无向图G是半欧拉 图当且仅当G是连通图，且G中恰有两个奇度顶点。
（1）
（2）
（3）
有向欧拉图与有向半欧拉图的判断方法
（1）
（2）
（3）
（4）
（5）
（6）
（1）（2）（3）（4）为哈密顿图 （5）为半哈密顿图 （6）既不是哈密顿图，又不是半哈密顿图。

中国计量学院本科毕业设计（论文）哈密尔顿图的判定及应用Judgement and application of Hamiltongraph学生姓名徐杰一村学号0900801110学生专业信息与计算科学班级 09信算1班二级学院理学院指导教师陈琴中国计量学院2013年5月郑重声明本人呈交的毕业设计论文，是在导师的指导下，独立进行研究工作所取得的成果，所有数据、图片资料真实可靠。

尽我所知，除文中已经注明引用的内容外，本学位论文的研究成果不包含他人享有著作权的内容。

对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确的方式标明。

本学位论文的知识产权归属于培养单位。

学生签名：日期：分类号：O157 密级：公开UDC：62 学校代码：10356中国计量学院本科毕业设计（论文）哈密尔顿图的判定及应用Judgement and application of Hamiltongraph作者徐杰一村学号0900801110申请学位理学学士指导教师陈琴学科专业信息与计算科学培养单位中国计量学院答辩委员会主席评阅人2013年5月致谢论文的撰写工作已经基本上完成，这段时间也经历了很多的波折。

从论文开始到结束，一直是在陈琴老师的指导下完成的，可以说没有老师的悉心指导，就没有这篇论文的诞生，在此，衷心感谢陈琴老师对我的指导。

感谢老师不厌其烦的帮我修正论文中的错误，也感谢老师在我失去信心时的谆谆教诲。

陈琴老师的严谨教学，用于创新，善于发现的精神不但在学习上为我树立了榜样，也给我未来的生活带来了帮助。

再次感谢陈琴老师对我的指导！同时，也感谢理学院老师的辛勤教育，感谢所有给我帮助的同学和朋友们。

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

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

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

哈密顿图十二面体中地哈密顿路径哈密顿图（英语：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 个连通分支, 故该图不是哈密尔顿图.判断哈密尔顿图地充分条件很多, 我们仅介绍其中一个.定理10.4.5 设G＝〈V ,E〉是有n个结点地简单图,1）如果任两结点u, v∈V, 均有deg(u)＋deg(v)≥n－1,则在G中存在一条哈密尔顿路；2）如果对任两结点u, v∈V, 均有deg(u)＋deg(v)≥n,则G是哈密尔顿图. 证明略.【例10.4.3】某地有５个风景点.若每个景点均有两条道路与其他景点相通,问是否可经过每个景点恰好一次而游完这５处？解将景点作为结点,道路作为边,则得到一个有５个结点地无向图.由题意,对每个结点vi,有deg(vi)＝2（i∈Ｎ5）.则对任两点vi, vj（i, j∈Ｎ5）均有deg(vi)＋deg(vj)＝2＋2＝4＝5－1 可知此图一定有一条哈密尔顿路,本题有解.我们再通过一个例子,介绍一个判别哈密尔顿路不存在地标号法.【例10.4.4】证明图10.4.11所示地图没有哈密尔顿路.证明: 任取一结点如v1,用A标记,所有与它相邻地结点标B.继续不断地用A标记所有邻接于B 地结点,用B标记所有邻接于A地结点,直到图中所有结点全部标记完毕.如果图中有一条哈密尔顿路,则必交替通过结点A和B.因此或者结点A和B数目一样,或者两者相差１个.（10.4.11）而本题有３个结点标记A,５个结点标记B,它们相差２个,所以该图不存在哈密尔顿路.作为哈密尔顿回路地自然推广是著名地货郎担问题.问题是这样叙述地：设有一个货郎,从他所在地城镇出发去n－１个城镇.要求经过每个城镇恰好一次,然后返回原地,问他地旅行路线怎样安排才最经济？从图论地观点来看,该问题就是：在一个有权完全图中找一条权最小地哈密尔顿回路.研究这个问题是十分有趣且有实用价值地.但很可惜,至今没有找到一个很有效地算法.当然我们可以用枚举法来解,但是当完全图地结点较多时,枚举法地运算量在计算机上也很难实现.下面介绍地“最邻近方法”给出了问题地近似解.最邻近方法地步骤如下：1) 由任意选择地结点开始, 找与该点最靠近（即权最小）地点, 形成有一条边地初始路径.2) 设ｘ表示最新加到这条路上地结点, 从不在路上地所有结点中选一个与ｘ最靠近地结点, 把连接ｘ与这一结点地边加到这条路上. 重复这一步, 直到G中所有结点包含在路上.3) 将连接起始点与最后加入地结点之间地边加到这条路上, 就得到一个圈, 即为问题地近似解.【例10.4.5】某流动售货员居住在ａ城,为推销货物他要访问ｂ,ｃ,d城后返回ａ城.若该４城间地距离如图10.4.12所示,试用最邻近方法找出完成该旅行地最短路线？解按最邻近方法一共有４步,见图10.4.13. 得到地总距离为46.（10.4.12）寻找哈密顿路径是一个典型地NP-完全问题.后来人们也证明了,找一条哈密顿路地近似比为常数地近似算法也是NP-完全地.寻找哈密顿路地确定算法虽然很难有多项式时间地,但是这并不意味着只能进行时间复杂度为O(n!*n)暴力搜索.利用状态压缩动态规划,我们可以将时间复杂度降低到O(2^n*n^3),具体算法是建立方程f[i][S][j],表示经过了i个节点,节点都是集合S地,到达节点j时地最短路径.每次我们都按照点j所连地节点进行转移.哈密顿路图论在许多领域,诸如物理、化学、运筹学、计算机科学、信息论、控制论、网络理论、社会科学以及经济管理等各方面都有广泛地应用,它已经广泛地应用于实际生活、生产和科学研究中.所以作为二十一世纪地应用型,我们应该好好学习图论,把图论应用到现实生活中,帮我们解决一些实际生活中地问题,让所学地知识更好地服务于我们.。

2012年第09期吉林省教育学院学报No.09，2012第28卷JOURNAL OF EDUCATIONAL INSTITUTE OF JILIN PROVINCEVol .28（总309期）Total No .309收稿日期：2012—05—11作者简介：于言坤（1972—），男，吉林通化人。

吉林广播电视大学通化分校远程教育技术中心，高级讲师，教育硕士，研究方向：职业技术教育教学。

哈密尔顿图的矩阵判定法于言坤（吉林广播电视大学通化分校，吉林通化134000）摘要：哈密尔顿图是一种特殊的连通图。

一般情况下，哈密尔顿图只能根据定义加以判定，在某些特殊情况下才有判别法。

在充分理解哈密尔顿图定义，认真研究、分析其邻接矩阵特点的基础上，我们可以找到判定哈密尔顿图的充要条件的矩阵方法，从而得出一种判定哈密尔顿图的新方法。

关键词：哈密尔顿图；邻接矩阵；A *（D ）形邻接矩阵中图分类号：O158文献标识码：A 文章编号：1671—1580（2012）09—0149—02图是《离散数学》的重要知识内容。

图论的内容在不断扩展，理论研究和实践应用在不断深入、扩大。

图的理论正在现代运筹学、信息论、网络理论、生物学、化学、物理学、社会科学、语言学和计算机科学等领域得到广泛应用，解决了一些实际问题。

哈密尔顿图是一种特殊的连通图。

连通图中存在经过所有顶点的初级通路或回路，我们把这样的初级通路或回路称为哈密尔顿通路或回路。

一、定义1．1经过图中每个顶点一次且仅有一次的通路（回路），称为哈密尔顿通路（回路），存在哈密尔顿回路的图称为哈密尔顿图。

必须强调的是，存在哈密尔顿通路，但不存在哈密尔顿回路的连通图不是哈密尔顿图。

一般情况下，哈密尔顿图只能根据定义加以判定，在某些特殊情况下才有判别法。

定理1．1设G 是n （n ≥3）阶无向简单图，如果G 中任何一对顶点的度数之和都大于等于n ，则G 是哈密尔顿图。

定理1．1只是哈密尔顿图的充分条件，而不是必要条件。