漢彌頓容錯圖的建構方法

Abstract

聯結網路聯結平行電腦的處理器，吾人可以一圖形結構來表示其聯結架構，在此圖形結構中的一個節點表示一處理器一條邊表示一聯通一對處理器的線路。在設計聯結網路時容錯性是一重要考慮的問題，另外漢彌頓性質也是一主要的設計考量。 在一無向圖中任意拔除k個節點後為漢彌頓圖時，該原圖吾人稱為k-點-漢彌頓圖。任意拔除k條邊後為漢彌頓圖時，該原圖吾人稱為k-邊-漢彌頓圖。若拔除的節點與邊數之和為小或等於k後仍為漢彌頓圖時，該原圖吾人稱為 k-漢彌頓圖。在所有相同節點數的k-漢彌頓圖中具有最少邊數的 k-漢彌頓圖，吾人稱該圖為最佳k-漢彌頓圖。在此論文中，將特別著重在k =1時任意節點或邊被拔除後該圖的漢彌頓性質，即單-漢彌頓圖。 在此論文中，我們將提出四種建構最佳單-漢彌頓圖的方法，即3-join、(3,4)-join、cycle extension和cycle join。運用此四種方法於單-漢彌頓圖將產生保有原漢彌頓性質的新圖，一些已發表在文獻上的單-漢彌頓圖亦可由這些建構方法所產生並且他們的漢彌頓性質可由運用這些建構方法而直接獲得，此外這些建構方法也可產生新的單-漢彌頓圖。

An interconnection network connects the processors of the parallel computer. Its architecture can be represented as a graph in which the nodes correspond to the processors and the edges to the communication links. Fault tolerance is an important issue in the design of an interconnection network. When faults occur in a network, it corresponds to removing edges and/or vertices from the graph. The hamiltonian properties is another one of the major requirements in designing the topology of network. Let $G=(V,E)$ be an undirected graph. Let $V^{\prime} \subseteq V$ and $E^{\prime} \subseteq E$. If $G- V^{\prime}$ is hamiltonian for any $V^{\prime} \subseteq V$ and $|V^{\prime}|= k$, then $G$ is called a $k$-{\it vertex-hamiltonian} graph. If $G- E^{\prime}$ is hamiltonian for any $E^{\prime} \subseteq E$ and $|E^{\prime}|= k$, then $G$ is called a $k$-{\it edge-hamiltonian} graph. If $G - F$ is hamiltonian for any $F \subseteq V \cup E$ and $|F|\le k$, then $G$ is called a $k$-{\it hamiltonian} graph. A $k$-hamiltonian graph is said to be {\it optimal} if it contains the least number of edges among all $k$-hamiltonian graphs having the same number of vertices. In this dissertation, we are in particular interested in $k= 1$ and an arbitrary vertex or edge fault, i.e., 1-hamiltonian graph. In this dissertation, we present four construction schemes for fault-tolerant hamiltonian graphs, $3$-{\it join}, $(3,4)$-{\it join}, {\it cycle extension}, and {\it cycle join}. We show that applying these construction schemes on fault-tolerant hamiltonian graphs generate graphs preserving the original hamiltonicity property. We apply these construction schemes to generate some known families of optimal 1-hamiltonian graphs in literature and the hamiltonicity properties of these graphs are the direct consequence of the construction schemes. In addition, we can use these construction schemes to propose new family of optimal 1-hamiltonian graphs.