哈密顿图

哈密顿图(中国大陆作哈密顿图,台湾作汉米顿图)又称汉密顿图,是指存在哈密顿环无向图,由哈密顿爵士提出。

十二面体中的哈密顿回路

定义

下列定义,既适用于无向图,亦适用于有向图。

哈密顿路径
图的一条,经过每个顶点恰好一次。
哈密顿环
在一条哈密顿路的基础上,再有一条边将其首尾连接,所构成的。注意,若有一个哈密顿圈,则移除其任一条边,皆可得到一条哈密顿路,但反之则不然,即给定一条哈密顿路,不一定能延伸成哈密顿圈,因为该路径的首尾两顶点之间,不一定有边相连。
哈密顿图
有哈密顿圈的图。
半哈密顿图
有哈密顿路,但无哈密顿圈的图。
哈密顿连通图
一幅图,以其任意两个顶点为起终点,皆存在一条哈密顿路。
哈密顿分解
将边集分划成若干个哈密顿圈。
亚哈密顿图
亚哈密顿图英语Hypohamiltonian graph并非哈密顿图,但只要移除任何一个顶点,就会变成哈密顿图。

性质

哈密尔顿图的必要条件: 若G=(V,E) 是一个哈密尔顿图,则对于V的每一个非空子集S,均有W(G-S) ≤|S|。其中|S|是S中的顶点数,W(G-S)表示图G擦去属于S中的顶点后,剩下子图的连通分支的个数。

充分条件

欧拉图而言,有某个充要条件,可用作简单判定一幅图是否欧拉图(欧拉定理)。然而,对于哈密顿图,并无相应的结果。

不过,仍有一系列越来越松的判别条件,能够断定一幅图必定为哈密顿图。[1]此类定理,最早见于盖布瑞·狄拉克英语Gabriel Andrew Dirac1952年的研究,其想法直观,即只要有“足够多”边,就能迫得图有哈密顿圈。用顶点的推出存在哈密顿圈的定理之中,目前最优的,是1976年邦迪与赫瓦塔尔的定理。

以上是有关无向图的部分。对于有向图,相应的定理举例有Ghouila–Houiri。

狄拉克定理

盖布瑞·狄拉克英语Gabriel Andrew Dirac于1952年[2]证明以下定理:[3]

 个顶点的简单图 )中,若每个顶点的度皆至少为 ,则必为哈密顿图。

欧尔定理

  是一个无向简单图,  。若对于任意两个不相邻的顶点  ,都有   ,即    满足  ,那么,  是哈密尔顿图。

此条件由挪威图论数学家奥斯丁·欧尔在1960年给出。

波绍定理

波绍·拉约什英语Lajos Pósa (mathematician)证明了几条有关哈密顿圈的定理。以下具体引用一条1962年的定理[4][5],有关连边少的顶点:

一幅 个顶点的完全图( ),若满足:

  1. 对所有满足 的整数 ,度不大于 的顶点个数,严格小于 
  2. 度不大于 的顶点个数,小于或等于 

则必为哈密顿图。

注意 为偶时,条件2已包含于条件1,所以只在 为奇数时,条件2才需要分开列出。

 
应用波绍定理的例子

作为例子,考虑附图中,具有 个顶点的图。其为哈密顿图:已经将顶点排列好,使哈密顿圈 (以红色标示)正好是外圈。

  • 狄拉克定理不足以证明该图为哈密顿图。若要应用狄拉克定理,则所有顶点的度皆要至少为 ,然而图中有顶点的度仅为 
  • 奥尔定理同样不敷使用,因为图中标出的两个不相邻顶点 的度,和仅为 ,但奥尔定理的条件中,至少要有 
  • 另一方面,波绍定理能够断定该图必为哈密顿图,因为只有 个度为 的顶点,以及 个度为 的顶点,故已满足条件1(因为  )。

例子

 
赫歇尔图英语Herschel graph
  • 超过2个顶点的完全图是哈密顿图。 阶无向完全图 上,不同的(无向)哈密顿圈有 个。而若考虑方向,则有 个有向哈密顿圈。
  •  个顶点的图当中,最少边数的哈密顿图是循环图 。任何循环图皆为哈密顿图。
  • 循环赛图英语Tournament (graph theory)有奇数条(有向)哈密顿路径。任意(多于两个顶点的)循环赛图为哈密顿图当且仅当其为强连通[6]
  • 任何以柏拉图立体(凸正多面体)的边与顶点构成的图(“1-骨架英语n-skeleton”)皆为哈密顿图。[7][8]
  • 同样,棱柱反棱柱的1-骨架也是哈密顿图。
  • 13种阿基米德立体的1-骨架皆为哈密顿图,但13种卡塔兰立体当中,仅有7个的1-骨架是哈密顿图。[9][10].
  • 赫歇尔图英语Herschel graph(附图)是众多不具哈密顿圈的凸多面体1-骨架当中,最小的一个。[11]
  • 哈密顿图的线图仍是哈密顿图。[12]:408
  • 欧拉图的线图也是哈密顿图。

哈密顿路径问题

寻找哈密顿路径是一个典型的NP-完全问题。后来人们也证明了,找一条哈密顿路的近似比为常数的近似算法也是NP-完全的。

寻找哈密顿路的确定算法虽然很难有多项式时间的,但是这并不意味着只能进行时间复杂度 暴力搜索。利用状态压缩动态规划[来源请求],可以将时间复杂度降低到 ,具体算法是建立方程f[i][S][j],表示经过了i个节点,节点都是集合S的,到达节点j时的最短路径。每次都按照点j所连的节点进行转移。

参见

参考文献

  1. ^ Melissa DeLeon. Department of Mathematics and Computer Science, Seton Hall University , 编. A Study of Sufficient Conditions for Hamiltonian Cycles (PDF). [2021-09-19]. (原始内容存档 (PDF)于2012-12-22) (英语). 
  2. ^ Dirac, Gabriel Andrew. Some theorems on abstract graphs. Proc. London Math. Soc. 3. 1952, 2: 6––81. MR 0047308. doi:10.1112/plms/s3-2.1.69 (英语). 
  3. ^ Ronald Graham. Handbook of Combinatorics. MIT Press. 1995. ISBN 978-0-262-57170-8 (英语). 
  4. ^ Pósa, Lajos. A theorem concerning hamilton lines. Magyar Tud. Akad. Mat. Kutató ́Int. Közl. 1962, 7: 225–226 (英语). 
  5. ^ Nash-Williams, Crispin. On Hamiltonian circuits in finite graphs (PDF). Proc. Amer. Math. Soc. 1966, 17: 466–467 [2021-09-19]. (原始内容存档 (PDF)于2022-02-17) (英语). 
  6. ^ Graham 1995,第29 & 31页.
  7. ^ Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150–156, May 1957. [2021-09-03]. (原始内容存档于2016-10-22). 
  8. ^ Weisstein, Eric W. (编). Wolfram MathWorld (首頁). at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英语). 
  9. ^ Weisstein, Eric W. (编). Wolfram MathWorld (首頁). at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英语). 
  10. ^ Weisstein, Eric W. (编). Wolfram MathWorld (首頁). at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英语). 
  11. ^ Weisstein, Eric W. (编). Wolfram MathWorld (首頁). at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英语). 
  12. ^ Xiong, Liming; Liu, Zhanhong. Hamiltonian iterated line graphs [哈密顿的迭代线图]. Discrete Mathematics. 2002, 256: 407–422. doi:10.1016/S0012-365X(01)00442-3 (英语).