【摘 要】
：
限制性最小K-树问题是算法图论中的一个经典的研究问题,它具有比较实际的应用背景和理论研究价值。本文主要研究限制顶点度的最小K-树构建问题,该问题是限制顶点度的最小支撑
论文部分内容阅读
限制性最小K-树问题是算法图论中的一个经典的研究问题,它具有比较实际的应用背景和理论研究价值。本文主要研究限制顶点度的最小K-树构建问题,该问题是限制顶点度的最小支撑树构建问题和最小K-树问题的推广,具体问题描述为:给定一个n`1阶的赋权图G“pV,E;wq,这里函数w:E?R`,v0P V,非负整数K和正整数d,构建一棵限制顶点v0的度为dTKpv0q“d的K-树TK“pV,EKq,e P EK,它的n`K条边由长度为L的若干材料来构建,c0表示长度为L的每根材料的售价,kpTKq表示所需材料的根数,cpeq表示边e的施工费。问题的目标是使得构建限制顶点度的K-树所有边的费用总和最小,即mint?ePEKcpeq`kpTKq¨c0u。在构建时考虑有没有施工费用的两种情况,第一种情况,考虑在有施工费用时,来解决限制一个顶点度的K-树构建问题,设计了DCKTC算法,它是一个2-近似算法,该算法的时间复杂度为Opn3q。第二种情况,考虑施工费用为0时,来解决限制一个顶点度的K-树构建问题,设计了DCKTP算法,其复杂度为Opn3q。在DCKTC算法的理论基础上,对其进行MATLAB语言编程,程序由四部分组成,分别是DCKTC算法主程序、Prim算法子程序、Fisher算法子程序和ChangeDegree子程序。
其他文献
目的改良原代肝星状细胞(HSCs)提取方法,观察miR-148a诱导大鼠原代HSCs的自噬作用。方法从成年雄性SD大鼠分离出原代HSCs,并对其进行培养与鉴定,包括形态、得率、活力和纯度
目的:系统评价白藜芦醇治疗非酒精性脂肪性肝病(NAFLD)的疗效。方法:计算机检索Pub Med、The Cochrane Library、Web of Science、EMBASE、中国期刊全文数据库、中国科技期刊
良好的延迟满足能力能够帮助大学生取得成就,获得自我价值。在信息井喷、娱乐至上的当下,大学生面对诸多诱惑更需要保持良好的延迟满足能力。为了解大学生的一般延迟满足状况
井冈霉烯胺属于C7N氨基环醇类化合物,作为糖苷水解酶抑制剂的核心结构,是II型糖尿病治疗药物阿卡波糖和伏格列波糖的共同前体,对糖尿病及相关疾病药物研发具有重要意义。目前
超快脉冲光纤激光器在光通信、材料加工、医学以及光谱学等领域都有广泛的应用。光纤激光器中广泛应用到的可饱和吸收体是一种非线性光学元件,能够将低能量的连续光转化为高
随着互联网高速发展,对相关人才的需求急剧增长。MOOC(Massive Open Online Courses)的兴起,对开放式教育产生了巨大影响,但因在实验教学上的不足,MOOE(Massive Open Online Experiments)便应运而生。MOOE的出现打破了传统实验教学中时间与场地的限制,真正实现了各能力层次、各行业背景的“学生”用户随时随地、按需选择的自主实验学习,因此,开发
双层规划问题是一类二层递阶结构的系统优化问题.上层和下层都有各自的目标函数和约束条件.然而,在解决实际问题过程中常常会受到一些随机因素的影响,例如:天气、需求、价格等,如果决策者在解决实际问题的过程中忽视这些因素的存在,将会导致决策失误,无法得到有效合理的结果.因此,学者逐渐考虑含有随机因素的双层规划问题即,随机双层规划问题.由于随机变量的存在,使得随机双层规划问题在一般条件下通常无解,为了满足含
数字半群作为一种特殊的含幺半群,在代数学的其他领域有许多应用,人们对此也展开广泛的研究。最开始是由Urbano-Blanco等人在研究了丢番图不等式之后,证明了丢番图不等式的非负解集是一个数字半群。他们称这种数字半群叫比例模数字半群,也正是为了描述比例模数字半群的概念,他们提出了数字半群商的概念。文章通过J.C.Rosales对数字半群的有关理论研究,进一步地对数字半群的商,以及一些典型数字半群商
农村承包地作为农业生产的物理承载和关键要素,其流转情况将对农业的现代化发展产生重大而深远的影响。认识和分析哪些因素会在多大程度上影响农户流出土地承包经营权的行为,对于促进农村土地适度规模化流转,提高农业生产效率,加快“三农”发展,最终实现乡村振兴具有重要意义。本文基于对安吉县样本农户的研究,通过梳理国内外土地流转相关文献,实地调研和发放调查问卷,建立Logistics回归模型,研究分析样本农户流出
大豆富含丰富的植物蛋白质和油脂,在人类生活中发挥着重要作用。同时,大豆也是典型的生物固氮作物,为植物的生长发育提供了充足的清洁氮源,对发展可持续绿色农业具有重要意义