加權圖中由最小生成樹尋找最重要的邊

Abstract

我們稱G=(V,E) 為圖形, 若V 是一個有限集合且E.｛(a,b.｜a≠b,(a,b)是V的無序序 對｝。而V 表示為圖形G 的所有端點所成的集合，E則表示為圖形G的所有邊所成的集 合。且令｜V=P 而｜E｜=q。 若圖H=(V,E)中V包含於V且E包含於E (V*V) 則稱圖形H 為圖形G 的子圖形。若圖形 H 再限制V'=V 則稱圖形H 為圖形G 的生成子圖形。若有一個圖形其滿足是圖形G 的 一個連接的生成子圖形且沒有回圈則稱其為生成樹。 若圖形G 的每一個邊e 都賦與比重，以w(e)岩示,即稱之為加權圖。一生成樹T的比重 ，以w(T)表示，定義為T 中所有邊比重的總和。若其中的一個生成樹T 與圖形G 的其 它生成樹TW(T) W(T) 的關係，則T 稱為圖形G 的最小生成樹。有兩個有名的演算法 用以解決找最小生成樹的問題。一個是Kruskal 的演算法其時間復雜度為O(q logq), 另一個是Prim的演算法其時間復雜度為O(p2)。 令g(G)定義為G 中最小生成樹的比重。若G 其中的一個邊e' 與的其它邊e 有g(G-e) g(G-e)的關係，則e稱是G 中最重要的邊,簡稱MVE而尋找這個邊的問題即稱為1-MVE問 題。文中提出三個循序演算法，時間復雜度分別為O(q log q+P2),O(q log q)及O(P2 )，還有一個在EREW PRAM的計算模式下,用了(P1+x)個處理器,其時間復雜度為O(P1+x )(0＜X＜1)的平行演算法來解決1-MVE 問題。