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

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

1、分类号密级公幵编号七擘碛士研究嗲像伦夂题目艮制出度的曇小树形图问匾学院（所、中心）数学与统计学院专业名称运赛学与控制研究生姓名夏先锋学号导师姓名李建平职称教授年月扉页论文独创性声明及使用授权本论文是作者在导师栺导下取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研宄成果，不存在剽窃或抄袭行为。与作者一同工作的同志对本研宄所做的任何贡献均己在论文中作了明确的说明并表示了谢意。现就论文的使用对云南大学授权如下：学校有权保留本论文（含电子版），也可以釆用影印、缩印或其他复制手段保存论文；学校有权公布论

2、文的全部或部分内容，可以将论文用于查阅或借阅服务；学校有权向有关机构送交学位论文用于学术规范审查、社会监督或评奖；学校有权将学位论文的全部或部分内容录入有关数据库用于检索服务。内部或保密的论文在解密后应遵循此规定）研究生签名导师签名日期胸摘要本论文主要研究有向图中限制出度的最小【树形图问题，其叙述如下：给定一个阶含有条弧的赋权有向连通图这里函数：在中寻找一个含条弧的子集丑，满足诱导子图￡丑含有一棵以固定顶点为根的支撑树形图，限制固定顶点的出度为一个常数且不含有向圈，目标是使得丑中所有弧的权重之和达到最小。本论文首先把有向图中限制出度的

3、最小树形图问题分解成限制出度最小支撑树形图问题和最小欠树形图问题来研宄。对限制出度最小支撑树形图问题，设计出一种的多项式时间算法。对最小树形图问题，设计出一种的多项式时间算法。然后，结合上述两个算法思想，设计出一个多项式时间算法来解决限制出度的最小树形图问题，其复杂性为。关键词：限制出度；树形图；算法；复杂性AbstractInthisthesis,wemainlyconsidertheconstrainedout-degreeminimumK-arborescenceproblem,whichisdefinedasfollows:g

4、ivenaweighteddigraphD=(V,Aw)withn+1verticesandmarcs,wherew:weareaskedtofindasubsetHofn+KarcsinDsothatthesubgraphD[H]inducedbyHhasaspanningarborescencewithafixedroot,andtheout-degreeoffixedrootisaconstant,andD[H]containnodirectedcycles,theobjectiveistominimizethetotalwe

5、ightofarcsinH,Inthisthesis,wedecomposetheconstrainedout-degreeminimumif-arboresce-nceproblemintotheconstrainedout-degreeminimumarborescenceproblemandtheminimumK-arborescenceproblem,wepresentapolynomial-timealgorithmtosolvetheconstrainedout-degreeminimumarborescenceprobl

6、em，目录摘要第一章引言理论背景主要结果论文结构第二章预备知识■仓组合最优化最小支撑树形图问题及算法第三章艮制出度的最小树形图问题及其算法限制出度最小支撑树形图问题及其算法最小树形图问题及其算法限制出度的最小树形图问题及其算法算例结论参考文献致谢第一章引言§理论背景本论文提出了有向图中限制出度的最小：树形图问题，即树形图问题，这里。是一个给定的顶点，是一个非负整数。限制出度的最小树形图问题叙述如下：给定一个阶含条弧的赋权有向连通图这里函数：—是一个给定的顶点，是一个非负整数，在中寻找一个含：条弧的子集，满足诱导子图含有一棵以固定顶点为

7、根的支撑树形图，限制固定顶点训的出度为一个常数且不含有向圈，目标使得丑中所有弧的权重之和达到最小。限制出度的最小树形图是对限制度最小费用树的推广。在年，对最小支撑树问题进行研究，设计出的多项式时间算法来解决最小支撑树问题。最小支撑树主要应用于连接个城市的交通网络构建问题。在年，朱永津和刘振宏对最小支撑树形图问题进行研宄，设计出的多项式时间算法来解决最小支撑树形图问题。最小支撑树形图主要应用于修建水渠灌概庄家等问题。在年，】独立提出最优分枝问题，并且设计出的多项式时间算法来解决最优分枝问题。最优分枝问题和最小支撑树形图问题是等价的。在年

8、，和⑷研宄最小度限制树问题，设计出的多项式时间算法来解决最小度限制树问题。最小度限制树主要应用于电话机的总机和分机安装问题。在年，和对支撑树算法做了不同的修改得到了一’个交通路径问题的下界。在年，和基于和的结果，设计出了