本文關鍵詞：調整和權值下一類極大加和支撐樹逆問題

  更多相關文章： 極大+和支撐樹逆問題 瓶頸型哈明距離 二分法 單位和型哈明距離 不可近似性 Lagrange對偶問題

【摘要】：本文研究的是一類調整和-費用向量時的極大+和支撐樹逆問題(IMSST)極大+和支撐樹問題(MSST)是在一個邊賦權無向連通網(wǎng)絡G(V,E,c,ω)中,找一棵最優(yōu)支撐樹T,使得目標函數(shù)maxe∈Tω(e)+∑e∈Tc(e)盡可能的小.本文研究的極大+和支撐樹逆問題為：給定網(wǎng)絡G的一棵非最優(yōu)支撐樹T0,調整網(wǎng)絡各邊的費用c(e)到c(e),使得T0為新網(wǎng)絡G(V,E,c,ω)下的最優(yōu)極大+和支撐樹,其中0 c-l≤c≤c+ μ,l≥0,μ讓≥O.目標函數(shù)是使得哈明距離下邊權調整費用盡可能的小.第一章介紹了極大+和支撐樹逆問題的背景和研究意義,并列出了研究哈明距離下極大+和支撐樹逆問題需要的預備知識.第二章研究有界瓶頸型哈明距離下極大+和支撐樹逆問題.首先給出了該問題的數(shù)學模型,進而分析了其解的性質和可行性檢驗方法；接著設計求解該問題的二分法,并分析了算法的復雜度為O(mlog~2(n)),其中n為頂點的個數(shù);最后進行數(shù)值實驗,檢驗該算法的有效性.第三章研究單位和型哈明距離下極大+和支撐樹逆問題.先證明該問題為NP-難的,而NP-難問題很難找到最優(yōu)解,因此我們分析了該問題的不可近似性.最后以該問題的擴充問題為媒介求得該問題的近似解.第四章對本文做出總結并對極大+和支撐樹逆問題未來的研究方向進行展望.
【關鍵詞】：極大+和支撐樹逆問題 瓶頸型哈明距離 二分法 單位和型哈明距離 不可近似性 Lagrange對偶問題
【學位授予單位】：東南大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O221
【目錄】：

• 摘要4-5
• Abstract5-9
• 第一章 緒論9-24
• 1.1 研究背景及意義9-12
• 1.2 支撐樹的基礎知識12-13
• 1.3 算法復雜性簡介13-17
• 1.3.1 算法的基本概念14-16
• 1.3.2 算法的設計16-17
• 1.4 模、共軛函數(shù)、Lagrange對偶函數(shù)17-23
• 1.4.1 向量的模17-19
• 1.4.2 矩陣的模19
• 1.4.3 對偶模、共軛函數(shù)19-20
• 1.4.4 Lagrange對偶函數(shù)20-23
• 1.5 本文主要研究工作23-24
• 第二章 有界瓶頸型哈明距離下的極大+和支撐樹逆問題24-35
• 2.1 IMSST_(BH)~b的數(shù)學模型24-27
• 2.2 IMSST_(BH)~b的算法27-35
• 2.2.1 IMSS_(BH)~b的可行性27-28
• 2.2.2 IMSST_(BH)~b的算法28-31
• 2.2.3 IMSST_(BH)~b的一個實例31-33
• 2.2.4 數(shù)值實驗33-35
• 第三章 單位和型哈明距離下的極大+和支撐樹逆問題35-47
• 3.1 l_0模下極大+和支撐樹逆問題的數(shù)學模型35-37
• 3.2 l_0模下極大+和支撐樹逆問題的不可近似性37-41
• 3.2.1 不可近似性理論的相關定義37-39
• 3.2.2 l_0模下極大+和支撐樹逆問題的復雜性和不可近似性39-41
• 3.3 l_0模下極大+和支撐樹逆問題的近似解41-47
• 3.3.1 標準化模型41
• 3.3.2 l_0模下極大+和支撐樹逆問題的擴充問題41-43
• 3.3.3 l_0模和l_1模下極大+和支撐樹逆問題的Lagrange對偶問題43-46
• 3.3.4 單位和型哈明距離下極大+和支撐樹逆問題的近似解46-47
• 第四章 總結與展望47-48
• 致謝48-49
• 參考文獻49-52

【相似文獻】

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

1 周麗,黃哲浩,王博,賀北方;求最小支撐樹的方法探討[J];鄭州工業(yè)大學學報;2001年03期

2 李幫義,姚恩瑜;嚴格第k最小支撐樹問題[J];系統(tǒng)工程理論與實踐;2002年01期

3 連海峰,雷雪萍;最小支撐樹的新算法[J];淮陰師范學院學報(自然科學版);2004年01期

4 王澤磊,張同全,李建平;關于K棵支撐樹的2個問題[J];云南大學學報(自然科學版);2004年S1期

5 付鉛生,李幫義;Pendants-median支撐樹及其一個相關問題:復雜性和算法[J];高等學校計算數(shù)學學報;2004年02期

6 李淑君;唐恒永;;約束最小支撐樹問題[J];沈陽師范大學學報(自然科學版);2006年01期

7 許進;;幾類圖的支撐樹的計數(shù)公式[J];西北大學學報(自然科學版);1989年04期

8 周德鎮(zhèn);;最小支撐樹簡算法及其應用[J];管理現(xiàn)代化;1993年02期

9 朱娟萍;吳旭亭;楊子蘭;;網(wǎng)絡中支撐樹的邊擴容問題[J];云南大學學報(自然科學版);2013年05期

10 左霞;關秀翠;;一類特殊的極大+和支撐樹在調整和權值下的逆問題[J];南京大學學報(數(shù)學半年刊);2013年02期

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

1 章舜哲;圖的哈密爾頓連通性及支撐樹特征研究[D];華中師范大學;2015年

2 陳園;圖中參數(shù)與樹型結構研究[D];華中師范大學;2013年

3 劉龍城;賦權哈明距離下若干網(wǎng)絡逆問題的研究[D];浙江大學;2009年

4 張斌武;哈明距離下的逆優(yōu)化問題及多物品的制造與分配問題[D];浙江大學;2005年

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

1 朱芳;幾類網(wǎng)絡改進問題的算法研究[D];中國計量學院;2015年

2 何新燕;調整和權值下一類極大加和支撐樹逆問題[D];東南大學;2015年

3 王芳;網(wǎng)絡中的均勻度問題和比值問題[D];國防科學技術大學;2004年

4 楊曉凌;最短路及最小支撐樹的靈敏度分析[D];國防科學技術大學;2007年

5 徐何花;K_(1,5)-free圖中的支撐樹[D];華中師范大學;2012年

6 潘陽;關于圖的最小線性布局的一些問題與結果[D];福州大學;2011年

7 王小燕;基于最小費用支撐樹的合作對策問題[D];國防科學技術大學;2005年

8 張春明;圖論在聚類分析中的應用[D];山東師范大學;2004年

9 王妍;圖的在支撐樹上作限制的L（p，1）-點標號及L（p，，q）-邊標號問題[D];山東師范大學;2012年

本文編號：742803