【摘 要】
：
本论文主要研究有向图中限制出度的最小K-树形图问题,其叙述如下：给定一个n+1阶含有m条弧的赋权有向连通图D=(V,A；ω),这里函数ω：A→R+,在D中寻找一个含n+K条弧的子集H,满足诱
论文部分内容阅读
本论文主要研究有向图中限制出度的最小K-树形图问题,其叙述如下：给定一个n+1阶含有m条弧的赋权有向连通图D=(V,A；ω),这里函数ω：A→R+,在D中寻找一个含n+K条弧的子集H,满足诱导子图D[H]含有一棵以固定顶点为根的支撑树形图,限制固定顶点的出度为一个常数且不含有向圈,目标是使得H中所有弧的权重之和达到最小。本论文首先把有向图中限制出度的最小K-树形图问题分解成限制出度最小支撑树形图问题和最小K-树形图问题来研究。对限制出度最小支撑树形图问题,设计出一种O(n3m)的多项式时间算法。对最小K-树形图问题,设计出一种O(m2lgm)的多项式时间算法。然后,结合上述两个算法思想,设计出一个多项式时间算法来解决限制出度的最小K-树形图问题,其复杂性为O(n3m)。
其他文献
交叉数是图论的一个分支,有很多应用,譬如电路板设计、生物工程DNA的图示等等。许多重要的结果已经被发现,主要集中在平面上交叉数的问题。然而关于非平面曲面上图的交叉数问
将永磁材料分散在高分子基体中制备得到的磁性高分子复合材料具有非常广泛的应用。文献调研表明,基于热塑性高分子基体且具有各向异性磁取向结构的永磁/高分子复合材料尚未见
本文主要是对辫群Bn的(左)有序性进行综述,列出了三种较为经典的证明Bn是(左)有序群的方法。辫群Bn的(左)有序性最初是由Dehornoy得到的,本文首先详细给出了Dehornoy定义Bn上
双循环半群是一类特殊的逆半群.本文从双循环半群上的同余关系出发,对双循环半群的结构与性质给出了具体描述.主要结果如下：1.从双循环半群上的一类同余出发,讨论了幂等元所在
通过数百年来对Gamma函数的系统研究,揭示了它具有一系列独特的性质,关于Gamma函数的问题,是数学领域内的一个十分有意义的课题.本研究在已有结论的基础上,深入地研究了Gamma
烟囱排污的采样、检测属于高空作业,一般在烟囱离地面40～80米的高处搭建采样平台,利用采样仪器对烟囱排放的污染物进行采样、并检测温度等参数。采样环境恶劣且部分排出的污染气体对人体有致命伤害,使用烟囱排污采样机器人代替人工采样非常有必要。随着科技的不断发展,机器人在工业领域内的使用日益广泛。精度是机器人的一项非常重要的性能指标,机器人的工作水平受其精度高低的影响。如何提高工业机器人的位姿精度问题受到
线性递推序列中特殊数的相关问题一直是数论研究的重要内容之一.国内外许多学者对该问题进行了深入的研究,并且获得了丰硕的研究成果.1996年,P.Ribenboim和W.L.McDaniel研究
目的:运用“中医传承辅助平台”软件,对王伟明教授治疗慢性胆系疾病处方进行整合、数据分析,发掘王伟明教授在治疗慢性胆系疾病中的用药规律,以期将王教授临床经验得以继承和发扬,更好地应用于临床。方法:搜集王伟明教授治疗慢性胆系疾病(慢性胆囊炎、胆囊息肉、胆石症)相关的中医处方,建立数据库,以中医传承辅助平台系统(V2.5)为依托,进行数据整合、分析、挖掘,获取王教授临床治疗慢性胆系疾病用药规律。结果:搜
态理论是为了研究模糊逻辑中一个命题真值的平均度而引入的.1995年,学者Mundici提出了MV-代数上态的概念.本文将研究超BCI/BCK-代数及其商结构上的态,所做的具体工作有以下几
Chebyshev多项式Tn(x)和Un(x)(n∈N*)满足下列二阶线性递推序列：To(x)=1,T1(x)=x,Tn+1(x)=2xTn(x)-Tn1(x), Uo(x)=1,U1(x)=2x,Un+1(x)=2xUn(x)-Un-1(x).这两个多项式在解析数