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

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

有关对称无权图生成树数目的拆分定理

设G是一个对称平面图.Ciucu等证明了一个有关G的生成树数目的拆分定理,也就是G的生成树数目可用两个小图的生成树数目乘积来表示.在此基础上,提出了一种图变换,给出了图在这种变换下生成树数目的变化关系式,再结合矩阵-树定理给出了该拆分定理的一个简短证明.同时,受Zhang等证明的赋权图生成树权和的拆分定理启发,还给出了一个关于对称无权图生成树数目的等价拆分公式.     

图中生成树数目的一个上界

图论中一个重要的极值问题是刻画具有最大生成树数目的某些图类的特征。利用图中割点数或割边数目,给出了连通图中生成树数目的上界。     

基于圈或路的多重星相关图的生成树数目

利用图的标定技巧、矩阵和行列式运算、补生成树矩阵定理等理论,研究了当图G是基于圈或路的多重星图时,补图类Kn-G的生成树数目的计数问题,得到了一些特殊情况下基于圈或路的多重星相关图的生成树数目的计数公式．     

基于路的多重完全图相关图的生成树数目

利用图G的标号技巧、矩阵和行列式运算、补生成树矩阵定理等,研究了当G是基于路的多重完全图时的补图类Kn-G的生成树数目的计数问题,并求出了补图类Kn-G的一些特殊情况的生成树数目的计数公式.     

基于圈的多重完全图相关图的生成树数目

利用图G的标定技巧、矩阵和行列式运算、补生成树矩阵定理等理论,研究了当G是基于圈的多重完全图时,其补图类Kn－G的生成树数目的计数问题.给出基于圈的多重完全图相关图Kn－G的一些特殊情况时生成树数目具体计数公式.     

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

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

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

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

一些具有较多边数图的临界群

图的临界群是图生成树数目的一个加细,图的临界群的阶数恰为该图的生成树的数目.确定了一些具有较多边数图如Kn-K1,m,Kn-Km,Kn-mK2,Kn,n-nK2的临界群的结构,证明了这些图的临界群不是一个循环群,而是多个循环群的直和.     

一类平面图的生成树数目

利用平面图的对偶图的Kirchhoff矩阵来求一些平面图的生成树数目,求这类平面图的生成树数目比直接利用Cayley公式要简单,且该方法对于同一类的平面图可以进一步推广.     

用面向对象方法求解图中树的数目的无误差计算

利用面向对象编程方法中的封装，重载等技术，分别生成有理数类和矩阵类来进行图中树的数目无误差计算。并通过链表解决实际计算中所存在的整数溢出问题，使得此方法可以对较大规模的图进行支撑树的计算。     

生成树数目公式的概率证法

在一个给定的概率空间（Ω,Ｆ,Ｐ）中,通过建立一个古典概率,人出了图论中关于完全图Ｋn的生成树的数目公式,即Ｃayley定理及Ｃlarke定理,进而,证明了在“团”下更一般情形的图的生成树的数目公式,使Ｃaley定理及Ｃlarke定理成为其在完全图下的特殊情况。     

合成图的Laplacian特征值

给出了任意两个图的合成图的Ｌａｐｌａｃｉａｎ特征值和特征向量,同时得出了合成图的生成树的数目。     

用秩1矩阵矫正法计算两类图的生成树数

设P是完全二部图K_m,n的一个匹配，本文用秩1矩阵矫正法给出了完全二部图K_m,n中包含P中的所有边和不包含P中边的生成树数目公式的一个简单证明.     

树扩图生成树数的界

连通图的生成树是指该图的极小连通生成子图．在Cayley公式的基础上，给出树扩图生成树数的上下界．     

边冠图 Tm◇Sn的临界群

确定了任意树与星的边冠图 Tm◇Sn 的临界群的代数结构,证明了边冠图 Tm◇Sn 的临界群的Smith标准型为 (n－2)m 个循环群的直和,同时给出了图 Tm◇Sn的生成树数目.     

完全图K_5中的生成树的构造与计数

给出了生成子图和生成子图的计数定理。证明了生成子图的构造定理。提出了任意完全图Kp的生成树的计数方法和构造方法。给出了生成子树的计数公式。利用生成子圈的计数方法,寻找生成子图的生成树,证明了生成树的构造定理和计数定理。同时介绍了完全图K5的含圈生成子图及不含圈的生成树的计数和构造。生成树的计算公式过于庞大,且仅适用于完全图的Kp。平图例子验证了构造定理和计数定理的实用性和有效性,是构造一个完全图的生成树的简单易行的方法。     

有限图的边荫度分解

设有限图Ｇ＝（Ｖ，Ｅ），Ｐ＝｛Ｖ１，Ｖ２，…，Ｖｒ｝为Ｇ的一个划分，收缩Ｖｉ为一点ｖｉ（ｉ＝１，…，ｒ），得到Ｇ的收缩图ＧＰ＝（ＶＰ，ＥＰ）．文中通过对Ｇ递归地进行收缩，改进了Ｇ的边不重生成树数目的上界，并给出了Ｇ的边荫度分解的具体方法     

平面格图生成树的计数

设ｔ（ｍ,ｎ）和ｔ（ｍ,ｎ）分别是平面ｍ×ｎ格图生成树和对称生成树的数目,从而给出了ｔ（３,ｎ）和ｔ（３,ｎ）的闭公式以及ｔ（ｍ,ｎ）递推式阶的估计．     

具有最小子树数目的单圈图与双圈图

运用删边缩边原理,探讨了3种减小子树数目的变形,每一种变形都能比较一组图的子树数目的大小。在利用这些变形的基础上,刻画了具有最小子树数目的单圈图和双圈图的结构。