限制性最小K-樹問題是算法圖論中的一個經(jīng)典的研究問題,它具有比較實際的應(yīng)用背景和理論研究價值。本文主要研究限制頂點度的最小K-樹構(gòu)建問題,該問題是限制頂點度的最小支撐樹構(gòu)建問題和最小K-樹問題的推廣,具體問題描述為:給定一個n`1階的賦權(quán)圖G“pV,E;wq,這里函數(shù)w:E?R~`,v_0P V,非負整數(shù)K和正整數(shù)d,構(gòu)建一棵限制頂點v_0的度為d_(TK)pv_0q“d的K-樹T_K“pV,E_Kq,e P E_K,它的n`K條邊由長度為L的若干材料來構(gòu)建,c_0表示長度為L的每根材料的售價,kpT_Kq表示所需材料的根數(shù),cpeq表示邊e的施工費。問題的目標是使得構(gòu)建限制頂點度的K-樹所有邊的費用總和最小,即mint?_(ePEK)cpeq`kpT_Kq¨c_0u。在構(gòu)建時考慮有沒有施工費用的兩種情況,第一種情況,考慮在有施工費用時,來解決限制一個頂點度的K-樹構(gòu)建問題,設(shè)計了DCKTC算法,它是一個2-近似算法,該算法的時間復(fù)雜度為Opn~3q。第二種情況,考慮施工費用為0時,來解決限制一個頂點度的K-樹構(gòu)建問題,設(shè)計了DCKTP算法,其復(fù)雜度為Opn~3q。在DCKTC算法的理論基礎(chǔ)上,對其進行MATLAB語言編程,程序由四部分組成,分別是DCKTC算法主程序、Prim算法子程序、Fisher算法子程序和ChangeDegree子程序。
【學位單位】：云南大學
【學位級別】：碩士
【學位年份】：2018
【中圖分類】：TP301.6;O157.5

【相似文獻】

相關(guān)期刊論文 前10條

1 姚兵;;關(guān)于樹基數(shù)的不等式[J];西北師范大學學報(自然科學版);1987年01期

2 戴祖旭;無向簡單圖頂點度數(shù)的一個性質(zhì)[J];培訓與研究(湖北教育學院學報);2004年02期

3 劉翼舉;侯耀平;;一些由它的鄰接譜和角確定的圖[J];邵陽學院學報(自然科學版);2009年02期

4 彭波;高煒;;特殊框架下分數(shù)(g,f,m)-消去圖的不相鄰頂點度條件[J];山西大學學報(自然科學版);2017年02期

5 傅春花;徐秀蓮;何大韌;;大數(shù)據(jù)背景下一類社會網(wǎng)統(tǒng)計性質(zhì)的初步研究[J];計算機時代;2019年01期

6 袁履冰;丁勇;;計算共振能的一個新的經(jīng)驗方法[J];化學研究與應(yīng)用;1991年04期

7 張培培;何閱;周濤;蘇蓓蓓;常慧;周月平;汪秉宏;何大韌;;一個描述合作網(wǎng)絡(luò)頂點度分布的模型[J];物理學報;2006年01期

8 林政寬;趙源;樊建席;程寶雷;;基于頂點度數(shù)的完全獨立生成樹研究[J];計算機科學;2017年06期

9 呂劍波;;含k個頂點度為n-1的簡單連通圖的調(diào)和指標[J];漳州師范學院學報(自然科學版);2013年03期

10 董顯亮;對Bermond猜想(32)的一個注記[J];本溪冶金高等�？茖W校學報;2001年02期

相關(guān)會議論文 前1條

1 于博;李建中;王宏志;高宏;;超大有向圖上Top-k頂點度查詢的一種有效處理方法[A];第二十三屆中國數(shù)據(jù)庫學術(shù)會議論文集（技術(shù)報告篇）[C];2006年

相關(guān)博士學位論文 前2條

1 周金紅;大規(guī)模圖計算系統(tǒng)關(guān)鍵技術(shù)研究[D];中國科學技術(shù)大學;2017年

2 李靜;關(guān)于圖的能量和斜能量的若干極值問題[D];南開大學;2013年

相關(guān)碩士學位論文 前10條

1 李明亮;限制一個頂點度的K-樹構(gòu)建問題[D];云南大學;2018年

2 秧柳;限制頂點度的最小K-樹問題[D];云南大學;2017年

3 龍浩;以簇為中心的大規(guī)模圖數(shù)據(jù)分布式處理系統(tǒng)[D];華中科技大學;2017年

4 肖威;面向動態(tài)大圖的異步增量計算優(yōu)化機制[D];華中科技大學;2018年

5 黃仁毅;限制兩個頂點度的最小K-樹問題[D];云南大學;2015年

6 賀國卿;隨機圖上頂點度數(shù)序列及樹分圖的分布[D];天津大學;2010年

7 何守偉;熒蒽型苯環(huán)系統(tǒng)的基于頂點度的拓撲指數(shù)[D];湖南師范大學;2017年

8 駱曉波;多圖中的度匿名隱私保護算法[D];電子科技大學;2013年

9 陳功;圖的拓撲指標與結(jié)構(gòu)性質(zhì)若干問題的研究[D];深圳大學;2016年

10 朱笑然;網(wǎng)絡(luò)關(guān)系數(shù)據(jù)可視化研究與實現(xiàn)[D];北京郵電大學;2017年

本文編號：2810519