瓶颈型Hamming距离下约束最小支撑树的反问题

本文讨论了瓶颈型Hamming距离下约束最小支撑树的反问题,通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用瓶颈型Hamming距离来衡量修改的费用,且修改费用最小. 把瓶颈型Hamming距离下约束最小支撑树的反问题转化为最小瓶颈权点覆盖问题,并给出了多项式算法.     

图的支撑树伸展与层叠最优化

在图的支撑树最优化中,有两个重要的优化指标:伸展度和层叠度.由此提出两个组合最优化问题:最小伸展支撑树问题,求一个图的支撑树,使得当所有边嵌入到此支撑树时,这些边的最大伸展距离为最小;最小层叠支撑树问题,求一个图的支撑树,使得当所有边嵌入到此支撑树时,每条树边上的最大重叠边数为最小.这两个问题确定出两个图论参数:树展和树层.本文主要论述树展和树层的基本结构性质,包括圈与余圈的对偶性、极值性、上下界、最优性刻画和最优值计算等.     

带区间数据的最小风险斯坦纳树问题

考虑了在带区间数据的不确定网络中, 最小风险和模型以及最小最大风险模型下的斯坦纳树问题. 它们推广了相应模型下的最短路问题和最小支撑树问题, 在网络设计中具有更加广泛的应用.我们分别给出了这两个模型下斯坦纳树问题的近似算法, 并对算法性能做了理论分析和证明. 结果显示我们的算法具有优良的常数逼近的性质, 能在多项式时间内算出令人满意的解.     

最小树问题的全部解

<正> 以某些实际问题(如管道设计、通讯网建设等)为背景,图论中的最小树问题引起人们的广泛兴趣.自从 Kruskal 提出三种基本的构造法以后,各种算法实现途径相继出现,使这一问题得到完满的解决.然而,实际问题往往不能满足于求出一个最小树,而希望兼顾其它目标,在若干最小树中进行再选择.这就要求我们讨论最小树问题的全部解.在已有文献中,求全部支撑树已有较成熟的算法,尤其是文献[4]提供的算法可以将全部支撑树按权的大小依次列出.从理论上说,可以认为这些结果已经包含了求全部最小树问题.作为另一种途径,本文将着重讨论最小树问题全部解的性质,并由此建立求全部解的广探法(求全部支撑树的 Mayeda-Seshu 算法的推广).     

多目标度约束最小生成树的蚁群优化算法求解

多目标最小生成树问题与度约束最小生成树问题分别是网络优化中两个NP难题,在实际中一直有着重要的应用.本文针对同时考虑多目标和度约束情况下的最小生成树求解问题,采用蚁群优化算法思想,设计了一种求解方案,并在计算机上用Delphi予以实现.经大量数值算例求解测试,验证了算法的有效性和可行性.     

在有向网络中寻找最小支撑入树的计算方法

本文研究了有向网络中支撑入树的性质 ,提出了在有向网络图中寻找以某一指定点为根的最小支撑入树的一种较简便的算法 ,并给出了应用该算法的一个实际算例     

最小度生成树的一种近似算法

最小度生成树问题是一个NP难问题.本文给出了求最小度生成树的一种近似算法,这种算法得到的生成树的度数比最优解至多大1.     

Minimum Global Height支撑树及相关问题

本文研究了两个组合优化问题:minimum g1obal height支撑树和minimum aveageheight支撑树问题.利用3SAT问题的时间复杂性,本文证明了这两个问题都是NP-hard的,并分别给出了一个算法,即（mgh）-算法和（mah）-算法.在非负网络中,这两个算法的时间复杂性都为O（n3）.利用第一个问题的复杂性,本文证明了minimum height支撑树问题也是NP-hard的,从而纠正了有关文献中的一个错误结论.     

计算最小支撑出树的一种简便算法

本文通过对网络中有向支撑出树性质的研究,提出了在有向网络图中寻找以某一定点为根的最小有向支撑出树一种较简便的计算方法,并给出了应用该算法进行实际操作的一个算例．     

最小费用k度限制树对策

本在Glover—Klingman算法及最小费用支撑树对策的基础上，讨论了最小费用k度限制树对策问题．利用威胁、旁支付理论制订了两种规则，并利用优超、策略等价理论分别给出了在这两种规则下最小费用k度限制树对策核心中的解，从而证明了在这两种规则下其核心非空．     

最小最大树划分的近似算法与最小和树划分的精确算法

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题)．文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法．     

新增结点下最小生成树研究

本文研究了对于给定结点及边的图,在可新增结点的情况下求最小生成树的问题.利用文献[3]的部分结果和LINGO软件编程计算等方法,获得了费尔马点的坐标表示及n结点图的最小生成树只需至多增加n-2个结点的结果.同时寻找到四结点图的最小生成树的一般解法及理论证明,推广了费尔马点对于平面的结论到三维空间中,有利于某些可建立树图模型的优化问题的求解.     

基于α-CIS值的非合作-合作双型博弈的求解

本文研究了非合作-合作双型博弈模型求解的问题.首先利用于α-CIS值,求解非合作-合作双型博弈中的合作博弈阶段,再对非合作博弈阶段求其纯策略纳什均衡,获得了基于α-CIS值的双型博弈的一种新的求解方法.推广了原始双型博弈模型的求解方法并证明其可行性.     

SLD-博弈树及其删除策略

结合SLD-反驳和对策论的思想,提出标记逻辑程序的SLD-博弈树语义.在SLD-博弈树中,一个目标的所有支持和反对证据作为游戏双方参加博弈.对有限树,提出一种删除策略(博弈规则),根据删除过程的结果判断目标是否成立.对覆盖不循环程序,删除策略是可靠的和完备的.     

一种基于Split-findmin和Set-maxima的最小支撑树灵敏度分析方法

本文首先根据最小支撑树的截性质和圈性质给出了灵敏度分析的基本公式,然后基于现代图论算法中经典的Split—findmian数据结构介绍了树上边的灵敏度分析算法,最后将非树边的灵敏度分析转化为已有成熟的算法的Set—maxima问题进行处理.     

一类最小支撑树的逆问题及其求解方法

本文针对传统的基于边的最小支撑树逆问题，提出了一类基于点边更新策略的最小支撑树逆问题．更新一个点是指减少与此点相关联的某些边的权值．根据是否含有更新点的费用，考虑了两类模型，它们均可转化为森林上的最小(费用)点覆盖的求解问题，算法的复杂性都是O(mn)，其中m=|E|n=|V|。     

次限制拟阵基的排序算法

§1 引言本文对一般的拟阵,给出在一个子集上具有次限制所有拟阵基的排序算法。著名的“greedy”算法是求连通图最小权的支撑树的好算法。在连通图上特别指定了一个顶点,求在该顶点次限制的最小权的支撑树,Glover—Klingman也给出了好算法。Burns—Haff给出了图的支撑树权的大小进行排序的生成算法,并且指出能够把它推广为拟阵基的排序算法。本文对一般的拟阵,给出在一个集上具次限制的所有拟阵基的按权的大小进行排序的生成算法。     

次最小树及其相关问题-算法设计和复杂性分析

支撑树问题已经有很长的研究历史了,见[1].在许多工程问题中,需要产生一个网络G的所有支撑树,见[2,3,4].当G为赋权图时,每棵支撑树T有长度L（T）.在产生G的所有支撑树时,许多工程问题希望按照L（T）的非降顺序产生,见[5,6].在按照L（T）的非降顺序产生的支撑树中,有许多支撑树长度是相同的,而支撑树的数目又非常大（可以高达nn-2个）,因此算法的计算量非常大.本文希望能够按照L（T）的严格上升顺序产生所有的支撑树,从而避免大量的重复计算.     

一个具有变化联盟结构的动态合作博弈模型

本文运用合作博弈的观点分析和解决在动态决策进程中出现的合作方式发生变化的问题.针对于在博弈树给定的有限个节点上随机改变联盟剖分的动态博弈,通过引入新的特征函数和最优准则,建立了动态最优解PGN向量,同时给出了求最优路径和最优解的算法.     

有向网络中具有一个枢纽点的最小支撑树的计算方法

对有向网络中具有一个枢纽点的支撑树的问题和性质进行了研究,给出了在有向网络图中寻找以某一定点为枢纽点的最小支撑树的计算方法,并对算法的复杂性进行了讨论,最后将该算法应用于实际算例的计算．