不過，仍有一系列越來越鬆的判別條件，能夠斷定一幅圖必定為哈密頓圖。[1]此類定理，最早見於蓋布瑞·狄拉克（英语：Gabriel Andrew Dirac）1952年的研究，其想法直觀，即只要有「足夠多」邊，就能迫得圖有哈密頓圈。用頂點的度推出存在哈密頓圈的定理之中，目前最優的，是1976年邦迪與赫瓦塔爾的定理。
以上是有關無向圖的部分。對於有向圖，相應的定理舉例有Ghouila–Houiri。
狄拉克定理编辑
蓋布瑞·狄拉克（英语：Gabriel Andrew Dirac）於1952年[2]證明以下定理：[3]
^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） （英语）.
^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（英语）.
^Pósa, Lajos. A theorem concerning hamilton lines. Magyar Tud. Akad. Mat. Kutató ́Int. Közl. 1962, 7: 225–226 （英语）.
^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） （英语）.
^Graham 1995，第29 & 31頁 harvnb error: no target: CITEREFGraham1995 (help).
^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）.
哈密顿图, 此條目目前正依照fr, graphe, hamiltonien上的内容进行翻译, 2021年9月3日, 如果您擅长翻译, 並清楚本條目的領域, 欢迎协助翻譯, 改善或校对本條目, 此外, 长期闲置, 未翻譯或影響閱讀的内容可能会被移除, 目前的翻译进度为, 本條目存在以下問題, 請協助改善本條目或在討論頁針對議題發表看法, 此條目包含過多行話或專業術語, 可能需要簡化或提出進一步解釋, 2021年2月6日, 請在討論頁中發表對於本議題的看法, 並移除或解釋本條目中的行話, 此條目可参照法語維基百科相應條. 此條目目前正依照fr Graphe hamiltonien上的内容进行翻译 2021年9月3日 如果您擅长翻译 並清楚本條目的領域 欢迎协助翻譯 改善或校对本條目 此外 长期闲置 未翻譯或影響閱讀的内容可能会被移除 目前的翻译进度为 25 本條目存在以下問題 請協助改善本條目或在討論頁針對議題發表看法 此條目包含過多行話或專業術語 可能需要簡化或提出進一步解釋 2021年2月6日 請在討論頁中發表對於本議題的看法 並移除或解釋本條目中的行話 此條目可参照法語維基百科相應條目来扩充 2021年9月3日 若您熟悉来源语言和主题 请协助参考外语维基百科扩充条目 请勿直接提交机械翻译 也不要翻译不可靠 低品质内容 依版权协议 译文需在编辑摘要注明来源 或于讨论页顶部标记 a href Template Translated page html title Template Translated page Translated page a 标签 匈牙利人名顺序为先姓后名 本条目中的译名遵从此顺序 哈密顿图 台湾作漢米頓圖 又稱漢密頓圖 是指存在哈密頓環的無向圖 由哈密顿爵士提出 十二面体中的哈密顿回路 目录 1 定義 2 性質 3 充分條件 3 1 狄拉克定理 3 2 歐爾定理 3 3 波紹定理 4 例子 5 哈密顿路径问题 6 參見 7 參考文獻定義 编辑下列定義 既適用於無向圖 亦適用於有向圖 哈密頓路徑 圖的一條路 經過每個頂點恰好一次 哈密頓環 在一條哈密頓路的基礎上 再有一條邊將其首尾連接 所構成的圈 注意 若有一個哈密頓圈 則移除其任一條邊 皆可得到一條哈密頓路 但反之則不然 即給定一條哈密頓路 不一定能延伸成哈密頓圈 因為該路徑的首尾兩頂點之間 不一定有邊相連 哈密頓圖 有哈密頓圈的圖 半哈密頓圖 有哈密頓路 但無哈密頓圈的圖 哈密頓連通圖 一幅圖 以其任意兩個頂點為起終點 皆存在一條哈密頓路 哈密頓分解 將邊集分劃成若干個哈密頓圈 亞哈密頓圖 亞哈密頓圖 英语 Hypohamiltonian graph 並非哈密頓圖 但只要移除任何一個頂點 就會變成哈密頓圖 nbsp 非哈密頓圖 nbsp 半哈密頓圖 nbsp 哈密頓圖性質 编辑哈密尔顿图的必要条件 若G V E 是一个哈密尔顿图 则对于V的每一个非空子集S 均有W G S S 其中 S 是S中的顶点数 W G S 表示图G擦去属于S中的顶点后 剩下子图的连通分支的个数 充分條件 编辑對歐拉圖而言 有某個充要條件 可用作簡單判定一幅圖是否歐拉圖 歐拉定理 然而 對於哈密頓圖 並無相應的結果 不過 仍有一系列越來越鬆的判別條件 能夠斷定一幅圖必定為哈密頓圖 1 此類定理 最早見於蓋布瑞 狄拉克 英语 Gabriel Andrew Dirac 1952年的研究 其想法直觀 即只要有 足夠多 邊 就能迫得圖有哈密頓圈 用頂點的度推出存在哈密頓圈的定理之中 目前最優的 是1976年邦迪與赫瓦塔爾的定理 以上是有關無向圖的部分 對於有向圖 相應的定理舉例有Ghouila Houiri 狄拉克定理 编辑 蓋布瑞 狄拉克 英语 Gabriel Andrew Dirac 於1952年 2 證明以下定理 3 n displaystyle n nbsp 個頂點的簡單圖 n 3 displaystyle n geq 3 nbsp 中 若每個頂點的度皆至少為n 2 displaystyle frac n 2 nbsp 則必為哈密頓圖 歐爾定理 编辑 主条目 奧爾定理 设 G V E displaystyle G V E nbsp 是一个无向简单图 V n displaystyle V n nbsp n 3 displaystyle n geq 3 nbsp 若对于任意两个不相鄰的顶点 u v V displaystyle u v in V nbsp 都有 u displaystyle u nbsp 和 v displaystyle v nbsp 的度 即 d u displaystyle d u nbsp 与 d v displaystyle d v nbsp 满足 d u d v n displaystyle d u d v geq n nbsp 那么 G displaystyle G nbsp 是哈密尔顿图 此条件由挪威图论数学家奧斯丁 歐爾在1960年给出 波紹定理 编辑 波紹 拉約什 英语 Lajos Posa mathematician 證明了幾條有關哈密頓圈的定理 以下具體引用一條1962年的定理 4 5 有關連邊少的頂點 一幅n displaystyle n nbsp 個頂點的完全圖 n 3 displaystyle n geq 3 nbsp 若滿足 對所有滿足1 k lt n 1 2 displaystyle 1 leq k lt frac n 1 2 nbsp 的整數k displaystyle k nbsp 度不大於k displaystyle k nbsp 的頂點個數 嚴格小於k displaystyle k nbsp 度不大於n 1 2 displaystyle frac n 1 2 nbsp 的頂點個數 小於或等於n 1 2 displaystyle frac n 1 2 nbsp 則必為哈密頓圖 注意n displaystyle n nbsp 為偶時 條件2已包含於條件1 所以只在n displaystyle n nbsp 為奇數時 條件2才需要分開列出 nbsp 應用波紹定理的例子作為例子 考慮附圖中 具有6 displaystyle 6 nbsp 個頂點的圖 其為哈密頓圖 已經將頂點排列好 使哈密頓圈H displaystyle H nbsp 以紅色標示 正好是外圈 狄拉克定理不足以證明該圖為哈密頓圖 若要應用狄拉克定理 則所有頂點的度皆要至少為3 displaystyle 3 nbsp 然而圖中有頂點的度僅為2 displaystyle 2 nbsp 奧爾定理同樣不敷使用 因為圖中標出的兩個不相鄰頂點a b displaystyle a b nbsp 的度 和僅為d a d b 3 2 5 displaystyle d a d b 3 2 5 nbsp 但奧爾定理的條件中 至少要有6 displaystyle 6 nbsp 另一方面 波紹定理能夠斷定該圖必為哈密頓圖 因為只有0 displaystyle 0 nbsp 個度為1 displaystyle 1 nbsp 的頂點 以及1 displaystyle 1 nbsp 個度為2 displaystyle 2 nbsp 的頂點 故已滿足條件1 因為0 lt 1 displaystyle 0 lt 1 nbsp 且0 1 lt 2 displaystyle 0 1 lt 2 nbsp 例子 编辑 nbsp 赫歇爾圖 英语 Herschel graph 超過2個頂點的完全圖是哈密顿图 n displaystyle n nbsp 階無向完全圖K n displaystyle K n nbsp 上 不同的 無向 哈密頓圈有 n 1 2 displaystyle frac n 1 2 nbsp 個 而若考慮方向 則有 n 1 displaystyle n 1 nbsp 個有向哈密頓圈 n displaystyle n nbsp 個頂點的圖當中 最少邊數的哈密頓圖是循環圖C n displaystyle C n nbsp 任何循環圖皆為哈密顿图 循環賽圖 英语 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 完全的 寻找哈密顿路的确定算法虽然很难有多项式时间的 但是这并不意味着只能进行时间复杂度为O n n displaystyle O n times n nbsp 暴力搜索 利用状态压缩动态规划 來源請求 可以将时间复杂度降低到O 2 n n 3 displaystyle O 2 n cdot n 3 nbsp 具体算法是建立方程f i S j 表示经过了i个节点 节点都是集合S的 到达节点j时的最短路径 每次都按照点j所连的节点进行转移 參見 编辑哈密頓路徑 哈密顿路径问题參考文獻 编辑 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 英语 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 英语 Ronald Graham Handbook of Combinatorics MIT Press 1995 ISBN 978 0 262 57170 8 英语 Posa Lajos A theorem concerning hamilton lines Magyar Tud Akad Mat Kutato Int Kozl 1962 7 225 226 英语 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 英语 Graham 1995 第29 amp 31頁harvnb error no target CITEREFGraham1995 help 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 Weisstein Eric W 编 Wolfram MathWorld 首頁 at MathWorld A Wolfram Web Resource Wolfram Research Inc 英语 Weisstein Eric W 编 Wolfram MathWorld 首頁 at MathWorld A Wolfram Web Resource Wolfram Research Inc 英语 Weisstein Eric W 编 Wolfram MathWorld 首頁 at MathWorld A Wolfram Web Resource Wolfram Research Inc 英语 Weisstein Eric W 编 Wolfram MathWorld 首頁 at MathWorld A Wolfram Web Resource Wolfram Research Inc 英语 Xiong Liming Liu Zhanhong Hamiltonian iterated line graphs 哈密頓的疊代線圖 Discrete Mathematics 2002 256 407 422 doi 10 1016 S0012 365X 01 00442 3 英语 取自 https zh wikipedia org w index php title 哈密顿图 amp oldid 74735830, 维基百科，wiki，书籍，书籍，图书馆，
