有信心之單容線容錯圖及一些串並聯網路之演算法

Abstract

在本篇論文中,要討論三個問題 (一)有信心的單線容錯圖 (二)串 並聯網路上一般的演算法及 (三)串並聯網路中之平行演算法的樹收縮. 針對有信心的單線容錯圖.我們在第二章介紹其優越的特性.依此方法可建 立 n維環狀的最佳單線容錯圖.電路的模式可用串並聯網路表示之.在第三 章我們發展出一個計算串並聯網路中最大配對數與最小配對數與最小控制 數的演算法,此演算法只需要線性的時間;針對串並聯網路中之平行演算的 樹收縮,我們建立一個平行演算法,此演算法在串並聯網路中可平行計算一 些非對稱函數. Three research topics are discussed in this study. These three issuesare the faithful edge fault tolerant graphs, algorithms for series-parallelnetworks and associated parallel algorithms. A graph $G^*$ is defined as$1$-edge fault tolerant with respect to a graph $G$, denotedby $1$-EFT($G$), if any graph obtained by removing an edge from $G^*$contains $G$. And the $1$-EFT($G$) graph isoptimal if it contains the minimum numberof edges among all $1$-EFT($G$) graphs. Let $G_i^*$ be $1$-EFT($G_i$) for$i=1, 2$. Then it can be easily verified that the cartesian product graph $G_1^*\times G_2^*$ is $1$-edge fault tolerant with respect to the cartesian productgraph $G_1 \times G_2$. However, $G_1^* \times G_2^*$ may contain too manyedges; hence it may not be optimal for many cases. In this study, thisproblem is overcome by introducingthe concept of faithful graph with respect to a given graph, which is proved to be 1-edge fault tolerant. Based on this concept,the construction method of $k$-EFT graphs for the cartesianproduct of several graphs is presented. Applying thisconstruction scheme, the optimal $1$-edge fault tolerant graphswith respect to $n$-dimensional tori $C(m_1, m_2, \ldots , m_n)$, where$m_i \geq 4$ are even integers for all $1 \le i \le n$, can be obtainedefficiently. Series-parallel networks have a lot of application.They are often used as models for electric circuits. In this study,series-parallel graphs are used to represent the series-parallel networks.Since there are many different graph representations for a series- parallelnetwork, our interest is focused on studying the maximum and minimummatching in different graph representations of a single network. Thelinear time algorithms are presented to compute the maximum and theminimum matching numbers and the minimum domination number for anyseries-parallel network $N$. It has been proved that everyseries-parallel network $N$ corresponds to a parse-tree $T(N)$. In manyapplications, there is a need to evaluate a parameter $F(N)$ for aseries-parallel network $N$. And this evaluation was implemented byevaluate $F( N)$ sequentially using dynamic programming techniques on$T(N)$. If the function $F$ is symmetric, the tree contraction techniquecould be used to evaluate $F(N)$ in parallel. However, many functionsdefined on series-parallel networks are non- symmetric. In this study,the idea of tree contraction to compute non-symmetric functions $F$ inparallel on the series-parallel networks is applied. Future work and theconclusion are also presented.