發(fā)布時間：2017-10-09 05:38

  本文關(guān)鍵詞：限制出度的最小K-樹形圖問題

  更多相關(guān)文章： 限制出度 K-樹形圖 算法 復(fù)雜性

【摘要】：本論文主要研究有向圖中限制出度的最小K-樹形圖問題,其敘述如下：給定一個n+1階含有m條弧的賦權(quán)有向連通圖D=(V,A；ω),這里函數(shù)ω：A→R+,在D中尋找一個含n+K條弧的子集H,滿足誘導(dǎo)子圖D[H]含有一棵以固定頂點為根的支撐樹形圖,限制固定頂點的出度為一個常數(shù)且不含有向圈,目標(biāo)是使得H中所有弧的權(quán)重之和達到最小。 本論文首先把有向圖中限制出度的最小K-樹形圖問題分解成限制出度最小支撐樹形圖問題和最小K-樹形圖問題來研究。對限制出度最小支撐樹形圖問題,設(shè)計出一種O(n3m)的多項式時間算法。對最小K-樹形圖問題,設(shè)計出一種O(m2lgm)的多項式時間算法。然后,結(jié)合上述兩個算法思想,設(shè)計出一個多項式時間算法來解決限制出度的最小K-樹形圖問題,其復(fù)雜性為O(n3m)。
【關(guān)鍵詞】：限制出度 K-樹形圖 算法 復(fù)雜性
【學(xué)位授予單位】：云南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要3-4
• Abstract4-5
• 目錄5-6
• 第一章 引言6-9
• 1.1 理論背景6-7
• 1.2 主要結(jié)果7
• 1.3 論文結(jié)構(gòu)7-9
• 第二章 預(yù)備知識9-18
• 2.1 圖論9-11
• 2.2 組合最優(yōu)化11-15
• 2.3 最小支撐樹形圖問題及算法15-18
• 第三章 限制出度的最小K-樹形圖問題及其算法18-39
• 3.1 限制出度最小支撐樹形圖問題及其算法18-26
• 3.2 最小K-樹形圖問題及其算法26-28
• 3.3 限制出度的最小K-樹形圖問題及其算法28-30
• 3.4 算例30-39
• 結(jié)論39-40
• 參考文獻40-43
• 致謝43

【共引文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 孫小軍;王志強;;帶負權(quán)最短路問題前趨法的改進[J];安徽大學(xué)學(xué)報(自然科學(xué)版);2009年02期

2 張彬;袁叢鑫;司璇;金飛;;基于圖論的數(shù)字圖像邊緣檢測算法[J];中國傳媒大學(xué)學(xué)報(自然科學(xué)版);2011年03期

3 張忠海;李端玲;廖啟征;;柔性變胞機構(gòu)的拓撲結(jié)構(gòu)表示及構(gòu)態(tài)變換分析[J];北京郵電大學(xué)學(xué)報;2010年03期

4 王德忠,方健;切槽加工走刀路徑優(yōu)化問題的處理[J];包裝工程;2002年04期

5 楊羅輝;;一類基于模糊圖論的費用與時間最優(yōu)化問題的模型[J];長春大學(xué)學(xué)報;2007年12期

6 郝自軍;何尚錄;;最短路問題的Floyd算法的若干討論[J];重慶工學(xué)院學(xué)報(自然科學(xué)版);2008年05期

7 涂冰英;;實時動態(tài)最佳路徑的實現(xiàn)方法[J];測繪信息與工程;2006年03期

8 郭紀云;;每棵非平凡樹至少有兩片葉子的證法研究[J];長沙大學(xué)學(xué)報;2011年05期

9 葉玉民,周立新,胡小倩;關(guān)于最佳糧庫地址的選擇[J];東北電力學(xué)院學(xué)報;2001年01期

10 王興偉,王岳昭,鄭連偉,劉積仁;一種基于服務(wù)質(zhì)量的點對點通信路由選擇算法[J];東北大學(xué)學(xué)報;2000年02期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 王偉;鐵路網(wǎng)抗毀性分析與研究[D];北京交通大學(xué);2011年

2 陳德良;物流網(wǎng)絡(luò)可靠性的關(guān)鍵問題與應(yīng)用研究[D];中南大學(xué);2010年

3 邱宇;基于雙邊濾波的圖像去噪及銳化技術(shù)研究[D];重慶大學(xué);2011年

4 王兵;邏輯進程范型的形式語義、算法評估及其在空間隨機仿真中的應(yīng)用[D];國防科學(xué)技術(shù)大學(xué);2011年

5 李光;分類挖掘中的隱私保護問題研究[D];哈爾濱工業(yè)大學(xué);2011年

6 張強;基于連通性的無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)研究[D];天津大學(xué);2011年

7 王旭東;基于圖論的智能電網(wǎng)最優(yōu)孤島劃分模型和算法[D];天津大學(xué);2011年

8 楊威;協(xié)作認知無線電網(wǎng)絡(luò)優(yōu)化模型與算法研究[D];國防科學(xué)技術(shù)大學(xué);2011年

9 葛悅;模糊環(huán)境下若干網(wǎng)絡(luò)優(yōu)化問題的模型及其算法研究[D];哈爾濱工業(yè)大學(xué);2012年

10 牛東曉;非確定性工程項目計劃管理的新方法研究[D];華北電力大學(xué);2002年

，

本文編號：998459