限制两个顶点度的最小K-树问题

发布时间：2017-09-12 14:33

  本文关键词：限制两个顶点度的最小K-树问题

  更多相关文章： 限制性K-树 可交换边对 多项式时间算法 复杂性

【摘要】：限制性K-树问题是一类组合优化问题,它具有重要的理论研究价值和实际应用价值。本论文研究限制性K-树问题的一种推广形式,称之为限制两个顶点度的最小K-树问题。该问题具体描述为：给定一个n+1阶赋权图G=(V,E;w),这里函数w:E→R+,两个固定顶点vs,vt∈V及两个正整数k1和k2与一个非负整数K,寻找图G的一棵K-树TKst,使之满足dTKst(Vs)=k1,和dTKst(Vt)=k2,目标是使TKst所有边的权重之和w(TKst)=∑e∈TKstw(e)达到最小。 本论文设计了一个多项式时间算法来解决限制两个顶点度的最小K-树问题,算法复杂性为(?)(n4)；并对这个算法进行MATLAB编程并实现了算例。
【关键词】：限制性K-树 可交换边对 多项式时间算法 复杂性
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要3-4
• Abstract4-7
• 第一章 引言7-10
• 1.1 理论背景7-8
• 1.2 主要结果8
• 1.3 论文结构8-10
• 第二章 预备知识10-15
• 2.1 图论10-12
• 2.2 组合最优化12-15
• 第三章 K-树问题及求解算法15-20
• 3.1 最小支撑树问题15-16
• 3.2 限制度最小支撑树问题16-18
• 3.3 限制度的最小K-树问题18-20
• 第四章 限制两个顶点度的最小K-树问题20-45
• 4.1 问题描述20
• 4.2 主要结果及证明20-40
• 4.3 求解算法40-41
• 4.4 算例41-45
• 结论45-46
• 附录46-85
• 参考文献85-87
• 致谢87

【共引文献】

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

1 孙小军;王志强;;带负权最短路问题前趋法的改进[J];安徽大学学报(自然科学版);2009年02期

2 王德忠,方健;切槽加工走刀路径优化问题的处理[J];包装工程;2002年04期

3 杨罗辉;;一类基于模糊图论的费用与时间最优化问题的模型[J];长春大学学报;2007年12期

4 郝自军;何尚录;;最短路问题的Floyd算法的若干讨论[J];重庆工学院学报(自然科学版);2008年05期

5 王兴伟,王岳昭,郑连伟,刘积仁;一种基于服务质量的点对点通信路由选择算法[J];东北大学学报;2000年02期

6 胡雷刚;付新华;肖明清;许明;;基于随机遗传算法的并行测试任务调度研究[J];电测与仪表;2008年10期

7 林农;;旅行商问题图论近似算法有效性分析[J];东莞理工学院学报;2012年01期

8 邓丰;陈楠;曾祥君;李泽文;程远林;袁超;;基于图论的电网故障行波定位装置最优配置算法[J];电力系统自动化;2010年11期

9 左郑敏,吴耀武,熊信艮,张正陵;联合电力网中最短路径的小偏差量δ算法[J];电力系统及其自动化学报;2000年06期

10 陈自力;潘燕燕;王军祥;;最小费用算法在城市交通网络中的应用[J];电脑知识与技术;2006年20期

中国重要会议论文全文数据库 前10条

1 李桂平;陈楠;;多中心车辆路径问题的解决思路[A];中国地理信息系统协会第四次会员代表大会暨第十一届年会论文集[C];2007年

2 冷洪泽;谢政;徐桢;;基于带固定费用运输问题的自适应并行搜索算法研究[A];2008通信理论与技术新进展——第十三届全国青年通信学术会议论文集（上）[C];2008年

3 蓝伯雄;张跃;;物流配送中的优化问题[A];全国第七届工业工程与企业信息化学术会议论文集[C];2003年

4 陈豪;何童;李传胪;;多层电磁屏蔽拓扑图的分析方法及应用[A];2005通信理论与技术新进展——第十届全国青年通信学术会议论文集[C];2005年

5 胡向东;王平;聂能;陈天基;;邮政运输指挥调度网路优化系统的设计与实现[A];1999年中国智能自动化学术会议论文集（下册）[C];1999年

6 王平;胡向东;;敏捷制造模式下的物流配送决策支持系统[A];2001年中国智能自动化会议论文集（下册）[C];2001年

7 谷炜;张群;卫李蓉;;基于GIS的物流配送中心末端大规模车辆路径优化问题研究[A];“两型社会”建设与管理创新——第十五届中国管理科学学术年会论文集（上）[C];2013年

8 候建鑫;马国华;谢瑜;;成品油气输送管网模拟与优化[A];石化产业创新·绿色·可持续发展——第八届宁夏青年科学家论坛石化专题论坛论文集[C];2012年

9 Yi Zhang;Mengxiang Zhang;;Research on Logistics Cost Control of Coal Enterprises[A];第26届中国控制与决策会议论文集[C];2014年

10 余，

本文编号：837813