限制出度的最小K-树形图问题

发布时间：2017-10-09 05:38

  本文关键词：限制出度的最小K-树形图问题

  更多相关文章： 限制出度 K-树形图 算法 复杂性

【摘要】：本论文主要研究有向图中限制出度的最小K-树形图问题,其叙述如下：给定一个n+1阶含有m条弧的赋权有向连通图D=(V,A；ω),这里函数ω：A→R+,在D中寻找一个含n+K条弧的子集H,满足诱导子图D[H]含有一棵以固定顶点为根的支撑树形图,限制固定顶点的出度为一个常数且不含有向圈,目标是使得H中所有弧的权重之和达到最小。 本论文首先把有向图中限制出度的最小K-树形图问题分解成限制出度最小支撑树形图问题和最小K-树形图问题来研究。对限制出度最小支撑树形图问题,设计出一种O(n3m)的多项式时间算法。对最小K-树形图问题,设计出一种O(m2lgm)的多项式时间算法。然后,结合上述两个算法思想,设计出一个多项式时间算法来解决限制出度的最小K-树形图问题,其复杂性为O(n3m)。
【关键词】：限制出度 K-树形图 算法 复杂性
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要3-4
• Abstract4-5
• 目录5-6
• 第一章 引言6-9
• 1.1 理论背景6-7
• 1.2 主要结果7
• 1.3 论文结构7-9
• 第二章 预备知识9-18
• 2.1 图论9-11
• 2.2 组合最优化11-15
• 2.3 最小支撑树形图问题及算法15-18
• 第三章 限制出度的最小K-树形图问题及其算法18-39
• 3.1 限制出度最小支撑树形图问题及其算法18-26
• 3.2 最小K-树形图问题及其算法26-28
• 3.3 限制出度的最小K-树形图问题及其算法28-30
• 3.4 算例30-39
• 结论39-40
• 参考文献40-43
• 致谢43

【共引文献】

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

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

2 张彬;袁丛鑫;司璇;金飞;;基于图论的数字图像边缘检测算法[J];中国传媒大学学报(自然科学版);2011年03期

3 张忠海;李端玲;廖启征;;柔性变胞机构的拓扑结构表示及构态变换分析[J];北京邮电大学学报;2010年03期

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

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

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

7 涂冰英;;实时动态最佳路径的实现方法[J];测绘信息与工程;2006年03期

8 郭纪云;;每棵非平凡树至少有两片叶子的证法研究[J];长沙大学学报;2011年05期

9 叶玉民,周立新,胡小倩;关于最佳粮库地址的选择[J];东北电力学院学报;2001年01期

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

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

1 王伟;铁路网抗毁性分析与研究[D];北京交通大学;2011年

2 陈德良;物流网络可靠性的关键问题与应用研究[D];中南大学;2010年

3 邱宇;基于双边滤波的图像去噪及锐化技术研究[D];重庆大学;2011年

4 王兵;逻辑进程范型的形式语义、算法评估及其在空间随机仿真中的应用[D];国防科学技术大学;2011年

5 李光;分类挖掘中的隐私保护问题研究[D];哈尔滨工业大学;2011年

6 张强;基于连通性的无线传感器网络节点定位技术研究[D];天津大学;2011年

7 王旭东;基于图论的智能电网最优孤岛划分模型和算法[D];天津大学;2011年

8 杨威;协作认知无线电网络优化模型与算法研究[D];国防科学技术大学;2011年

9 葛悦;模糊环境下若干网络优化问题的模型及其算法研究[D];哈尔滨工业大学;2012年

10 牛东晓;非确定性工程项目计划管理的新方法研究[D];华北电力大学;2002年

，

本文编号：998459