內(nèi)點帶權(quán)的最小生成樹.pdf

1、在已知邊帶權(quán)的連通圖中找一棵邊權(quán)總和最小的生成樹的問題很早就被提出和研究[15，14】，并且也得到了廣泛的應(yīng)用【15，14，23】。但是在日常生活中也會遇到這樣一類類似的問題，抽象出來就是在一個結(jié)點和邊都有權(quán)重的連通圖中找一棵生成樹，使得生成樹的內(nèi)點(非葉子結(jié)點)的權(quán)值和邊的權(quán)值總和最小，稱之為內(nèi)點帶權(quán)的最小生成樹。此前并沒有文獻提到并研究過此問題。本文首次提出了內(nèi)點帶權(quán)的最小生成樹問題，并對此問題進行了深入的分析和研究。主要有如下結(jié)論

2、： 1．首先對此問題進行了計算復(fù)雜性分析。證明了內(nèi)點帶權(quán)最小生成樹問題是NP-hard的；而且在Metric'隋況下，即若圖的邊權(quán)之間滿足三角不等式時，內(nèi)點帶權(quán)的最小生成樹問題仍然是NP-hard的。它們對應(yīng)的判定問題也都是NPC的。 2．在Metric'隋況，即圖的邊權(quán)滿足三角不等式時，本文給出了兩個近似度分別為3．52和3．106的多項式時間近似算法。同時分析了其不可近似性：此問題在Metric情況下不可能有近似度小

3、于1．463的多項式時間近似算法除非NP∩-DTIME[7／O(1oglogn]。 3．在一般情況下，即圖中的邊權(quán)不一定滿足三角不等式，本文給出了兩個近似度分別為2.35.1ogn和2．(Hn-1)的多項式時間近似算法，這里Hn是調(diào)和數(shù)(Harmonicnumber)，即：Hn=l+1/2+…+1/n，這里的n是原圖中結(jié)點的個數(shù)。同時證明了其不可近似性：對任意的E>0，此問題不可能有近似度小于(1一E)．Hn，的多項式時間近似算

4、法除非NP∩-DTIME[nO(10glogn)1。 4．本文最后給出了一個近似度為△一1的相對比較簡單的多項式時間近似算法，這里△是原圖的度，即圖中結(jié)點的最大度數(shù)。不難看出，當(dāng)原圖的度數(shù)比較小時，此算法非常有效。 綜上，本文證明了內(nèi)點帶權(quán)的最小生成樹的計算困難性，并且就不同的情況分別設(shè)計了相應(yīng)的近似算法以及分析了其不可近似性。由于計算內(nèi)點帶權(quán)的最小生成樹問題在實際中應(yīng)用比較廣泛，因此，本文的思想和方法對以后這方面的工作