fbpx
维基百科

哈密頓路徑

十月 18, 2023

在圖論中，哈密顿路径（台湾作漢米頓路徑）是在無向圖或有向圖中，恰好能將圖中所有頂點各拜訪一次的路徑。與之相近的概念為哈密顿环（台湾作漢米頓環），即該路徑在拜訪完圖中所有頂點後會回到出發點，而構成一個環。要確定圖中是否存在哈密頓路徑或哈密頓環的問題稱為哈密顿路径问题[1]，這個問題是一個NP完全的問題。哈密頓路徑有時會跟尤拉路徑一起討論，因為哈密頓路徑要求通過所有頂點（哈密顿路径问题）而尤拉路徑要求通過所有邊（一筆畫問題）。[2]:218[3]

經過圖中所有頂點的迴路稱為哈密頓環

定義 编辑

哈密頓路徑是一個拜訪過某圖所有頂點的路徑，且每個頂點只會被拜訪一次。[4]存在哈密頓路徑的圖稱為可追蹤圖。如果一個圖中每對頂點都能找到一條哈密頓路徑，則這個圖可以被視為哈密頓連通的。哈密頓環或哈密頓迴路是一個拜訪過某圖所有頂點的環或循環路徑[5]:196，在這個循環路徑中每個頂點只會被拜訪一次，且拜訪完所有頂點後會回到起始點。存在哈密頓環的圖稱為哈密頓圖[6][7]。哈密頓環與哈密頓路徑主要可以由起點和終點來區別：若一哈密頓路徑起點與終點相同，其為哈密頓環；而若起點與終點不同，則其就不是哈密頓環，僅能視為哈密頓路徑。[8]

哈密頓分解（英语：Hamiltonian decomposition）是將圖分解成哈密頓環的邊分解方式。[9]

哈密頓迷宮是一種邏輯益智遊戲，其目標在於找到圖中唯一的哈密頓環。[10][11]

性質 编辑

任何哈密頓環都可以透過移除一條邊來轉換成哈密頓路徑。然而哈密頓路徑只有路徑的2端點相鄰時才有機會透過新增一條邊來轉換成哈密頓環。所有具備哈密頓環的圖（即哈密頓圖）都是雙連通圖；但雙連通圖不一定會存在哈密頓環（即雙連通圖不一定是哈密頓圖，如佩特森圖）。[12]

階數為n（n=1,2,3...）的簡單圖中存在的哈密頓環的總數為0, 0, 2, 10, 58, 616, 9932, 333386, 25153932, 4548577688, ...（OEIS數列A124964）。[13]

參見 编辑

參考文獻 编辑

  1. ^ 漢密頓路徑 Hamiltonian path. 資訊與通信術語辭典. 國家教育研究院. 2003年6月 [2021-09-03]. （原始内容于2021-09-03）. 
  2. ^ 高通量测序数据分析 (PDF). 興邦二校. [2021-09-03]. （原始内容 (PDF)于2021-08-06）. 
  3. ^ 徐力行. 沒有數字的數學. 天下文化. 2003-09-16. ISBN 9789864171842 （中文（臺灣））. 
  4. ^ 特殊路徑與迴路. ck.tp.edu.tw. [2021-09-03]. （原始内容于2019-10-30）. 
  5. ^ Skiena, Steven; Pemmaraju, Sriram. "Hamiltonian Cycles" §5.3.4 in. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge University Press. 1990: 196-198. ISBN 978-0521806862. 
  6. ^ Weisstein, Eric W. (编). Hamiltonian Cycle. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）. 
  7. ^ Weisstein, Eric W. (编). Hamiltonian Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）. 
  8. ^ Hamilton Circuit. ntnu.edu.tw. [2021-09-03]. （原始内容于2021-09-03）. 
  9. ^ Bermond, J.-C., Hamiltonian decompositions of graphs, directed graphs and hypergraphs, Annals of Discrete Mathematics, 1978, 3: 21–28, ISBN 9780720408430, MR 0505807, doi:10.1016/S0167-5060(08)70494-1 
  10. ^ de Ruiter, Johan. Hamilton Mazes – The Beginner's Guide. 2017. 
  11. ^ Friedman, Erich. Hamiltonian Mazes. Erich's Puzzle Palace. 2009 [27 May 2017]. （原始内容于16 April 2016）. 
  12. ^ Weisstein, Eric W. (编). Biconnected Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2021-09-03]. （原始内容于2018-01-15） （英语）. 
  13. ^ Sloane, N.J.A. (编). Sequence A124964 (Total counts of distinct (directed) Hamiltonian cycles for all simple graphs of order n.). The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. 

外部連結 编辑

十月 18, 2023
哈密頓路徑, 在圖論中, 哈密顿路径, 台湾作漢米頓路徑, 是在無向圖或有向圖中, 恰好能將圖中所有頂點各拜訪一次的路徑, 與之相近的概念為哈密顿环, 台湾作漢米頓環, 即該路徑在拜訪完圖中所有頂點後會回到出發點, 而構成一個環, 要確定圖中是否存在或哈密頓環的問題稱為哈密顿路径问题, 這個問題是一個np完全的問題, 有時會跟尤拉路徑一起討論, 因為要求通過所有頂點, 哈密顿路径问题, 而尤拉路徑要求通過所有邊, 一筆畫問題, 經過圖中所有頂點的迴路稱為哈密頓環, 目录, 定義, 性質, 參見, 參考文獻, 外部連. 在圖論中 哈密顿路径 台湾作漢米頓路徑 是在無向圖或有向圖中 恰好能將圖中所有頂點各拜訪一次的路徑 與之相近的概念為哈密顿环 台湾作漢米頓環 即該路徑在拜訪完圖中所有頂點後會回到出發點 而構成一個環 要確定圖中是否存在哈密頓路徑或哈密頓環的問題稱為哈密顿路径问题 1 這個問題是一個NP完全的問題 哈密頓路徑有時會跟尤拉路徑一起討論 因為哈密頓路徑要求通過所有頂點 哈密顿路径问题 而尤拉路徑要求通過所有邊 一筆畫問題 2 218 3 經過圖中所有頂點的迴路稱為哈密頓環 目录 1 定義 2 性質 3 參見 4 參考文獻 5 外部連結定義 编辑哈密頓路徑是一個拜訪過某圖所有頂點的路徑 且每個頂點只會被拜訪一次 4 存在哈密頓路徑的圖稱為可追蹤圖 如果一個圖中每對頂點都能找到一條哈密頓路徑 則這個圖可以被視為哈密頓連通的 哈密頓環或哈密頓迴路是一個拜訪過某圖所有頂點的環或循環路徑 5 196 在這個循環路徑中每個頂點只會被拜訪一次 且拜訪完所有頂點後會回到起始點 存在哈密頓環的圖稱為哈密頓圖 6 7 哈密頓環與哈密頓路徑主要可以由起點和終點來區別 若一哈密頓路徑起點與終點相同 其為哈密頓環 而若起點與終點不同 則其就不是哈密頓環 僅能視為哈密頓路徑 8 哈密頓分解 英语 Hamiltonian decomposition 是將圖分解成哈密頓環的邊分解方式 9 哈密頓迷宮是一種邏輯益智遊戲 其目標在於找到圖中唯一的哈密頓環 10 11 性質 编辑任何哈密頓環都可以透過移除一條邊來轉換成哈密頓路徑 然而哈密頓路徑只有路徑的2端點相鄰時才有機會透過新增一條邊來轉換成哈密頓環 所有具備哈密頓環的圖 即哈密頓圖 都是雙連通圖 但雙連通圖不一定會存在哈密頓環 即雙連通圖不一定是哈密頓圖 如佩特森圖 12 階數為n n 1 2 3 的簡單圖中存在的哈密頓環的總數為0 0 2 10 58 616 9932 333386 25153932 4548577688 OEIS數列A124964 13 參見 编辑哈密顿图 具有哈密頓環的圖 哈密顿路径问题 判斷圖中是否存在哈密頓路徑的問題參考文獻 编辑 漢密頓路徑 Hamiltonian path 資訊與通信術語辭典 國家教育研究院 2003年6月 2021 09 03 原始内容存档于2021 09 03 高通量测序数据分析 PDF 興邦二校 2021 09 03 原始内容存档 PDF 于2021 08 06 徐力行 沒有數字的數學 天下文化 2003 09 16 ISBN 9789864171842 中文 臺灣 特殊路徑與迴路 ck tp edu tw 2021 09 03 原始内容存档于2019 10 30 Skiena Steven Pemmaraju Sriram Hamiltonian Cycles 5 3 4 in Implementing Discrete Mathematics Combinatorics and Graph Theory with Mathematica Cambridge University Press 1990 196 198 ISBN 978 0521806862 Weisstein Eric W 编 Hamiltonian Cycle at MathWorld A Wolfram Web Resource Wolfram Research Inc 英语 Weisstein Eric W 编 Hamiltonian Graph at MathWorld A Wolfram Web Resource Wolfram Research Inc 英语 Hamilton Circuit ntnu edu tw 2021 09 03 原始内容存档于2021 09 03 Bermond J C Hamiltonian decompositions of graphs directed graphs and hypergraphs Annals of Discrete Mathematics 1978 3 21 28 ISBN 9780720408430 MR 0505807 doi 10 1016 S0167 5060 08 70494 1 de Ruiter Johan Hamilton Mazes The Beginner s Guide 2017 Friedman Erich Hamiltonian Mazes Erich s Puzzle Palace 2009 27 May 2017 原始内容存档于16 April 2016 Weisstein Eric W 编 Biconnected Graph at MathWorld A Wolfram Web Resource Wolfram Research Inc 2021 09 03 原始内容存档于2018 01 15 英语 Sloane N J A 编 Sequence A124964 Total counts of distinct directed Hamiltonian cycles for all simple graphs of order n The On Line Encyclopedia of Integer Sequences OEIS Foundation 外部連結 编辑埃里克 韦斯坦因 哈密頓環 MathWorld Euler tour and Hamilton cycles 取自 https zh wikipedia org w index php title 哈密頓路徑 amp oldid 75223811, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。