Abstract
在本篇論文中，我們將第一篇參考論文所提出的隨機演算法 R(m)加以修 改來建造一個2連接圖(2-connected graph)並分析其在平均狀況( average case)和最差狀況(worst case)下的效能。事實上，在平均狀況 方面,根據第三篇參考論文的結果，我們可以推導出一個n和m的函數來表 示當給定的點數很大時，R(m)所造出圖的長度期望值和最佳圖的長度期望 值的比值。在最差狀況方面，我們對R(m)的競爭比值(competitive ratio)導出了一個上限。此外，我們還考慮幾何平面上最小k邊連接圖問 題(minimum k-edge connected graph problem)與最小k點連接圖問題( minimum k-vertex connected graph problem)。平面上給定n個點，最小 k邊連接圖問題是在為這n個點造出一個總長度最小的圖，且其被移去k-1 個邊時，此圖要不是維持連接性，就是不包含任何邊。最小k點連接圖問 題則是將前面敘述中的邊換成點即可。上述兩者都是NP-hard問題，所以 我們針對前者提出一個趨進演算法(approximation algorithm)KE，並推 導出KE所造成圖的長度對最佳圖長度的比值為一個常數。對後者，我們提 出一個趨進演算法KV和一個經驗演算法(heuristic algorithm) KR，其中 KV所造成圖的長度對最佳圖長度的比值為O(k)，接著我們利用趨進演算法 KV來建造一個(k1點，k2邊)連接圖 (k1-vertex,k2-edge connected graph)並分析其效能。最後，KR則是利用K-RNG為k連接圖的特性，將其應 用在平均狀況且得到不錯的結果。