Abstract
正如大家所知的,一個圖是由頂點集合與邊集合組成的,而用它來表問題就 是所謂的圖論問題。它廣泛的出現在人工智慧、網路理論、系統工程、作 業研究學、控制學、語言學、物理學、化學、經濟管理等領域, 因而研究 圖論問題有其重要的理論與意義。在圖論及應用中,連結性( Connectivity)是一個非常重要的性質.它代表一個圖的強軔性( Routability)與可靠性(Reliability);譬如就邊的連結性(Edge Connectivity)而言,一個包含了橋(Bridges)的圖比雙邊連通圖(2-Ege Connected Graph)更不可靠; 而就點的連結性而言(Vertex Con -nectivity)而言,一個包含了關節點(Cutnodes)的圖比雙連通圖( Biconne -cted Graph)更不可靠。事實上,無向圖的橋(Bridges)、關節 點(Cutnodes)、連通分支(Conne -cted Components)、雙連通分支( Biconnected Components)都是常常出現的問題,這些問題也都屬於圖論應 用的基本問題。在順序及平行的環境中如何快速的計算圖的這些基本性 質,不僅具有重要的理論意義,而且有很大的應用價值。而在本篇論文中, 我們分別在順序及平行的環境中探討了下列新圖論問題: (1)最少關鍵點 集合基礎(Minimum Vertex Cutset Bases) (2)最少關鍵邊集合基礎( Minimum Edge Cutset Bases) (3)最少關鍵元素集合基礎(Minimum Element Cutset Bases),等都是架在上述基本圖學理論性質之上。而為了 簡化起見,所有我們在這本論文中提出的平行演算法皆製作於CRCW PRAM 上,但事實上它們都可無誤地製作於較弱的平行處理模式上。