限制一个顶点度的K-树构建问题

发布时间：2020-09-02 11:10

　　 限制性最小K-树问题是算法图论中的一个经典的研究问题,它具有比较实际的应用背景和理论研究价值。本文主要研究限制顶点度的最小K-树构建问题,该问题是限制顶点度的最小支撑树构建问题和最小K-树问题的推广,具体问题描述为:给定一个n`1阶的赋权图G“pV,E;wq,这里函数w:E?R~`,v_0P V,非负整数K和正整数d,构建一棵限制顶点v_0的度为d_(TK)pv_0q“d的K-树T_K“pV,E_Kq,e P E_K,它的n`K条边由长度为L的若干材料来构建,c_0表示长度为L的每根材料的售价,kpT_Kq表示所需材料的根数,cpeq表示边e的施工费。问题的目标是使得构建限制顶点度的K-树所有边的费用总和最小,即mint?_(ePEK)cpeq`kpT_Kq¨c_0u。在构建时考虑有没有施工费用的两种情况,第一种情况,考虑在有施工费用时,来解决限制一个顶点度的K-树构建问题,设计了DCKTC算法,它是一个2-近似算法,该算法的时间复杂度为Opn~3q。第二种情况,考虑施工费用为0时,来解决限制一个顶点度的K-树构建问题,设计了DCKTP算法,其复杂度为Opn~3q。在DCKTC算法的理论基础上,对其进行MATLAB语言编程,程序由四部分组成,分别是DCKTC算法主程序、Prim算法子程序、Fisher算法子程序和ChangeDegree子程序。
【学位单位】：云南大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP301.6;O157.5

【相似文献】

相关期刊论文 前10条

1 姚兵;;关于树基数的不等式[J];西北师范大学学报(自然科学版);1987年01期

2 戴祖旭;无向简单图顶点度数的一个性质[J];培训与研究(湖北教育学院学报);2004年02期

3 刘翼举;侯耀平;;一些由它的邻接谱和角确定的图[J];邵阳学院学报(自然科学版);2009年02期

4 彭波;高炜;;特殊框架下分数(g,f,m)-消去图的不相邻顶点度条件[J];山西大学学报(自然科学版);2017年02期

5 傅春花;徐秀莲;何大韧;;大数据背景下一类社会网统计性质的初步研究[J];计算机时代;2019年01期

6 袁履冰;丁勇;;计算共振能的一个新的经验方法[J];化学研究与应用;1991年04期

7 张培培;何阅;周涛;苏蓓蓓;常慧;周月平;汪秉宏;何大韧;;一个描述合作网络顶点度分布的模型[J];物理学报;2006年01期

8 林政宽;赵源;樊建席;程宝雷;;基于顶点度数的完全独立生成树研究[J];计算机科学;2017年06期

9 吕剑波;;含k个顶点度为n-1的简单连通图的调和指标[J];漳州师范学院学报(自然科学版);2013年03期

10 董显亮;对Bermond猜想(32)的一个注记[J];本溪冶金高等专科学校学报;2001年02期

相关会议论文 前1条

1 于博;李建中;王宏志;高宏;;超大有向图上Top-k顶点度查询的一种有效处理方法[A];第二十三届中国数据库学术会议论文集（技术报告篇）[C];2006年

相关博士学位论文 前2条

1 周金红;大规模图计算系统关键技术研究[D];中国科学技术大学;2017年

2 李静;关于图的能量和斜能量的若干极值问题[D];南开大学;2013年

相关硕士学位论文 前10条

1 李明亮;限制一个顶点度的K-树构建问题[D];云南大学;2018年

2 秧柳;限制顶点度的最小K-树问题[D];云南大学;2017年

3 龙浩;以簇为中心的大规模图数据分布式处理系统[D];华中科技大学;2017年

4 肖威;面向动态大图的异步增量计算优化机制[D];华中科技大学;2018年

5 黄仁毅;限制两个顶点度的最小K-树问题[D];云南大学;2015年

6 贺国卿;随机图上顶点度数序列及树分图的分布[D];天津大学;2010年

7 何守伟;荧蒽型苯环系统的基于顶点度的拓扑指数[D];湖南师范大学;2017年

8 骆晓波;多图中的度匿名隐私保护算法[D];电子科技大学;2013年

9 陈功;图的拓扑指标与结构性质若干问题的研究[D];深圳大学;2016年

10 朱笑然;网络关系数据可视化研究与实现[D];北京邮电大学;2017年

本文编号：2810519