哈密顿图

(重定向自哈密頓圖

哈密顿图(台湾作漢米頓圖)又稱漢密頓圖,是指存在哈密頓環無向圖,由哈密顿爵士提出。

十二面体中的哈密顿回路

定義

下列定義,既適用於無向圖,亦適用於有向圖。

哈密頓路徑
圖的一條,經過每個頂點恰好一次。
哈密頓環
在一條哈密頓路的基礎上,再有一條邊將其首尾連接,所構成的。注意,若有一個哈密頓圈,則移除其任一條邊,皆可得到一條哈密頓路,但反之則不然,即給定一條哈密頓路,不一定能延伸成哈密頓圈,因為該路徑的首尾兩頂點之間,不一定有邊相連。
哈密頓圖
有哈密頓圈的圖。
半哈密頓圖
有哈密頓路,但無哈密頓圈的圖。
哈密頓連通圖
一幅圖,以其任意兩個頂點為起終點,皆存在一條哈密頓路。
哈密頓分解
將邊集分劃成若干個哈密頓圈。
亞哈密頓圖
亞哈密頓圖英语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 (英语).