欧几里德最短2-连通Steiner网络的性质

称连接平面上给定点集的最短2-连通Steiner网络为欧几里德最短2-连通Steiner网络。给出了欧几里德最短2-连通Steiner网络的两个性质。     

非基本最短欧几里德2-连通Steiner网络的几个性质

欧几里德2-连通Steiner网络问题是组合优化中的著名问题,在水、电供应网络等的设计中有非常广泛的应用.以块图为工具,证明了非基本最短欧几里德2-连通Steiner网络的一些结构性质.     

K度Steiner问题

给定平面上n个固定点 (称为正则点 )的集合N和m =n - 2k- 2 个可动点 (称为Steiner点 )的集合M ,其中k( 3≤k≤n)是确定的正整数 要求互联点集V =N∪M的网络的拓扑在正则点的度为 1 ,Steiner点的度不超过k ,这种网络称为k度网络 确定m个Steiner点的位置 ,使互联这n m个点的k度网络总长度最短 显然这个最短的k度网络一定是树 ,我们称这个树为k度Steiner最小树 (kDSMT) ,并称这个问题为k度Steiner问题 本文得到了kDSMT的一些结构特征 ,并提出了一些有待进一步研究的问题     

3t-2阶Steiner三连系构造的一种方法

阐明了v阶Steiner三连系构造的基本思路,给出边矩阵的定义.提出3t-2阶Steiner三连系构造的一种方法,介绍25阶Steiner三连系构造的全过程,最后讨论了3t-2阶Steiner三连系不同构的个数问题.     

31阶Steiner三连系的构造与计数

阐明了v阶Steiner三连系构造的基本思路,给出了完全图Kv的边矩阵的定义,提出了2t+1阶Steiner三连系构造的一种方法.介绍了依据已存15阶Steiner三连系ST(15)构造31阶Steiner三连系的全过程,并讨论了2t+1阶Steiner三连系的计数问题.     

基于遗传算法的通讯网络最佳Steiner树构造

提出了一种解决Steiner最小树问题的自适应遗传算法,将Steiner最小树问题转化成一个组合优化问题,并对部分初始种群的构造给出了一种试探选择方法.通过对通讯网络Steiner最小树问题的实例仿真分析,表明算法能有效地跳出局部极小值并快速地收敛于全局最优值.将其推广到考虑建站费用的极小树问题上,取得了很好的近似解.     

49阶Steiner三连系的构造与计数

阐明了v=t^2阶Steiner三连系构造的基本思路。给出了任意完全图kv的边矩阵的定义，从而为图论研究提供了一个工具。提出了t^2阶Steiner三连系构造的一种方法。介绍了49阶Steiner三连系构造的全过程。讨论了t^2阶Steiner三连系的计数问题。     

k度Steiner最小权网络的线性时间算法

已知平面上n个固定点集合N和m个可动点集合M,求互连点集N∪M的最短连通网络,要求这个连通网络满足：（1）固定点的度为1,可动点的度为k(k≥3）;（2）n=2 （k-2）m。网络中每条边的权与可动点的位置有关,问题是如何确定这m个可动点的位置,使这个连通网络的权最小,这个问题称为k度Steiner最小权网络问题。本给出了k为偶数,边权值为L1距离时计算最小权网络的O(n ln k)时间算法。     

图的Steiner最小树的竞争决策算法

图的Steiner最小树问题是一个著名的NP难题,在通讯网络、VLSI等工程实践中有着重要的应用.在分析图的Steiner最小树问题数学性质的基础上,提出了图的Steiner最小树的竞争决策算法.为了验证算法的有效性,求解了OR-Library中的基准问题,测试结果表明了算法具有较好的求解效果.     

近似2-连通k-支配容错虚拟主干网

由于无线网络存在节点失效、链路断裂等特性,虚拟主干网需要具备一定的容错性。利用2-连通k-支配集作为容错虚拟主干网的模型。通过分析单位圆盘图中极大独立集的性质和连通图的块-割点树结构,首次设计出在无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法。从理论上分析了该算法的时间复杂度,并证明了该算法的近似比为常数。