非齐次树上非齐次马氏链转移矩阵的一个极限性质

通过引入样本散度的概念和构造辅助非负鞅,利用Doob鞅收敛定理给出了非齐次树上k重非齐次马氏链转移矩阵的一个极限性质.

矩阵-树定理的一个简单证明

本文不用行列式计算中的Binet－Chachy定理，给出矩阵-树定理的一个简单证明．

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

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

关于树补图的A_(α)-谱半径的一些极值结论

设A(G)和D(G)分别表示图G的邻接矩阵和度对角矩阵,称A_(α)(G)=αD(G)+(1-α)A(G)为图G的A_(α)-矩阵,并称A_(α)(G)的最大特征值为图G的A_(α)-谱半径,其中α∈[0,1).图G的A_(α)-矩阵是图G的邻接矩阵和无符号Laplacian矩阵的共同推广.该文研究了树的补图中谱半径的排序问题,分别确定了最大度为△的n阶树的补图中A_(α)-谱半径的唯一极大和唯一极小图,还确定了n阶树的补图中唯一的A_(α)-谱半径极小图.在此基础上,得到了n阶树的补图中邻接谱半径的标尺定理(The Scalar Theorem).

半正则二部图的补图生成树计数的一种新方法

一个二部图G = (U, V, E)是半正则当且仅当同一部顶点集的两个顶点的度相等。 进一步,设G = (V1, V2, E)是一个二部划分为(V1, V2)的连通二部图,即V1 ∪ V2 = V (G) 且V1 ∩ V2 = ∅。 若G满足|V1| = s, |V2| = t,且∀ui ∈ V1, dG(ui) = x (i = 1, . . . , s), ∀vj ∈ V2, dG(vj ) = y (j = 1, . . . , t),则称G是一个半正则二部图,记作G = (s, t;x, y)。 利用Kirchhoff矩阵-树定理和矩阵的Schur补,本文得到一种半正则二部图的补图的生成树计数一般公式,并得到一些特殊半正则二部图补图的生成树数目计数公式。

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

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

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

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

无向循环图的支撑树数

设，gcd， 是个无向循环图，是其支撑树数。令 , 其模大于的根为 。本文证明了这里 ，并给出了几个例子。

几种图的生成树的数目

连通图G的生成树是它的极小连通生成子图。对给定图G来说,如何精确求解出图的全部生成树的数目,是图论中一个重要的问题;对于特殊的图类已经有着各种各样的计算方法,文章利用图的K irchhoff矩阵研究了一些图类的生成树的数目,并给出了相应的生成树数的计算公式。

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

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

关于图类Knm±G的生成树数目

记Knm(n≥2,m≥1)是n个顶点的完全多重图,即任意两个顶点间有且仅有m条边相连。Knm+G (或Knm-G)为在Knm基础上再添加(或从中删除)子图的对应边得到的图。Nikolopoulos和Papadopoulos利用Kirchhoff矩阵–树定理给出了Knm+G生成树数目τ(Knm±G)=m(mn)n-p-2det[mnIp±L(G)]。本文利用线性代数技巧(一个有关矩阵和的行列式计算公式),对该定理给出了一种新的简洁证法。并给出当G为完全图、圈、路、二部图时Knm±G生成数目的计算公式。

合成图K_(n^m)[G]的生成树计数公式

图的生成树的计数在图论及其应用的许多领域都有重要意义, 本文给出了合成图Kn[ G ]的生成树计数公式。

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

利用图G的标定技巧、矩阵和行列式运算、补生成树矩阵定理、不等式运算等理论,研究了当m=2,3,4,5,且a1,a2,…,am为任意数时,基于路的多重完全图相关图一般情况的生成树数目,并得到了相关公式。

图类K_n-C_4~s(a1,a2,a3,a4)的生成树数目最大化条件

利用图G的标定技巧、补生成树矩阵定理、线性代数的矩阵、行列式运算和不等式运算等理论,研究了补图类——当m比较小且为任意数时,基于圈的多重星相关图的一般情况(即a1,a2,…,am为任意数时)的生成树的数目最大时满足的条件并得到了相关结论。

图类K_n-P_m^S(a_1,a_2,…,a_m)的生成树数目

利用图G的标定技巧、线性代数的矩阵、行列式运算、补生成树矩阵定理和不等式运算等理论,研究当m=2,3,4,5时且a1,a2,…,am为任意数时,基于路的多重星图相关图Kn-PSm(a1,a2,…,am)的一般情况的生成树的数目并得到了相关公式.

一类平面图的生成树数目

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

欧拉回路与生成树的关系

计算图(有向图或无向图)中生成树的个数可以用组合的方法,也可以用代数的方法。介绍了用代数的方法求图中生成树的个数,给出了欧拉回路与生成树的关系,并将其应用于实际的问题中,解决了一类等价类问题。

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

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

扇图的生成树的计数

应用计算生成树个数的有向图方法、分块矩阵的行列式计算法以及常系数线性递归方程的解法,得到扇图的生成树个数的计算公式.

对称矩阵的行列式的Feussner展开及其在图论中的应用

在这篇文章中,我们将Feussner组合公式与Kirchhoff矩阵-树定理——组合方法与代数方法有机地结合起来,获得了Feussner组合公式的一种行列式表示形式并将这种表示形式推广为一般对称矩的行列式的一种递推展开式.最后用对称矩阵的行列式的这种递推展开式证明了Feussner组合公式与Kirchhpff矩阵-树定理的等价性.