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

  更多相關文章： 限制出度 K-樹形圖 算法 復雜性

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

• 摘要3-4
• Abstract4-5
• 目錄5-6
• 第一章 引言6-9
• 1.1 理論背景6-7
• 1.2 主要結果7
• 1.3 論文結構7-9
• 第二章 預備知識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
• 結論39-40
• 參考文獻40-43
• 致謝43

【共引文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號：998459