串並聯圖形中對擴展樹數目最具影響的連線之研究

Abstract

由於在通訊電腦網路中，各個工作站間的線路好壞與否甚為重要，某些線路一旦損壞 ，對整個網路的通訊或可靠度影響甚鉅。對網路圖形而言，擴展樹數目越大表示網路 可靠越佳。故此，我們在串並聯網路中研究連線對擴展樹數目的影響，論文共分五章 。 在第一章中，我們提出研究動機，並解釋所探討之題目，當一個連線在圖形中被去掉 (如同網路中的線路損壞中斷) 時，新的圖形產生的擴展樹數目。對圖形中的某一連 線而言，當它被去掉時所得的擴展樹數目較其它連線被去掉時犬為最少，我們稱此K 個連線為此圖形中最重要之K 個連線。 第二章中，概要的介紹串並聯圖形的一些基本定義，及介紹其上的二種結構：擴展樹 (Spanning tree) 及灌木(Bush)，利用此二結構，的特徵點做分類(Classification) ，並對各個邊緣點進行編碼(Coding)，可以在現性時間內算出串並聯圖形中的擴展樹 數目。 第三章中，我們設計二種特殊的資料結構稱E-elvaluation matrix及Preserving mat rix，利用此二2×2 的矩陣，可以在線性的時間內找到串並聯圖形最重要的連線。 第四章中，探討找二個以上的最重要連線。此情況較複雜，我們所提出的方法是得串 並聯圖形(Multigraph)改為簡單圖形(Simple graph)再加以處理，去找最重要之多個 連線。 最後一章，我們稍做結論以說明研究所得，並提出將來可繼續進行之研究方向。