最小树问题的全部解

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

最小树图的Hamilton性及全部最小树的生成

对给定的连通图G,树图T(G)的Hamilton性,首先由Cummins所证明。稍后,Kamae给出另一构造证明,并用于树的生成。本文将研究一个赋权图G所有最小树的一些性质。主要结果如下:(1)对任意赋权图G,证明了最小树图T_(min)(G)的Hamilton性;(2)根据构造性证明,给出生成全部最小树的算法。     

最小树的一般算法

本文根据设计并行算法的基本原则,给出了最小树的两个对偶定理.在此基础上,建立了两种对偶的同步并行算法的雏型.这两种算法恰恰在对偶的意义下,概括了以往的最小树算法.     

具有次限制的最小树问题

F.Glover和D.Klingman在[2]中给出了予先确定的一个点x具有固定次数为k的最小树算法。 本文给出了任意m个互不关联点具有次数限制的最小树问题的算法.算法的基础是线性规划的对偶理论。     

三维欧氏Steiner最小树的Delaunay四面体网格混合智能算法

Steiner最小树问题是组合优化中经典的NP难题,在许多实际问题中有着广泛的应用,而三维欧氏Steiner最小树问题是对二维欧氏Steiner最小树问题的推广。由于三维欧氏Steiner树问题的求解非常困难,至今为止的相关成果较为少见。本文针对该问题,利用Delaunay四面体网格剖分技术,提出了一种混合型智能求解方法,不仅可以尽量避免拓扑结构陷入局部最优,且对较大规模的问题求解亦有良好的效果。算法在Matlab环境下编程实现,经实例测试,获得了满意的效果。     

相对于Wiener-Hosoya指标的最小树

Wiener-Hosoya指标是由Randic在文[1]中引入的一个指标,旨在揭示分子结构与其化学性质的更进一步的关系.任意给定点数及直径,本文确定了相对于该指标的最小树.进一步地,具有任意给定点数的最小的16个树也得到确定.     

正多边形顶点集上的斯坦纳最小树

众所周知,覆盖一给定点集A的最小树T是所谓的斯坦纳最小树,简记为SMT.T中的顶点集记为V(T),V(?)A,而S=V-T中的点即为斯坦纳点。SMT的构作及其基本性质可见文献[1]及[2]。1977年Garey和其他人证明了离散的斯坦纳问题是属NP-complete类,从而很少有希望找到SMT的有效算法了。故斯坦纳问题研究中的另一方     

无向图上最小树的唯一性定理

本文研究各边具非负长度的有限无向图中最小树的唯一性,得到下述定理:H为图G上唯一最小树的充要条件是对任一不属于H之边e,图H∪{e}所含之唯一圈中,e是唯一最长边. 给定无向图G=(X,U),X为顶点集合,U为边集合,对边e∈U,给定长度l(e)≥     

带有边集限制的最均匀支撑树问题

本在无向网络中，建立了带有边集限制的最均匀支撑树问题的网络模型．中首先解决最均匀支撑树问题，并给出求无向网络中最均匀支撑树的多项式时间算法；然后，给出了求无向网络中带有边集限制的最小树多项式时间算法；最后，在已解决的两个问题的基础上解决了带有边集限制的最均匀支撑树问题．     

关于Steiner最小树问题

在本刊第二卷第二期上,我们曾发表了黄光明的《最短网络》一文,对Steiner最小树问题在当时的发展情况作了一些介绍。最近由于他与堵丁柱共同解决了Gilbert和Pallak在1968年所提出的一个猜想,不少读者对于这一问题产生了兴趣。为此,我们组写了这篇文章,目的在于使读者对这一问题的历史和连带产生的问题以及目前的发展状况有一较确切的和较全面的了解。     

具有限制的最小 k一个边不交支撑树问题

本文推广了刘振宏等具有次限制最小树算法,给出了求具有限制的最小 k 个边不交支撑树算法.该算法已在 IBM-PC 机上用 Fortran 语言实现,其时间复杂性为max{O(k~2|E|~2|V|~2),O(k~3|V|~4|E|)}.     

网络最小树的一种矩阵算法

求网络最小树问题，人们熟知常用的方法有“避圈法”和“破圈法”，这些方法有其直观易解的优点，然而它们毕竟是要在图上作业（在图上完成）。由于网络与距离矩阵的对应关系，本文将利用矩阵性质给出该问题的一个矩阵解法。     

系列平行图上带时间约束的Steiner最小树问题

对一类特殊系列平行图上带有时间约束的Steiner最小树问题,证明了其复杂性为NPC,并给出了一个完全多项式时间近似方案.     

求最小树的破圈法

§1.引言 最小树问题是图论中一个有较广泛实际应用的问题,它的提法如下: 设G-(X,U)是一个有限无向图,这里X表示图G的顶点的集合,U表示G的边的集合.我们设G是连通的,即对于G的任意两个不同的点x_i与x_j,都存在一条由U的边组成的链把x_i与x_j连接起来(关于图论的一些基本概念的较详细的叙述,可以参看[1]).     

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

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

抢救小树

昨天中午,小区里一辆面包车在倒车时,不小心碰倒了我家楼下的一棵小木棉树。我跑下楼去看小树,发现邻居张奶奶也在那儿。她摇摇头说：“啧啧啧,可惜了,     

最小双权树

本文根据一个实例建立了在双权无向网络中求最小双权树的多目标网络模型，提出了最小双权树和临界最小树子图的概念，并给出了这个模型的一个有效算法．     

最短时限缺省指派问题的一个解法

将周良泽在1998年提出的最短时限缺省指派问题转化成赋权二分图的最小权K-匹配问题,研究了其解的最优性充分及必要条件,并给出了适合在图上求解的生长树法及适合在表上直接求解的标号法,最后给出一个实例,该算法是一种较简便的算法。     

λ5-geometry中的Steiner树问题(Ⅱ)

首先研究了λ5－geometry中4个点的Steiner最小树的某些特点，然后证明了对于λ5－geometry中的给定点集P，必有P的一个Steiner最小树，其Steiner点在P的前[2n/3]代格点中。     

最短时限缺省指派问题的一种解法

将周良泽在 1998年提出的最短时限缺省指派问题转化成赋权二分图的最小权 K-匹配问题。研究了其解的最优性充分及必要条件 ,并给出了适合在图上求解的生长树法及适合在表上直接求解的标号法 ,最后给出一个实例。该解法是一种较简便的算法。