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

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

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

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

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