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

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

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

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

不可满足公式的同态证明系统

合取范式(CNF)公式 H 到 F 的同态?是一个从 H 的文字集合到 F 的文字集合的映射,并保持补运算和子句映到子句.同态映射保持一个公式的不可满足性.一个公式是极小不可满足的是指该公式本身不可满足,而且从中删去任意一个子句后得到的公式可满足.MU(1)是子句数与变元数的差等于 1 的极小不可满足公式类.一个三元组(H,?,F)称为 F 的一个来自 H 的同态证明,如果?是一个从 H 到 F的同态.利用基础矩阵的方法证明了:一个不可满足公式 F 的树消解证明,可以在多项式时间内转换成一个来自 MU(1)中公式的同态证明.从而,由 MU(1)中的公式构成的同态证明系统是完备的,并且由 MU(1)中的公式构成的同态证明系统与树消解证明系统之间是多项式等价的.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

几类平面图生成树数目的一种求法

求连通图生成树数目的方法有很多。本文利用平面图的对偶图的Kirchhoff矩阵求出梯形图,扇形图和轮图的生成树数目,这类平面图利用收缩边和去边的方法已经求出,但用本文的方法更简单直接且便于推广到一般平面图。

一类柱面上的格子图的生成树数

计算一个图的生成树数问题在数学、物理和化学等很多领域都被广泛的研究.该文考虑具有柱面条件的一类网格图的生成树数,给出了生成树数的显式表达式.

连通图中含某些指定边的生成树的计数

应用线性代数的方法 ,推广了Kirchhoff矩阵—树定理、得到了连通图中含某些指定边的所有生成树的计数公式 ;

关于树补图的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).

树指标马氏链随机矩阵的一个强极限定理

给出了树指标m重非齐次马氏链随机矩阵的一个强极限定理.