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

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

乘积图生成树的Wiener数问题

研究了给定一个连通图,如何确定其Wiener数最小的生成树问题。Dobrynin等构造了超立方体的两类Wiener数“很小”的生成树,并进一步猜想这两类树都是Wiener数最小的生成树。利用归纳推理及递归关系,对更一般的且具有良好拓扑性质和较高网络模型应用价值的乘积图,如G1×G2、Kmn等,构造了相应的生成树并计算了它们的Wiener数的值,以期获得这些乘积图Wiener数最小的生成树。这些结果推广了Dobrynin关于超立方体的结果。     

关于Kruskal算法的一个简便实现

根据数据结构中求一个带权无向连通图的最小生成树算法的特点,文章给出了Kruskal算法的一个简便而完整的C语言实现。特别是对不连通子图的刻画,只引进了一个一维数组就解决了问题。     

几类图的无符号Laplace矩阵的行列式

我们知道n个顶点的图G的无符号Laplace特征多项式为σ(G;λ)=det(λIn-Q(G))=n i =0移(-1)ibiλn-i, Cvetkovic等[6]给出了其系数bi的组合解释.我们发现det(Q(G))的值恰好是常数项系数bn.于是可以根据bn的组合解释来讨论图G的无符号Laplace矩阵的行列式.本文主要研究n个顶点的树、连通单圈图与连通双圈图的无符号Laplace矩阵的行列式的计算问题,给出了计算这些图类的无符号Laplace矩阵的行列式的一般方法,对研究图的无符号Laplace矩阵的行列式有着重要的意义.     

无向图的第二大生成树的算法

在一个有生成树的赋权图 G=(V,E)中,其最大生成树的算法是早已解决了的.但它是否还有第二大生成树呢?如果有,又如何去求它呢?关于这个问题,本文给出了解答.在一个无向图 G=(V,E)中,来规定各条边的方向.对于图 G 的每一条边 e∈E,规定一个权α(e)∈R~+(R~+是非负实数集合),树的权定义为树的各条边的权之和,对于图 G 的一棵生成树,如果它具有最大可能权,称这棵树为 G 的最大生成树.如果图 G 的生成树具有     

用基本割集组的余组生成含指定边的生成树

利用连通图基本割集组的余组,给出了求连通图含指定边生成树的一种简单、快捷的方法.     

具有第三大和第四大的Wiener指标的树

n个顶点的树记为T,连通图的Wiener指标等于图G中任意两点的距离之和.本文在引用文献[1],[2]两个引理的基础上,根据Wiener指标的计算公式及变换方法给出了具有第三大和第四大的Wiener指标的树.     

给定控制数的树的代数连通度

一个图G(V,E)的控制数γ(G)是V的这样一个子集S的最小基数,使得G中每一个顶点或者在S中或者和S中的一些顶点邻接.讨论给定控制数1,2,n/2的树的代数连通度,得出树T*=K1,y-1°K1具有最大的代数连通度;同时利用移接变形刻画出给定控制数2的树中具有最小代数连通度的极图,得出树T=T3(s3,t3)具有最小的代数连通度.     

连通图和不连通图的维纳指数W（G）

一个连通图的维纳指数W(G)等于图中所有无序点对的距离之和。本文研究了连通图和不连通图的维纳指数W(G),得到了上界图;以及研究了W(G) W(G)的上界和下界。     

组合计数的几个典型方法

在研究图的着色和树的计数问题中,遇到大量的复杂的计数问题,这些问题都不能用常规的计数方法来解决.交叉分类、发生函数以及Polya方法是解决这类问题的典型和有效方法,本文以代数学的视角阐述了这些方法的具体应用和解决技巧.     

图类Kn-PSm（a1,a2,…,am）的生成树数目

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

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

应用线性代数的方法，推广了Kirchhoff矩阵-树定理、得到了连通图中含某些指定边的所有生成树的计数公式；并且给出了Feussner递推公式一种更为具体的表达形式．     

关于图的临界群的秩

图的临界群决定了其支撑树的内部结构,因而支撑树的很多性质可以通过研究图的临界群得到.作为顶点数有限的图,其临界群是一个有限生成的群.该群的生成元的数目显示了群结构的复杂性.所需要用到的生成元的最小数目即为临界群的秩.在不引起混淆的情况下,临界群的秩也被称为图的秩.秩越小,临界群的需要的生成元的数目也就越小,研究的难度也相应越小.有一部分图的秩的下界可以通过计算直接得到.     

图类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)的一般情况的生成树的数目并得到了相关公式.     

图类 Kn-CS 4（a1，a2，a3，a4）的生成树数目最大化条件

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

基于蚁群算法UML活动图的测试用例生成研究

为了节约软件测试成本,减少测试用例数量,提出了一种利用蚁群算法直接从UML活动图中生成测试用例的方法。通过对UML活动图和蚁群算法进行形式化规约,构造人工蚁群,然后依据DFS遍历由UML活动图转化的有向连通图G,最后生成测试用例。通过仿真模拟,对提出的方法进行验证以及对实验结果进行分析,证明了该算法的可行性和有效性。     

非毛虫树的维纳指数最大值与最小值

一个连通图的维纳指数W(G)等于图中所有无序点对的距离之和.我们定义毛虫树为一棵树,并且满足当我们去掉其所有的悬挂点时成为一条路的树.设Rn为所有的含有n个点的非毛虫树的集合,在这篇文章中我们主要研究了Rn中的维纳指数最大值与最小值.     

连通简单图的典型着色

本文用图论知识利用连通简单图G的邻接矩阵来寻求其互不相交的极大独立集的方法,解决连通简单图G的典型着色问题.     

有关图论中生成树棵数的求法

迄今生成树棵数有两种求法,一是cayley公式,一是用关联矩阵来求.但这两种方法对于顶点个数和边的个数比较多的连通图使用起来不方便.本文给出两个定理,这两个定理和用关联矩阵法结合起来可以大大化简计算过程.且本文的定理2是cayley公式的推广.     

关于《连通图的平均距离》中的猜想

施容华在文[1]中提出如下猜想:G是n阶连通图,则有D(G)≤n/(δ+1).其中D(G)表示G的平均距离,δ表示G的最小度.本文给出了这个猜想的反例,并且对连通图的平均距离的上级做了进一步估计.