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

【相似文獻(xiàn)】

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

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

2 戴祖旭;無(wú)向簡(jiǎn)單圖頂點(diǎn)度數(shù)的一個(gè)性質(zhì)[J];培訓(xùn)與研究(湖北教育學(xué)院學(xué)報(bào));2004年02期

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

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

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

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

7 張培培;何閱;周濤;蘇蓓蓓;�；�;周月平;汪秉宏;何大韌;;一個(gè)描述合作網(wǎng)絡(luò)頂點(diǎn)度分布的模型[J];物理學(xué)報(bào);2006年01期

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

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

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

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

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

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

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

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

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

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

2 秧柳;限制頂點(diǎn)度的最小K-樹問(wèn)題[D];云南大學(xué);2017年

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

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

5 黃仁毅;限制兩個(gè)頂點(diǎn)度的最小K-樹問(wèn)題[D];云南大學(xué);2015年

6 賀國(guó)卿;隨機(jī)圖上頂點(diǎn)度數(shù)序列及樹分圖的分布[D];天津大學(xué);2010年

7 何守偉;熒蒽型苯環(huán)系統(tǒng)的基于頂點(diǎn)度的拓?fù)渲笖?shù)[D];湖南師范大學(xué);2017年

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

9 陳功;圖的拓?fù)渲笜?biāo)與結(jié)構(gòu)性質(zhì)若干問(wèn)題的研究[D];深圳大學(xué);2016年

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

本文編號(hào)：2810519