20 哈密頓定理
- 詳細內容
-
分類：《算術講義》
-
發佈於：28 十月 2013
-
點擊數：760
作者：國立台灣師範大學數學系教授 許志農
有十個人出席一場宴會，圍繞一圓桌而坐，這些人中，有的彼此認識，有的卻完全不認識。如果希望這十個人圍繞圓桌而坐的方式至少要：每人的左右鄰座都與他認識，那麼這種圍繞方式是否存在（如何判斷）？事實上，這與哈密頓所思考的一則問題是有關的。
在 1857 年，愛爾蘭數學家哈密頓專注於一個問題：在空間中，一個包含有限個頂點及連結這些頂點的某些邊之圖形當中，在什麼條件之下，可以從一個頂點出發，沿著所連結的邊通過所有的頂點一次，最後再回到原出發的頂點，而形成一封閉的迴路？為了紀念這位偉大的數學家，像這種所有頂點恰好通過一次，最後又回到原本出發頂點的迴路，就稱為哈密頓迴路（要注意的是哈密頓迴路並非一定要走過所有連結的邊，但一定要通過所有的頂點一次）。
在我們認識哈密頓迴路之前，我們先來看有關圖的知識：在空間中任取有限個點（稱這些點為頂點），連結兩個相異頂點的路徑叫做一條邊。如果從這些頂點中去畫出一些邊，就把這個含頂點及這些邊的幾何結構叫做一個圖；例如下圖（一）到圖（四）都是圖。
(閱讀全文，請下載附加檔案)
| File | File size |
|---|---|
 20 mathdata.pdf | 183 Kb |