最佳多容錯之號誌環網路

Abstract

設計一個最佳k容錯之號誌環網路相當於建造一個最佳k漢米爾頓連通圖, 其中k表示點或邊壞掉的個數. 對任意 $V_1 \subset V$, $E_1 \subset E$ 滿足 $\left| V_1 \right|+\left| E_1 \right| \leq k $ 的圖$G=(V,E)$ 被稱為k-漢米爾頓連通圖假如$G-(V_1-E_1)$是漢米爾頓連通圖. 在所有相同點數的k漢米爾頓連通圖裡面, 邊的點數最少的k漢米爾頓連通圖G*是最佳的. 在這篇論文中, 我們證明 是最佳k漢米爾頓連通圖其中k是大於等於4的偶正整數.

Designing an optimal $k$-fault-tolerant network for token rings is equivalent to constructing an optimal $k$-hamiltonian graph, where $k$ is a positive integer and corresponds to the number of faults. A graph $G=(V,E)$ is $k$-hamiltonian if $G-(V_1-E_1)$ is hamiltonian for arbitrary $V_1 \subset V$, $E_1 \subset E$ with $\left| V_1 \right|+\left| E_1 \right| \leq k $. A $k$-hamiltonian graph G* is optimal if it contains the fewest edges among all $k$-hamiltonian graphs with the same number of vertices as G*. In this thesis, we prove that $G_{n,k}$ is optimal $k$-hamiltonian for $k$ an even integer greater than 4.