關於網格的單線容錯設計

Abstract

其源於對於電腦網路系統中的電腦及網路系統的容錯能力的研究及問題探 討，許多專家學者近來將這些容錯系統的觀念轉化成圖形理論的問題。 若一個圖形G*被稱為是相對於一圖形G的k線容錯;則表示在G*中任意移去k 條線的新圖形中包含一個圖形G。 我們將此圖形G*簡記為k-EFT(G)。而一 個k-EFT(G)被視為最佳(optimal)則表示它在所有相對於圖形G的k線容錯 圖形中含有最少的線. 最近, Harary 和 Hayes提出了一些關於迴路 (cycle), 路徑(path), 超立方體(hypercube)和網格(mesh)的k線容錯設 計. 同時他們也猜測(conjecture)他們所提出關於網格的單線容錯設計應 是最佳的。針對他們所提出的猜測，我們提出了另一些關於網格的單線容 錯設計以證明他們的猜測是錯的。雖然我們無法證明我們所提出的所有設 計方法都是最佳的。 但對於一些特別的網格結構，我們可以確知其最佳 的單線容錯設計。 Motivated by the study of computers and communication networks that tolerate failure of their components, some scholars recently formulated the concept of fault tolerance in graphs. A graph G* is k-edge fault-tolerant with respect to a graph G, denoted by k-EFT(G), if every graph obtained by removing any k edges from G* contains G. A k-EFT(G) graph is optimal if it contains the minimum number of edges among all k-EFT(G) graphs. Recently, Harary and Hayes presented some designs which are k- EFT with respect to cycles, paths, hypercubes, and meshes. And they conjectured that their design for meshes is optimal. We disprove their conjecture is false by presenting another designs which is 1-EFT with respect to meshes. Though we can not prove all our designs are optimal for meshes, but there are some special cases that our designs are optimal for them.