【摘 要】
：
限制性K-树问题是一类组合优化问题,它具有重要的理论研究价值和实际应用价值。本论文研究限制性K-树问题的一种推广形式,称之为限制两个顶点度的最小K-树问题。该问题具体描
论文部分内容阅读
限制性K-树问题是一类组合优化问题,它具有重要的理论研究价值和实际应用价值。本论文研究限制性K-树问题的一种推广形式,称之为限制两个顶点度的最小K-树问题。该问题具体描述为：给定一个n+1阶赋权图G=(V,E;w),这里函数w:E→R+,两个固定顶点vs,vt∈V及两个正整数k1和k2与一个非负整数K,寻找图G的一棵K-树TKst,使之满足dTKst(Vs)=k1,和dTKst(Vt)=k2,目标是使TKst所有边的权重之和w(TKst)=∑e∈TKstw(e)达到最小。本论文设计了一个多项式时间算法来解决限制两个顶点度的最小K-树问题,算法复杂性为(?)(n4)；并对这个算法进行MATLAB编程并实现了算例。
其他文献
大规模场景的地图构建是地图测绘的重要任务之一,为自动驾驶、导航定位等提供重要的数据基础。然而地图测绘需要多种高精度传感器以及巨大的人力物力,制图效率较低。近年来,基于SLAM(Simultaneous Localization and Mapping)系统的建图方法受到学者们的广泛关注,但是受限于硬件基础和高计算复杂度使得在面对大场景的地图构建时存在极大的挑战,同时建图的结果由于稀疏特性无法应对稠
主要对一类具有时滞出生过程和依赖规模结构的自相食种群模型进行稳定性和异步性分析.首先将系统模型转化为抽象Cauchy问题,利用强连续算子半群理论证明了系统解的存在唯一性
在生物学中,非局部扩散方程有着相当广泛的应用。本文主要研究单物种非局部扩散的logistic模型。通过数值计算的方法来研究在资源分布不均匀的情况下,该模型的静态解中物种总
研究了一类三分量可逆自催化反应扩散系统和一类无界域上森林扩散模型的全局吸引子的存在性.对于第一类方程,在获得方程解的整体存在性的前提下,利用半群吸收性质和渐近紧性
随着2019年末“宇芽被家暴”“北大女生被PUA折磨自杀”等事件在网络的发酵,反家庭暴力的话题又再次引起大众激烈讨论。我国在打击和惩治家庭暴力违法和犯罪行为基础上,于201
本文考虑的是基于利息力和阈值分红策略下且时间间隔分布为广义的Erlang(n)分布的对偶风险模型.基于这种分红策略,在盈余不超过固定的阈值水平时不发生分红；当盈余超过阈值水
本文研究Abel范畴的可容许子范畴的相对奇点范畴与相对亏范畴。首先,本文回顾了范畴的局部化、乘法系与饱和乘法系的概念,特别地,我们指出了一些结论对于左乘法系也是成立的
本文的主要目的是完全确定其多重典范映射是射影平面P2上的阿贝尔覆盖的一般型极小曲面及其局部定义方程。实际上,只有二重典范映射能够实现为IP2上的有限覆盖映射,我们给出
解释性行政规定作为规范性文件中解释上位法概念的行政规则,其对公民权利义务的影响重大且深远。随着2018年《行政诉讼法》司法解释颁布施行,我国规范性文件的司法审查制度进
本文主要研究了整系数二阶递推数列通项之间的模p同余问题,其中p为一个素数.整系数二阶递推数列是指满足的数列,其中a,b,u1,u2为给定的整数.我们发现除去若干个素数p,其余的