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

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

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

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

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

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

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

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

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

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

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

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

偶阶完全图Kp的生成树的计数

给出了生成子图的定义.证明了生成子图的计数定理和构造定理.提出了生成树的计数方法和构造方法.介绍了完全图K6的含圈的生成子图和不含圈的生成树的计数与构造.     

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

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

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

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

奇阶完全图K_p的生成树的构造与计数

给出了生成子图的定义。证明了生成子图的计数定理和构造定理。提出了生成树的计数方法和构造方法。介绍了奇阶完全图K_5、K_7的含圈生成子图和不合圈生成树的计数与构造。     

某些伪类环图的生成树数

连通图的生成树是指该图的极小连通生成子图.通过Cayley公式、递推关系式及伪类环图与伪类环图生成树数之间的关系式给出伪类环图-Sn,-An的生成树数.     

若干图类的生成树数

连通图的生成树是该图的极小连通生成子图。本文求出了所有梯形图、扇形图和轮形图生成树的棵数，分别给出了它们的递推关系式和通项表达式．     

连通图含某些指定边生成树的环和矩阵生成法

提出并研究了连通图含某些指定边的生成树的生成问题.在给出环补关联矩阵与环和矩阵等定义的基础上,给出并证明了连通图含某些指定边的生成树的生成方法(环和矩阵法).利用环和矩阵法寻求图的特殊的生成树的方法、步骤以及其准确性和快捷性也在文中进行了讨论.     

4连通图中生成树上的可去边

图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割端片的性质给出某些4连通图中在特定子图上可去边的分布情况,得到了最小度至少为5或围长至少为4的4连通图中在其生成树上存在至少两条可去边;同时也得到了最小度至少为5的4连通图中在其生成树外存在至少两条可去边.     

一类平面图的生成树数目

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

关于判定超欧拉图的收缩法

P.A.Catlin提出一个问题：设H是图G的一个连通子图，如果G关于H的收缩图G/H有一个欧拉生成子图，那么在什么条件下G也有一个欧拉生成子图？研究了这一问题，讨论了Catlin提出的用收缩法判定超欧拉图的两个定理，给出了一些实用的超欧拉图的判别方法。     

树扩图生成树数的界

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

RP图的特征刻划

设T是图G的一颗支撑树,若某顶点u满足;对任意顶点υ均有dG(u,υ）=dT(u,υ）,则称u对于支撑树T是RP,如果对G的任一棵支撑树都至少存在一个RP点,则称图G是RP图,Gagliardi等在1997年证明了K2,n是一类RP图,并猜想：“K2,n以及在其顶点上加上若干树状结构所得的图是仅有的RP图”。但容易验证圈Cn也是一类RP图,因此上述猜想需要修正,本文证明了RP图的如下特征刻划：除树外,简单图中只有K2,n和Cn 以及在某若干顶点上分别外接互不相交的树状结构所得的图是RP的。