標題: | 最佳漢米爾頓連通圖族 A Family of Optimal Hamiltonian Connected Graphs |
作者: | 許弘駿 Hong-Chun Hsu 徐力行 Lih-Hsing Hsu 資訊科學與工程研究所 |
關鍵字: | 漢米爾頓連通;漢米爾頓路徑;Hamiltonian Connected;Hamiltonian Path |
公開日期: | 1998 |
摘要: | 一條路徑<v0,v1,…,vm>而且v0!=vm,包含一個圖形G上所有的點稱之為漢米爾頓路徑。一個圖形G被稱之為漢米爾頓連通圖,假如任兩點之間皆存在有漢米爾頓路徑。一個漢米爾頓連通圖是最佳的,假如在所有相同點數的漢米爾頓連通圖中它包含了最少的邊。在這篇論文中,我們會討論到一個最佳漢米爾頓圖的建構方法。 A path <v0,v1,…,vm> with v0!=vm that includes all vertices of G is called a hamiltonian path. A graph G is called a hamiltonian connected if there exists a hamiltonian path joining any two different vertices in G. A hamiltonian connected graph is optimal if it contains the least number of edges among all the hamiltonian connected graphs with the same number of vertices. In this thesis, we study a construction scheme for optimal hamiltonian connected graphs. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#NT870394029 http://hdl.handle.net/11536/64169 |
Appears in Collections: | Thesis |