標題: 最佳多容錯之號誌環網路
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
顯示於類別:畢業論文