Abstract
本篇論上旨在研究一套心跳式演算法，用來解決圖形上的一個重要問題－叉出一個無向連接（Undirected connected）圖中所有的橋（bridge）。給予一個無向連接圖Ｇ＝（Ｖ，Ｅ），其中Ｖ是有n 個元素的頂點集合，Ｅ是有個元素的邊集合，我們所提出的演算法，應用在使用２n －２個處理機的線性心跳式陣列型機器上，其時間複雜度是m ＋３n －３個心跳式週期（systolic cycle）。所謂的橋就是一個邊，當它從無向連接圖中去掉會造成不連接圖。我們所提出的演算法就是找出所有具有此特性的邊。在此篇論文中，我們推演出兩個預備定理。植基於這兩個預備定理，使我們所提出的方法完全不同於前人所提的方法。本文用來判斷一個邊是不是橋是利用展開樹（spanning tree ）的特性。因此，展開樹在本文中扮演很重要的角色。我們利用黃教授所提出的Ｆ函數建造演算法中所需的展開樹。至目前為止，此篇論文所討論的圖形問題，只有Prasad及Rangan曾提出線性心跳式演算法。和他們的演算法相比較，證明我們所提出的演算法需較少的時間複雜度。他們的演算法需要四個獨立步驟，其中第二步驟是相當複雜的，而且不容易達到完伓管線方式（pipelining）的運作。然而我們所提出的演算法是完全管線運作的結構，這是本篇最大的不同點和貢獻。