Abstract
在許多應用科學中，我們常利用圖形或網路的連結 (edge) 來描述元件之 間的相互關係，因此網路設計師常想確知連結（邊）對網路的重要性。例 如說，當某連結自網路中去掉時，網路之結構因而改變，也造成網路之損 失。其中造成網路最大損失的連結，稱之為“最重要連結（邊）” (most vital edge)。嚴格地說，給定一網路Ｎ=(V,E) 及定義於其上之連 結集合的權重函數 w。在Ｎ上定義一個與 w 有關的準則函數 F。設集合 Ｎ-e 為自Ｎ中去掉連結 e 之結構。若某連結 e* 滿足下面條件則被稱為 最重要連結(most vital edge, MVE)： |F(N-e*)-F(N)| =max{|F(N-e)- F(N)|:對所有在Ｎ中之連結 e 而言。}通常都是針對確定之準則去探討最 重要連結問題，故稱之為相對於準則函數 F 之最重要連結問題 (F-MVE problem)。在本篇論文中，將對最小生成樹與網路可靠度兩準則闡述。藉 著處理最小生成樹的最重要連結之最佳計算方法 (optimal MVE algorithm)，我們提出了三個最佳平行計算方法 (optimal parallel MVE algorithm)。其中一個計算方法是在不可同時讀寫 (Exclusive Read Exclusive Write) 的平行計算模式下設計的。還有兩個計算方法是 在超立體型 (Hypercube) 的平行計算模式下設計的。因為計算網路可靠 度是一個 NP-hard 問題，所以通常都在具特殊結構之網路上發展確實之 計算方法。在本篇論文中，針對網路可靠度在有向及無向之串並聯網路上 討論最重要連結問題。我們提出一個新的資料結構，即所謂縮減式似樹結 構 (reduction quasi-tree)。利用此資料結構，於上述網路我們設計出 兩個線性時間之計算方法。上述計算方法亦為最佳的 (optimal)。 A rupture edge may cause unexpected loss in the network system. If an edge causes the maximum loss then it is called the most vital edge. Systematically, consider a criterion function $F$ on the connected subgraph of a network $N=(V,E)$ with a weight function $w$ on the edge set $E$. An edge $e^*$ is the {\it most vital edge (MVE)} if $$|F(N-e^*)-F(N)| =max|F(N-e)-F(N)|$$ over all edges $e$ in $E$, and this problem of finding the $MVE$ is called the {\it $MVE$ problem}. In this paper, two criteria: {\it minimum spanning tree (MST)} and {\it network reliability} are dealt with. In regard to minimum spanning tree, the cost- optimal parallel algorithms are also presented under EREW model and hypercube model. In this thesis, concerning the series-parallel graphs and $BSP$ digraphs the $MVE$ problem with respect to network reliability is dealt with. The time complexities of algorithms for the $MVE$ problem with respect to network reliability are linear, and they are also optimal $MVE$ algorithms.