调整和权值下一类极大加和支撑树逆问题

发布时间：2017-08-26 20:23

  本文关键词：调整和权值下一类极大加和支撑树逆问题

  更多相关文章： 极大+和支撑树逆问题 瓶颈型哈明距离 二分法 单位和型哈明距离 不可近似性 Lagrange对偶问题

【摘要】：本文研究的是一类调整和-费用向量时的极大+和支撑树逆问题(IMSST)极大+和支撑树问题(MSST)是在一个边赋权无向连通网络G(V,E,c,ω)中,找一棵最优支撑树T,使得目标函数maxe∈Tω(e)+∑e∈Tc(e)尽可能的小.本文研究的极大+和支撑树逆问题为：给定网络G的一棵非最优支撑树T0,调整网络各边的费用c(e)到c(e),使得T0为新网络G(V,E,c,ω)下的最优极大+和支撑树,其中0 c-l≤c≤c+ μ,l≥0,μ让≥O.目标函数是使得哈明距离下边权调整费用尽可能的小.第一章介绍了极大+和支撑树逆问题的背景和研究意义,并列出了研究哈明距离下极大+和支撑树逆问题需要的预备知识.第二章研究有界瓶颈型哈明距离下极大+和支撑树逆问题.首先给出了该问题的数学模型,进而分析了其解的性质和可行性检验方法；接着设计求解该问题的二分法,并分析了算法的复杂度为O(mlog~2(n)),其中n为顶点的个数;最后进行数值实验,检验该算法的有效性.第三章研究单位和型哈明距离下极大+和支撑树逆问题.先证明该问题为NP-难的,而NP-难问题很难找到最优解,因此我们分析了该问题的不可近似性.最后以该问题的扩充问题为媒介求得该问题的近似解.第四章对本文做出总结并对极大+和支撑树逆问题未来的研究方向进行展望.
【关键词】：极大+和支撑树逆问题 瓶颈型哈明距离 二分法 单位和型哈明距离 不可近似性 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 模、共轭函数、Lagrange对偶函数17-23
• 1.4.1 向量的模17-19
• 1.4.2 矩阵的模19
• 1.4.3 对偶模、共轭函数19-20
• 1.4.4 Lagrange对偶函数20-23
• 1.5 本文主要研究工作23-24
• 第二章 有界瓶颈型哈明距离下的极大+和支撑树逆问题24-35
• 2.1 IMSST_(BH)~b的数学模型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 数值实验33-35
• 第三章 单位和型哈明距离下的极大+和支撑树逆问题35-47
• 3.1 l_0模下极大+和支撑树逆问题的数学模型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

【相似文献】

中国期刊全文数据库 前10条

1 周丽,黄哲浩,王博,贺北方;求最小支撑树的方法探讨[J];郑州工业大学学报;2001年03期

2 李帮义,姚恩瑜;严格第k最小支撑树问题[J];系统工程理论与实践;2002年01期

3 连海峰,雷雪萍;最小支撑树的新算法[J];淮阴师范学院学报(自然科学版);2004年01期

4 王泽磊,张同全,李建平;关于K棵支撑树的2个问题[J];云南大学学报(自然科学版);2004年S1期

5 付铅生,李帮义;Pendants-median支撑树及其一个相关问题:复杂性和算法[J];高等学校计算数学学报;2004年02期

6 李淑君;唐恒永;;约束最小支撑树问题[J];沈阳师范大学学报(自然科学版);2006年01期

7 许进;;几类图的支撑树的计数公式[J];西北大学学报(自然科学版);1989年04期

8 周德镇;;最小支撑树简算法及其应用[J];管理现代化;1993年02期

9 朱娟萍;吴旭亭;杨子兰;;网络中支撑树的边扩容问题[J];云南大学学报(自然科学版);2013年05期

10 左霞;关秀翠;;一类特殊的极大+和支撑树在调整和权值下的逆问题[J];南京大学学报(数学半年刊);2013年02期

中国博士学位论文全文数据库 前4条

1 章舜哲;图的哈密尔顿连通性及支撑树特征研究[D];华中师范大学;2015年

2 陈园;图中参数与树型结构研究[D];华中师范大学;2013年

3 刘龙城;赋权哈明距离下若干网络逆问题的研究[D];浙江大学;2009年

4 张斌武;哈明距离下的逆优化问题及多物品的制造与分配问题[D];浙江大学;2005年

中国硕士学位论文全文数据库 前9条

1 朱芳;几类网络改进问题的算法研究[D];中国计量学院;2015年

2 何新燕;调整和权值下一类极大加和支撑树逆问题[D];东南大学;2015年

3 王芳;网络中的均匀度问题和比值问题[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