最佳漢米爾頓連通圖族

Abstract

一條路徑<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.