切比雪夫多项式与循环图中生成树的个数

生成树的个数是评估图(网络)可靠性的一个重要且被广泛研究的量.利用切比雪夫多项式的性质推出了循环图中计算生成树个数的在线性时间内即可实现的方法,并讨论了渐进特性.     

∑树结构与更新最小生成树的并行算法

更新最小生成树问题,即已知图的最小生成树,当图的某条边的赋值被改变,如何快速有效的求新出的最小生成树.本文引进了∑-树结构,并以此获得了一个快速有效的更新最小生成树的并行算法,并行时间为O(logn),处理器个数为O(n~(4/(?)),计算模型为CREW-PRAM.其中n 为图的顶点个数,而且,进行预处理所需的时问也只需O(log~2n),处理器个数为O(n~(?)),存贮数据所需的空间为O(n~(?)).     

五面体平图中的生成树的构造与计数

首先给出了生成子图的定义,生成子图与生成树、含圈的生成子图的关系S(G)=C(G)+T(G);其次对于任意连通图,以p=4,q=6的完全图K4为例给出了生成子图个数的计算公式,同样以p=4,q=6完全图K4为例给出了生成树的构造定理和计数定理,提出了图S(G)生成树的计数方法和构造方法;最后,介绍了五面体平图生成子图个数的计算和各生成子图的构造,并验证了所给公式的正确性,从而解决了任意平图G(p,q)生成树的构造问题。     

利用对偶图求平面图的生成树数目

图的生成树数目是图的一个重要参数，求连通图生成树数目的方法有很多．本文利用平面图的对偶图的Kirchhoff矩阵来求一些平面图的生成树数目，求这类平面图的生成树数目比直接利用收缩边和去边得到递推公式的方法要简单，该方法对于平面图可以进一步推广.     

完全图的生成树中的完全m叉树

在完全m叉树中,假设其叶数为t,分支点数为i,则(m-1)i=t-1.证明了完全图的生成树中的完全m叉树的个数和构造是有规律的,而且当完全图的顶点数n固定时,其生成树中的完全m叉树的个数就被固定,构造也有规律可循,且当n为偶数时,生成树中不含有完全偶数叉树.     

基于关系数据库的图的运算

针对在数据库应用程序中经常遇到的一种查询和实际问题的求解，提出了在关系数据库中对图进行表示和运算的方法。在该方法中，图中各项点信息用字段来存放，图中的边用记录来表示，给出了在该表示方法中对图进行遍历和求解最小生成树的算法。通过对一无向图的遍历及其最小生成树的求解举例，表明该方法表示图易于存储数据，对于解决数据库应用中遇到的复杂问题具有一定的参考价值。     

电子线路基于树枚举技术的符号分析

给出了电路符号分析的一种拓扑方法，该方法建立在Ｕｎｉｓｔｏｒ图树积的衍生基础上。给出了以独立组生成Ｕｎｉｓｔｏｒ图的全部有向树的直接方法。网格的代数余子式由计算机简化的Ｕｎｉｓｔｏｒ图的行列式获得。还介绍了该方法的ＰＣ机程序。     

组合图中生成树的计数

经典理论矩阵树定理用于图中生成树的计数并不实用,但利用Chebyshev多项式的性质作为工具,结合Kel,malls和Chelnokov的结果,可以给出较简单的方法对很多图中的生成树进行精确计数．通过给出一些组合图中生成树的计数进一步体现了该技术在其中所起的作用．     

用母函数求解图的生成树问题

如何精确求解出图的全部生成树,是图论研究的重要课题之一.引入组合数学的母函数原理,结合图论相关理论,提出了一种求图的全部生成树的新方法,该方法易于在计算机上实现,能精确求解连通图的生成树数目及其全部生成树,快速找出带权图的最小生成树,并给出了严密证明.     

循环图C_(2n)(1,n-1)的临界群

连通图的临界群是阶数为生成树数目的有限阿贝尔群,连通图生成树的数目与Laplacian矩阵有关,可以用矩阵树定理求得。文中给出了循环图C_(2n)(1,n-1)的临界群的代数结构,它是n个或n+1个循环群的直和。