Abstract
圖形理論中，重要的延伸樹 (spanning trees) 包括以下四種： (1) 深度優先搜尋樹 (depth-first-search trees) (2) 寬度優先搜尋樹(breadth-first-search trees) (3) 最短路徑樹 (shortest pathtrees) (4) 最小延伸樹 (minimum spanning trees) 。本論文主要探討各類延伸樹的辨識問題，也就是提出一套有效的辨識方法以判斷給定的延伸樹是否屬於上述四種之一。為了要解決這類的辨識問題，我們探討各類延伸樹的充要條件，以做為各演算法的依據。在本論文所解決的兩個延伸樹的辨識問題中，我們的基本策略是反覆利用這些充要條件以消去不能滿足條件的節點 (vertices) ，只要有剩餘的節點未被刪除即代表該延伸樹通過檢測。同時為了要使辨識的時間最佳化，相同的節點應避免重複的消去動作。首先我們利用歐拉路徑法， 在 EREW PRAM 的平行處理模式下，針對深度優先搜尋樹的辨識問題，提出一個最佳的平行處理演算法。此演算法執行所需的時間為 O(m/p +log m) ，其中 p 代表處理器的個數。值得注意的是，一個圖形的深度優先搜尋法是個 P-complete 的問題，也就是它不容易被平行處理，然而我們證明了其對應的辨識問題卻有極佳的平行演算法。接著我們提出一個可在 O(m+n) 時間內執行的循序演算法，以解決最短路徑樹的辨識問題。由於建立最短路徑樹需要 O(m + n logn) 的時間，因此我們證實了最短路徑樹的辨識的確比其建立容易。本文共分五章：第一章前言與簡介；第二章為延伸樹性質之研析；第三章為辨識深度優先樹之平行演算法；第四章為辨識最短路徑樹之循序演算法；第五章結論及未來研究方向．There are several kinds of spanning trees we are concernedabout : (1) A depth-first-search tree is a by-product of adepth first search algorithm; (2) A breadth-first-search treeis a by-product of a breadth first search algorithm; (3) Ashortest-path tree is a rooted spanning tree such that, fromthe root to any vertex, the path going along only tree edges isa shortest path; (4) A minimum spanning tree is a spanning treewith the minimum total edge cost. To recognize a certain kindof spanning trees is to verify whether a given spanning tree isof this specific type. In this dissertation, two open problemsare solved. We first propose an O(m/p + log m)-time parallelalgorithm using p processors on the EREW PRAM model thatdetermines whether a given spanning tree T is a depth-first-search tree of a given graph G. The major technique utilizedin our algorithm is the Euler tour technique. Our algorithm isoptimal in both time complexity and cost. Next, we shallpropose an O(m + n)-time sequential algorithm to verify whethera given spanning tree T is a shortest-path tree of a givengraph G. A necessary and sufficient condition for recognizingshortest-path trees shall be discussed. We propose a method tocut off all vertices violating this condition. And, if thereis one vertex which has never been cut, T is a shortest-pathtree of G. The crutial techniques are to normalize the cuttinginformation and resolve them by an efficient bottom-uppropagation.