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

《限制两个顶点度的最小K-树问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级好编号碛士蚵究嗲像铪夂题目限制两个顶点度的最小树问题学院（所、中心）数学与统计学院专业名称计算数学研究生姓名黄仁毅学号导师姓名李建平职称謝受年月论文独创性声明及使用授权本论文是作者在导师指导取得的研究成果。降了文中特另挺幽挂和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不存在剽窃或抄袭行为。与作者一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。现就论文的使用对云南大学授权如下：学校有权保留本论文（含电子版），也可以采用影印、缩印或其他复制手段

2、保存论文；学校有权公布论文的全部或部分内容，可以将论文用于查阅或借阅服务；学校有权向有关机构送交学位论文用于学术规范审查、社会监督或评奖；学校有权将学位论文的全部或部分内容录入有关数据库用于检索服务。内部或保密的论文在解密后应遵循此规定）摘要限制性树问题是一类组合优化问题，它具有重要的理论研宄价值和实际应用价值。本论文研宄限制性欠树问题的一种推广形式，称之为限制两个顶点度的最小树问题。该问题具体描述为：给定一个阶赋权图—；丑；切这里函数—，两个固定顶点及两个正整数幻和与一个非负整数夂，寻找图的一

3、棵树麥，使之满足和目标是使挖所有边的权重之和达到最小。本论文设计了一个多项式时间算法来解决限制两个顶点度的最小树问题，算法复杂性为并对这个算法进行编程并实现了算例。关键词：限制性树；可交换边对；多项式时间算法；复杂性AbstractThedegree-constrainedK-treeproblemisaclassofcombinatorialoptimizationproblems.Ithasveryimportanttheoreticalresearchvalueandactualappli

4、cationvalue.Weconsiderageneralizationofthedegree-constrainedK-ireeproblem,i.e.thetwovertices-fixeddegree-constrainedminimumK-txeeproblem,itcanbedifinedasfollows:givenaweightedgraphG={V^E;w)^wherew:E—益，：目录摘要第一章引言理论背景主要结果论文结构第二章预备知识隠组合最优化第三章九树问题及求解算法最小

5、支撑树问题限制度最小支撑树问题限制度的最小欠树问题第四章限制两个顶点度的最小欠树问题问题描述主要结果及证明求解算法算例结论附录参考文献致谢第一章引言§理论背景网络问题是一类重要的组合优化问题，它具有重要的理论研宄价值和很强的实际应用价值。网络问题包括很多具体问题，如最小支撑树问题，限制度最小支撑树问题和限制性：树问题等。在这些问题中，最小支撑树问题已经被人们研究得很成熟了，应用最小支撑树问题算法解决了许多实际问题。现在人们感兴趣是研究支撑树问题的推广形式，称之为限制性树问题。人们熟知最小支撑树问

6、题。该问题具体描述为给定一个赋权图；丑《；，这里函数：—寻找图的一棵支撑树；目标是使所有边的权重之和⑷达到最小。在年设计出一个时间复杂性为的多项式时间算法来解决这个问题。在年也设计一个时间复杂度为的多项式时间的最优算法。最小支撑树问题的算法在现实生活中有很多应用。例如，一个地区的电话线网安装问题，既要满足每户人家用电话的需求，又要使得电话线总长度最短。和在年提出最小支撑树问题的一种推广形式，称之为限制度最小支撑树问题。该问题具体描述为：给定一个赋权图这里函数：，固定顶点为给定的正整数，寻找图的一

7、棵支撑树丑，使之满足，目标是使得所有边权重之和—最小。他们也设计出了多项式时间的最优算法来解决限制度最小支撑树问题。限制度最小支撑树问题的算法在生活中应用广泛。例如：在电话线路网中，我们要求从总机直接引出的电话线恰好为：条，在这一限制下，要设计一条总长度最短的电话线路网。人们已经开始研究限制度的最小树问该问题具体描述为：给定一个赋权图￡，这里函数—个正整数和一个非负整数，构造图的一棵树五，使之满足如目标是使中所有边权重之和达到最小。在年设计了一个多项式时间最优算法来解决限制度的最小：树问题，其复

8、杂性为；。本论文考虑一个实际问题：假设某市有两个公交综合运输枢纽，包括这两个枢纽在内总共有个车站，根据公交公司计划，要求从两个枢纽发出的车辆分别为和知，且到达所有车站总共只经历：条边，目标是这：条边的总长达到最小。该问题可以抽象为限制两个顶点度的最小■树问题简记为我们把限制两个顶点度的最小树问题描述为：给定一个赋权图；这里函数—、两个固定顶点及两个正整数：和与一个非负整数，要求构造图的一棵树，使之满和；￡；，目标是使所有边的权重之和《穿达到最小。限制两个顶点度最小树问题在实际生活、生产和科研领域