一类平面图的生成树数目

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

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

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

一类广义双锥图的生成树数目

证明了一类广义双锥图的生成树数目可以转化为一个二阶行列式的计算,以此得到了特殊图类的生成树数目的显式表达式,并推广已有的结果.     

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

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

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

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

极大平面图对偶二色子图结构特性树

本文在论文[1]的基础上给出极大平面图的另外一种商图,即极大平面图对偶二色子图结构特性图.证明极大平面图对偶二色于图特性图是树,并给出它的若干性质.     

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

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

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

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

基于对偶图的对偶树分解的4着色

阐明了对偶图G(p,q,f)4着色的基本思路,提出了n面体的展开图G′(f,s,t)与对偶图G(p,q,f)之间的依存关系,根据这种依存关系,提出了对偶图G(p,q,f)的对偶树及三胞胎树的3种不同的算法,同时提出了这3种算法的适用范围和条件。根据4着色理论,阐明了基于对偶树分解和三胞胎树分解的对偶图G(p,q,f)的4着色方法。文中以20面体为例,介绍了20面体的展开图与对偶图G(p,q,f)之间的对偶关系图和20面体平图的对偶图G(p,q,f)的4着色的全过程,提出了具体的实施步骤,并根据步骤得出相应的结论。     

树扩图的生成树数

连通图的生成树是指该图的极小连通生成子图,本文在Cayley公式的基础上,给出每一树扩图类Pn（t）、K1,n-1（t）、Tn（a1,a2,…,ak;t）、Tn,k（t）中的图的生成树数相同．     

组合图中生成树的计数

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

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

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

循环图中生成树个数的渐近性质

就给定的整数s1,s2,…,sk,1≤s1≤s2≤…≤sk,给出了一种简单的方法来计算Cn^21,s2,…,sk中生成树个数的渐近性质,证明了该渐近性可以归结为求解一个次数为2sk-2的多项式,并将这种计算方法应用到若干个循环图作为例子．     

基于Global optimization寻找无向完全图的最小生成树

将Global optimization思想引入到寻找无向完全图最小生成树的问题中,提出了Global optimization算法。与Kruskal算法和Prim算法相比之下,此算法避免了求解过程中对生成树中是否出现回路的判断,并在一定程度上降低了时间复杂度。     

树扩图生成树数的界

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

非固定步长的无向循环图的支撑树数

图的支撑树数是图的重要的不变量,也是网络可靠性的重要量度.循环图是一个重要的图类,可应用于局域网和分布系统的设计中.对有固定步长的循环图,其支撑树数已得到了研究.本文考虑有非固定步长的无向循环图Cpn(a1,a2-,…,ak,q1n,q2n,…,qmn),这里a1,a2,…,ak,q2,q2,…,qm,n和p都是正整数,a1≤a2≤…≤ak≤n/2,q1≤q2≤…≤qm≤p/2,且n是可变化的,因而有些步长并非固定.给出其支撑树数的一个公式,并得到其渐近性态和常数系数的线性递归关系.