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

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

Steiner最小树问题及其应用

Steiner最小树问题是一个历史悠久的经典的组合优化问题,由于应用广泛,多年来一直受到研究者的广泛关注。介绍了各种Steiner树问题及其求解算法和实际应用。     

度约束欧氏Steiner最小树问题及其求解

在欧氏Steiner最小树的基础上,对每个正则点加上了度约束限制,提出了度约束欧氏Steiner最小树问题,分析了该问题的特性,给出了该问题的模拟退火和蚂蚁算法求解过程,并使用Delphi语言编程,在Windows XP平台上运行通过．通过大量算例的计算结果验证了该问题的实用性及算法的有效性．     

Steiner问题的研究及进展

详细介绍了Ｓｔｅｉｎｅｒ问题及其几个主要研究方向的进展情况．探讨了有关Ｓｔｅｉｎｅｒ问题各时期的研究特点．并对其文献情况给出了统计分析．     

欧氏Steiner最小树的Delaunay三角网混合智能求解方法

欧氏Steiner最小树问题是组合优化中一个经典的NP难题,在许多实际问题中有着广泛的应用.由于使用普通智能算法求解较大规模问题时,极易陷入拓扑结构的局部最优,因此,基于Delaunay三角网技术并结合智能算法的有关思想,设计了一种改进的混合型智能求解方法,可大幅度提高算法在寻找更好拓扑结构上的有效性.算法在Matlab环境下编程实现,经大量STEINLIB中的标准数据实例测试和验证,获得了满意的效果,为求解较大规模的欧氏Steiner最小树问题提供了新的有效方法.     

求赋权图上最小树的两个算法

该文证明了赋权图上的树为最小树的一个充要条件，并由此得到求赋权图上最小树的两个算法。     

最小树的一种新的生成方法

最小树及其算法是图论研究的重要内容之一,迭代思想是网络优化的基本思想,从任意生成树出发,若它不是最小树,利用迭代规则得到一棵更小的生成树；本文引入了关于连枝的迭代法和关于树枝的迭代法并给出了从一棵生成树中找最小树的新的方法,这种方法在网络设计有重要的应用.     

关于φ=π/3 [n/2]<3时梯形波图G_n上的Steiner最小树

本文作为宋国栋等所作《梯形波图的Steiner最小树》(见《东北重型机械学院学报》一九八五年第二期)一文的一个注记,给出了φ=x/3,[n/2]<3时梯形波图G_n上的Steiner最小树。     

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

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

关于图的路色数

本文证明了P_∞-K-临界图的一些简单性质,并给出了某些图类的路色数。主要证明了:(1)若x(G,P_∞)=K,则G包含一个P_∞-l-临界子图,这里对所有的l≤K;(2)设G是P_∞-K-临界图,H是G的子图,且H∈P_∞。,则x(G—H,P_∞)=K-1;(3)设T为m阶树,C_n为偶圈,则x(T×C_n,P_∞)=2;(4)若C_n为奇圈,则对任意树T,有x(T×C_n,P_∞)≤3;(5)若m≠n,则x(K_m×K_n,P_∞)=max{[(m 1)/2],[(n 1)/2]}。     

关于一类Ore图的泛圈性

从所周知，ＪＡＢｏｎｄｙ的Ｍｅｔａｌ猜测对Ｏｒｅ图是成立的。本文从一个新的角度，对Ｇ中次数较小的节点所导出的子图的结构进行了分析，得出了一类新的泛圈图。     

关于图的叉数的一个注记

本文改进了完全二分图的叉数的已知下界,并证明了,在已知的完全图的叉数上界μ(K_p)≤1/4[p/2][(p-1)/2][(p-2)/2][(p-3)/2]中,如果对奇数p等号成立,邸么对下一个偶数p+1也有等号成立。     

求解一类非对称线性方程组的极小化残量法

本文考虑系数阵的特征值正负成对出现的非对称线性方程组,对这类线性方程组,本文提出了一种基于特殊子空间的极小化残量法,它在理论上具有至多N/2步的收敛性(N为方程组的阶数),文中的数值试验验证了所得结论。     

平面图边可重构的几个结果

本文得出几个平面图边可重构的结论:1.若 G 是平面图,δ(G)=4,且 G 没有次为5的点,则 G 是边可重构的。2.若 G 是平面图,δ(G)≥3,且 S_3为 G 中次为3的集合,又设 G—S_3为3连通的,G 无次为4的点。则 G 是边可重构的。     

两类平面图的指数集

完全确定了极大可平面图与极大外可平面图的指数集。     

关于常标量曲率的球面闭极小超曲面上L—算子的第一特征值的注记

本文讨论关于具有常标量曲率的球面闭极小浸入超曲面上L——算子的第一特征值λ_1及其所刻划的曲面的特征。并给出 定理 设M是S~n+1中的闭定向极小超曲面,且S=常数>n,则L——算子的第一特征值 λ_1≤-n-[2(S-n)/(n+2)]其中,S为第二基本形式模长的平方。     

THE MINIMAL DFA FOR EVENTUALLY PERIODIC UNIMODAL MAPS ON THE INTERVAL

Combining the theory of symbolic dynamics-with the. formal language theory, we determine the minimal deterministic finite automata (DFA ) accepting the formal languages generated by eventually periodic kneading sequences of unimodal maps on an interval.     

一类树的优美性的讨论

在优美图的问题中，Ｒｏｓａ猜想树是优美的；本文讨论了一类树，用Ｔｎｍ表示。