摘要：支撑树个数是边失效下网络可靠性分析与设计的一个重要性能参考指标,本文利用字典乘积的方法来构建网络,通过这种方法我们很容易由若干特定规模较小网络来构建规模较大的网络,并得到它的一个紧的支撑树计数解析公式,这样的计数公式仅仅依赖于小网络的性能参数,如:结点的度数、小网络的阶数、小网络的支撑树数目.

摘要：讨论了网络上的计算机不执行给定的算法,而是执行最利于其主人工作的这种情况。作为这样的参与者即操纵算法的代理,算法设计者应事先确保代理的利益通过真实报告是最大的。文中引用了机制设计的概念,提出了研究这样算法的框架。在这个模型中,算法解与参与者的支付有关。支付应选择那些激励所有参与者真实报告的支付。文中将机制设计的标准工具VGC机制应用到解决最小支撑树问题。

摘要：网络的支撑树个数是衡量一个网络可靠性程度的重要参考指标.利用字典乘积方法设计的网络,在应用数学与网络优化设计与分析领域变的重要起来.本文利用组合方法给出了一类新网络的支撑树计数公式,它仅仅依赖小网络的结构拓扑参数:阶数,拉谱拉斯特征值等.

摘要：限制性支撑树最大容量扩张问题(the maximum capacity expansion of spanning tree problem with constraints,MCESTC)是NP-难问题。针对MCESTC问题,采用允许增加支撑树长度值的双边替换策略设计了一个启发式算法进行求解,并证明了算法的正确性。最后,用实例阐述运用该算法求解问题的过程,从而验证算法的有效性。

摘要：结合最小支撑树问题和装箱问题,该文研究了一类新的组合优化问题:给定权重图G=(V,E;w,c)和一种长度为L的特定材料,要在图G中寻找一颗支撑树,并用给定的材料来构建支撑树的边,支撑树的总构建费用包括材料费用和构建费用两部分,目标是使得总构建费用达到最小。该问题是NP—难的,不存在多项式时间算法,除非P=NP。该文对所提问题设计了一个2—近似算法,并分析了算法的复杂性,证明了算法的近似度。

摘要：众所周知,从通讯网络建设中提出著名的最优支撑树问题,即在一个赋权连通图中求一个包含所有顶点而权(费用)最小的连通子图(支撑树).进而,在交通、通讯、供销系统的干线设计中,考虑的连线(干线)不一定连接网络的所有顶点,但被连接的顶点必须构成一个控制集,即其余任一顶点都有一条边直接与此主干部分相连.这就提出了最优控制树问题.似乎此问题与最优支撑树问题十分类似,但我们将证明它是NP-困难的,并给出一个分枝定界算法及相关性质.

摘要：对于通常的网状网,如何设计最小的保护容量来保证快速恢复是一个富有挑战性的问题。为了解决如何分配更少的保护容量的问题,该文提出了一些理想的拓扑结构,研究了支撑树算法。在这两者的基础上针对一条链路出现故障的问题给出了利用理想拓扑的保护容量分配算法。仿真结果说明该算法能预留比支撑树算法少得多的保护容量。

摘要：数据和信息传输业务对网络的要求越来越高,在满足实时性、可靠性的同时,还要求充分利用网络资源,降低传输成本.文章首先建立了数据传输网络选择的最小成本模型,给出了有效支撑树代表集的概念,并给出了一个时间复杂性为O(mlogn)的算法产生代表集,其中m,n分别代表网络的边数和顶点数.然后对静态数据传输支撑树问题和动态数据传输支撑树问题,分别给出了一个时间复杂性为O(mlogn)和O(m2+mlogn)的多项式时间的好算法.

摘要：面基域的确定是从工程设计二维平面图进行三维模型重构工作中的一个重要步骤。首先介绍两个面基域划分算法思想:一种是基于平面拓扑结构的广度遍历支撑树,然后对支撑树进行遍历确定各个面基域;另一种是对一个节点的可见边进行旋转角度的有序排列,确定从一条边出发如何选择后继边以围成面基域,从而对图进行划分确定面基域。在比较这两种算法的优缺点的基础上,结合它们的优点得出一种新的综合算法思想。

摘要：三级网络在实际中比较常见。本文讨论在二级顶点已选定的情况下的三级网络设计问题,给出了使网络费用极小化的两种方法。