本文關(guān)鍵詞：限制兩個(gè)頂點(diǎn)度的最小K-樹(shù)問(wèn)題

  更多相關(guān)文章： 限制性K-樹(shù) 可交換邊對(duì) 多項(xiàng)式時(shí)間算法 復(fù)雜性

【摘要】：限制性K-樹(shù)問(wèn)題是一類組合優(yōu)化問(wèn)題,它具有重要的理論研究?jī)r(jià)值和實(shí)際應(yīng)用價(jià)值。本論文研究限制性K-樹(shù)問(wèn)題的一種推廣形式,稱之為限制兩個(gè)頂點(diǎn)度的最小K-樹(shù)問(wèn)題。該問(wèn)題具體描述為：給定一個(gè)n+1階賦權(quán)圖G=(V,E;w),這里函數(shù)w:E→R+,兩個(gè)固定頂點(diǎn)vs,vt∈V及兩個(gè)正整數(shù)k1和k2與一個(gè)非負(fù)整數(shù)K,尋找圖G的一棵K-樹(shù)TKst,使之滿足dTKst(Vs)=k1,和dTKst(Vt)=k2,目標(biāo)是使TKst所有邊的權(quán)重之和w(TKst)=∑e∈TKstw(e)達(dá)到最小。 本論文設(shè)計(jì)了一個(gè)多項(xiàng)式時(shí)間算法來(lái)解決限制兩個(gè)頂點(diǎn)度的最小K-樹(shù)問(wèn)題,算法復(fù)雜性為(?)(n4)；并對(duì)這個(gè)算法進(jìn)行MATLAB編程并實(shí)現(xiàn)了算例。
【關(guān)鍵詞】：限制性K-樹(shù) 可交換邊對(duì) 多項(xiàng)式時(shí)間算法 復(fù)雜性
【學(xué)位授予單位】：云南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
【目錄】：

• 摘要3-4
• Abstract4-7
• 第一章 引言7-10
• 1.1 理論背景7-8
• 1.2 主要結(jié)果8
• 1.3 論文結(jié)構(gòu)8-10
• 第二章 預(yù)備知識(shí)10-15
• 2.1 圖論10-12
• 2.2 組合最優(yōu)化12-15
• 第三章 K-樹(shù)問(wèn)題及求解算法15-20
• 3.1 最小支撐樹(shù)問(wèn)題15-16
• 3.2 限制度最小支撐樹(shù)問(wèn)題16-18
• 3.3 限制度的最小K-樹(shù)問(wèn)題18-20
• 第四章 限制兩個(gè)頂點(diǎn)度的最小K-樹(shù)問(wèn)題20-45
• 4.1 問(wèn)題描述20
• 4.2 主要結(jié)果及證明20-40
• 4.3 求解算法40-41
• 4.4 算例41-45
• 結(jié)論45-46
• 附錄46-85
• 參考文獻(xiàn)85-87
• 致謝87

【共引文獻(xiàn)】

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

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

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

3 楊羅輝;;一類基于模糊圖論的費(fèi)用與時(shí)間最優(yōu)化問(wèn)題的模型[J];長(zhǎng)春大學(xué)學(xué)報(bào);2007年12期

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

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

6 胡雷剛;付新華;肖明清;許明;;基于隨機(jī)遺傳算法的并行測(cè)試任務(wù)調(diào)度研究[J];電測(cè)與儀表;2008年10期

7 林農(nóng);;旅行商問(wèn)題圖論近似算法有效性分析[J];東莞理工學(xué)院學(xué)報(bào);2012年01期

8 鄧豐;陳楠;曾祥君;李澤文;程遠(yuǎn)林;袁超;;基于圖論的電網(wǎng)故障行波定位裝置最優(yōu)配置算法[J];電力系統(tǒng)自動(dòng)化;2010年11期

9 左鄭敏,吳耀武,熊信艮,張正陵;聯(lián)合電力網(wǎng)中最短路徑的小偏差量δ算法[J];電力系統(tǒng)及其自動(dòng)化學(xué)報(bào);2000年06期

10 陳自力;潘燕燕;王軍祥;;最小費(fèi)用算法在城市交通網(wǎng)絡(luò)中的應(yīng)用[J];電腦知識(shí)與技術(shù);2006年20期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前10條

1 李桂平;陳楠;;多中心車輛路徑問(wèn)題的解決思路[A];中國(guó)地理信息系統(tǒng)協(xié)會(huì)第四次會(huì)員代表大會(huì)暨第十一屆年會(huì)論文集[C];2007年

2 冷洪澤;謝政;徐楨;;基于帶固定費(fèi)用運(yùn)輸問(wèn)題的自適應(yīng)并行搜索算法研究[A];2008通信理論與技術(shù)新進(jìn)展——第十三屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集（上）[C];2008年

3 藍(lán)伯雄;張躍;;物流配送中的優(yōu)化問(wèn)題[A];全國(guó)第七屆工業(yè)工程與企業(yè)信息化學(xué)術(shù)會(huì)議論文集[C];2003年

4 陳豪;何童;李傳臚;;多層電磁屏蔽拓?fù)鋱D的分析方法及應(yīng)用[A];2005通信理論與技術(shù)新進(jìn)展——第十屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集[C];2005年

5 胡向東;王平;聶能;陳天基;;郵政運(yùn)輸指揮調(diào)度網(wǎng)路優(yōu)化系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[A];1999年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（下冊(cè)）[C];1999年

6 王平;胡向東;;敏捷制造模式下的物流配送決策支持系統(tǒng)[A];2001年中國(guó)智能自動(dòng)化會(huì)議論文集（下冊(cè)）[C];2001年

7 谷煒;張群;衛(wèi)李蓉;;基于GIS的物流配送中心末端大規(guī)模車輛路徑優(yōu)化問(wèn)題研究[A];“兩型社會(huì)”建設(shè)與管理創(chuàng)新——第十五屆中國(guó)管理科學(xué)學(xué)術(shù)年會(huì)論文集（上）[C];2013年

8 候建鑫;馬國(guó)華;謝瑜;;成品油氣輸送管網(wǎng)模擬與優(yōu)化[A];石化產(chǎn)業(yè)創(chuàng)新·綠色·可持續(xù)發(fā)展——第八屆寧夏青年科學(xué)家論壇石化專題論壇論文集[C];2012年

9 Yi Zhang;Mengxiang Zhang;;Research on Logistics Cost Control of Coal Enterprises[A];第26屆中國(guó)控制與決策會(huì)議論文集[C];2014年

10 余，

本文編號(hào)：837813