漢密爾頓路徑
在圖理論的數學字段中，哈密頓路徑（或可追溯路徑）是無向或有向圖的路徑，它準確地訪問了每個頂點一次。哈密頓週期（或哈密頓電路）是一個準確訪問每個頂點的週期。可以通過增加一個邊緣形成漢密爾頓週期的漢密爾頓路徑，該路徑可以從相鄰的頂點開始和結束，並從哈密頓循環中刪除任何邊緣會產生漢密爾頓路徑。確定圖形和周期是否存在（哈密頓路徑問題和哈密頓週期問題）的計算問題是NP完整的。
漢密爾頓的路徑和周期以威廉·羅恩·漢密爾頓（William Rowan Hamilton）的名字命名，後者發明了冰島遊戲，現在也被稱為漢密爾頓的難題，其中涉及在十二面體的邊緣圖中找到漢密爾頓週期。漢密爾頓使用Icosian微積分解決了這個問題，Icosian演算是一種基於統一根的代數結構，與四元組相似（也由漢密爾頓發明）。該解決方案不會推廣到任意圖。
儘管以漢密爾頓的名字命名，但托馬斯·柯克曼（Thomas Kirkman）也曾研究過波利法德拉（Polyhedra）的漢密爾頓週期，特別是，他特別舉例說明了一個沒有漢密爾頓週期的多面體。甚至更早的時候，漢密爾頓騎士圖棋盤圖中的漢密爾頓週期和路徑，騎士的巡迴演出，在9世紀，魯德拉塔（ Rudrata）在印度的數學上進行了研究，大約在同一時間，Al- Adli Ar-Rumi在伊斯蘭數學上進行了研究。在18世紀的歐洲，騎士之旅由亞伯拉罕·德·莫伊夫（Abraham de Moivre）和萊昂哈德·歐拉（Leonhard Euler）出版。
定義
哈密頓路徑或可追溯路徑是一條準確訪問圖表的每個頂點的路徑。包含哈密頓路徑的圖稱為可追溯圖。如果對於每個頂點，兩個頂點之間都有一個哈密頓路徑，則圖形是與哈密頓相關的。
哈密頓循環，哈密頓電路，頂點遊覽或圖週期是一個循環，可以準確訪問每個頂點一次。包含哈密頓週期的圖稱為哈密頓圖。
可以針對有向圖定義類似的概念，其中路徑或週期的每個邊緣（弧）只能以一個方向追踪（即，頂點與箭頭連接，邊緣跟踪的“尾巴”）。
哈密頓分解是將圖形分解為哈密頓電路的邊緣分解。
漢密爾頓迷宮是一種邏輯難題，目標是在給定圖中找到獨特的漢密爾頓週期。
例子
- 有兩個以上頂點的完整圖是哈密頓
- 每個循環圖都是漢密爾頓
- 每場比賽都有奇數的漢密爾頓道路（ Rédei ，1934年）
- 每個被認為是圖形的柏拉圖固體都是哈密頓
- 有限的Coxeter組的Cayley圖是Hamiltonian（有關Cayley圖中哈密頓路徑的更多信息，請參見Lovász猜想。）
- 帶有環狀換向子亞組的尼爾植物組上的Cayley圖是哈密頓量。
- 凸多邊形的翻轉圖或等效的二進制樹的旋轉圖是哈密頓式的。
特性
任何哈密頓循環都可以通過去除其一個邊緣來轉換為哈密頓路徑，但是只有在其終點相鄰時，哈密頓路徑才能擴展到哈密頓循環。
所有漢密爾頓圖都是雙色的，但是雙連接的圖不必是哈密頓量（例如，參見Petersen圖）。
Eulerian圖G （每個頂點具有甚至度的連接圖）必然會有Euler Tour，一個封閉的步行路經過G的每個邊緣。這次巡迴演出對應於線圖L （ g ）中的哈密頓週期，因此每個Eulerian圖的線圖都是Hamiltonian。線形圖可能具有其他漢密爾頓週期，與Euler Tours不符，尤其是每個漢密爾頓圖G的線圖L （ g ）本身都是漢密爾頓人，無論該圖G是否為Eulerian。
當且僅當比賽緊密相連時，比賽（具有兩個以上的頂點）是哈密頓人。
在n個頂點上完整的無向圖中不同的漢密爾頓週期的數量是（n - 1）！/2，在n個頂點的完整有向圖中為（n - 1）！。這些計數假定與起點相同的循環不是單獨計數的。
邦迪 - chvátal定理
邦迪- chvátal定理在1972年提供了哈密頓圖的最佳頂點特徵，該定理概述了GA Dirac （1952）和Øyysteinore的早期結果。 Dirac和Ore的定理也可以源自Pósa的定理（1962）。與各種參數有關，例如圖形密度，韌性，禁止的子圖和其他參數之間的距離，對Hamiltonicity進行了廣泛的研究。 Dirac和Ore的定理基本上指出，如果它具有足夠的邊緣，則圖形為哈密頓量。
Bondy -Chvátal定理在圖形G的閉合Cl（ g ）上以N頂點進行操作，並通過反复添加新的邊緣UV連接一對非相鄰的頂點U和V與DEG （ v ） + nom直到找不到與此屬性的再在一起。
Bondy -Chvátal定理（1976） -當且僅當其關閉是哈密頓量時，圖是哈密頓量。
由於完整的圖是哈密頓量，所有閉合的圖都是哈密頓量，這是迪拉克和礦石的以下定理的以下定理的內容。
Dirac的定理（1952） -一個帶有n個頂點的簡單圖（ 
以下定理可以被視為定向版本：
必須將頂點的數量加倍，因為每個無方向的邊緣對應於兩個定向的弧，因此在有向圖中的頂點的度數是無向圖中的程度的兩倍。
上述定理只能識別圖表中的哈密頓路徑的存在，而不是哈密頓循環。
這些結果中有許多具有平衡的兩分圖的類似物，其中將頂點度與兩部分一側的頂點的數量進行了比較，而不是整個圖中的頂點數量。
平面圖中的漢密爾頓週期存在
定理-一個四連接的平面三角剖分具有哈密頓週期。
定理-一個4連接的平面圖具有哈密頓週期。
哈密頓週期多項式
給定的加權挖掘漢密爾頓週期的代數表示（其弧線是從某個地面分配的權重）是其加權鄰接矩陣的漢密爾頓循環多項式，定義為Digraph's Hamiltonian Cycles的弧產物的總和。當且僅當Digraph為Hamiltonian時，此多項式並不是弧權重量中的函數。 Grigoriy Kogan顯示了計算IT的計算複雜性與計算永久性的關係之間的關係。
也可以看看
- Barnette的猜想，關於立方雙方多面體圖的大麻的開放問題
- 歐拉（Eulerian）路徑，一條穿過圖中所有邊緣的路徑
- Fleischner的定理，在漢密爾頓的圖形方面
- 灰色代碼
- 格林伯格的定理給出了平面圖的必要條件，使其具有哈密頓週期
- 哈密頓路徑問題，查找哈密頓路徑的計算問題
- Hypohamiltonian圖，這是一個非哈米爾頓圖，每個頂點刪除子圖是哈密頓
- 騎士之旅，騎士圖中的哈密頓週期
- LCF符號表示哈密頓立方圖。
- Lovász的猜想認為頂點傳播圖是哈密頓
- 龐然大鏡圖，圖形，具有各個長度的周期，包括哈密頓週期
- 科尼格斯伯格的七個橋樑
- 短暫指數，一種數值衡量距離哈密頓的距離的數字度量可以是一個家庭中的圖表
- 蛇在盒子裡，是超立方體中最長的誘導路徑
- Steinhaus – Johnson -Trotter算法，用於在PermutoheDron中找到哈密頓式路徑
- subhamiltonian圖，平面哈密頓圖的子圖
- Tait的猜想（現在已知的錯誤），三個規範的多面體圖是哈密頓
- 旅行推銷員問題