Abstract
設G(V,E,W)表一個圖形，其中V,E 分別為點集合及邊集合, 且每一個V 中之點V, 均有一個比重W(V) 。在這樣的條件下，有關瓶頸函蓋集之論文，幾乎沒有，因此,本論文便先挑限制較多的一種函蓋集:獨立函蓋集,進行這方面之研究。本論文中，我們提出了一個新的問題：圖形上瓶頸獨立函蓋集問題，引問題主要是要找一組獨立函蓋集其最大的比重要最小，為一個典型之瓶頸問題。有關這個問題，我們作了下列之研究成果。我們首先證明了本問題之決定版本，即使是限制在二裂圖形上，便是一個NP- 完全的問題，因此，我們得到一個結論：我們的問題, 即使是只考慮二裂圖形,便是NP-困難的問題, 其在一般圖形上, 更是NP- 困難。由於其NP- 困難之特性，因此，我們便試著在限制較多多特殊圖形上解該問題；首先，在樹形圖上，我們利用動態規劃的技巧，漂亮的設計一個最佳之線性演算法，解決了樹形圖上之瓶頸獨立函蓋集問題。接下來，我們考慮排列圖形，我們先將其轉成一個平面幾何問題：瓶頸最大鏈問題(花線性時間) ，然後以各個擊破之策略配上高度平衡樹之資料結構，將我們的問題以O(nlog n) 之單解掉。值得一提的是，我們的演算法結構和一般利用各個擊破策略之結構有點不太一樣，一般的是S(n)+2T( /2)+M(N) ，而我們的演算法之遞迴式子為S(n)+T( /2)+M(n)+T( /2)=O(n)+T( /2)+O(nlogn)+T( /2)