標題: | 最佳多容錯之號誌環網路 Optimal k-Fault-Tolerant Networks for Token Rings |
作者: | 劉雅惠 Ya-Hui Liu 徐力行 Dr. Lih-hsing Hsu 資訊科學與工程研究所 |
關鍵字: | 容錯;號誌環;k漢米爾頓連通圖;fault tolerant;token rings;k-hamiltonian graph. |
公開日期: | 1998 |
摘要: | 設計一個最佳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. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#NT870394030 http://hdl.handle.net/11536/64170 |
顯示於類別: | 畢業論文 |