生成有向图全部有向树的新算法

本文算法生成一个有向边集数据做结点的生成林,用来表示有向图G的所有以指定顶点γ为根的有向树集。本文算法打破了H.N.Gabow和E.W.Myers算法(SIAM J.Computer,1978,7)的严格深度优先原则,并提出了有向图桥边集的概念和判据,从而使算法有效性达到新的高度。复杂性:时间D(bK),空间O(b),其中b和K分别为G的边数和算法生成林树梢结点数。     

计算全部树的撕裂算法

提出一种求连通图的全部树的方法，该方法采用撕裂大图分为两个连通片，然后添加撕裂边，便生成全部生成树，该方法可用于计算机并行运算，适用于大网络的计算机辅助分析。     

一种分布式后缀树构造与匹配算法

提出一种基于消息传递模式的分布式后缀树构造算法(DPSTG)及相应的并行匹配算法.DPSTG算法按不同的字符将原始字符串的后缀树分解成若干个子后缀树后由多个处理器并行构造.处理器间通过消息传递方式连接各个子后缀树,匹配时首先将要查找的字符串分割成若干不同首字符的子字符串,然后在构造相应首字符子后缀树的处理器上实现多个子字符串的并行匹配.理论分析表明DPSTG算法的时间复杂度要优于现有的大多数后缀树并行生成算法.模拟实验结果表明DPSTG算法的并行加速比随着待处理字符串的长度增加而提高.     

最小生成树的又一种生成法

提出一种关于最小生成树的生成法, 此方法是在一个给定的网络中,首先找到一条权最大的边,判断此边的 2个结点在不经过此边的情况下是否有另路相通,若相通则删除此边.否则, 保留此边,再寻找所剩余的权最大的边, 作类似的处理,直到在原网络中剩下的边为顶点数减 1 为止, 由此即得最小生成树.与传统的 Prim 算法及 Kruskal 算法相比较, 此法在点多而边数相对较少的网络中,能迅速地找到它的最小生成树.     

基于最小生成树的R~*-树结点分裂算法

针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出了一种新的R*-树结点分裂算法.该算法将R*-树索引结点表示为轴向包围盒,依据轴向包围盒外接球间的重叠度计算结点相似度,并将其作为权值构建结点无向连通图,用来求解结点无向连通图的最小生成树.沿最大权值边将最小生成树分裂为2棵子树,并基于结点外接球体积对R*-树结构进行优化,从而实现了R*-树结点分裂.实例表明,R*-树结点分裂算法可处理各种复杂数据的结点分裂问题,能够有效地提高R*-树的构建效率及空间数据的查询效率.     

寻找最小生成树的补图算法

提出了一种关于最小生成树的生成法，该算法与传统的prim算法及kruskal算法比较，有更低的计算复杂性．     

最小生成树问题

本文给出了最小生成树的一种计算方法，并介绍微机软件ＹＡＪ（运筹学和计算机）在此问题上的应用。     

一种对称无向图的同构判定算法

文章在电路模拟法的基础上提出了一种对称无向图的同构判定算法.电路模拟法对随机图的同构判定问题非常有效,但是对于处理对称度较高的图,判定效率明显降低甚至失效.该文提出的算法针对对称无向图的特性,在电路模拟法的基础上结合Dijkstra算法,综合得到顶点属性和最短距离序列来搜索顶点之间的映射关系,能够有效判定这类图的同构问...     

寻找最小生成树的补图算法

提出了一种关于最小生成树的生成法,该算法与传统的prim算法及kruskal算法比较,有更低的计算复杂性.     

无向树图的k点连通最小扩充

解决了以最少边集扩充一个任意无向树图为k点连通图这一优化问题,提出了一个计算复杂度为D(|V|~4)的算法。为进一步研究可靠网络的计算机辅助设计打下基础。     

任意无向图的最小R边连通扩充

研究了以最少边集扩充一个任意无向图为R边连通图这一优化问题。给出了一个复杂度为O(|V|~5)的算法。利用该算法可最优地将所研究图形中任意两点达到所要求的边连通度。它发展了K边连通最优扩充的研究,从而使图的边连通扩充的研究在应用于网络结线的可靠性设计方面更具有实际意义。     

无向图的特征多项式及其与图的某些整体性质的关系

本文引入无向图的特征多项式的概念,并推导出由特征多项式的系数表示的无向线图中圈的个数、边的条数及简单图中三角形的个数的计算公式.     

关于赋权欧拉图的均匀初级圈覆盖

本文给出赋权欧拉图无公共边均匀初级圈覆盖,M—均匀初级圈覆盖,最小均匀覆盖的概念,并给出求它们的相应算法.此文所给出的算法同样适用于有向欧拉图.     

广义轮型完全多部图的生成树数

证明了如下结论:设KWk,n是由轮图集W={Wn1,Wn2,…,Wnk}生成的n阶广义轮型完全k-部图,其中n={n1,n2,…,nk},n=|n|=n1+n2+…+nk,1≤k≤n.那么KWk,n的生成树数目为t(KWk,n)=n2k-2∏ki=1αni-1i+βni-1i-2n-ni+1,其中αi=(di+d2i-4)/2,βi=(di-d2i-4)/2,di=n-ni+3.     

通讯网络中的生成树

本文给出了一类比较重要的通讯网络中生成树的计数递推公式和其它几种通讯网络生成树的计算方法。