关于生成树的计数问题

本文论证了对连通图G的生成树的计数问题可归之于计算其块图的生成树的棵数问题,从而提供了计算图G的生成树数目的一种简便的计算方法。关键词:生成树,割边,制点,块图计算连通图G中生成树的数目,是图论计数问题中一个重要而且有趣的课题。目前已经有一些计算生成树数目的方法和公式。本文拟在现有计算公式基础上对若干图类的生成树的计数问题提供简便的计算方法。     

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

关于树的几个结果

树在图论研究以及复杂网络研究中常常用到.记号nd(G)表示图G中顶点度数为d的顶点的数目.本文利用树T的1度顶点个数可以由公式n1(T)=2+△(G)+D(G)n+1.对平面图G,它的面数(G)满足2(G)=4+d3Σ(d-2)n(dG).     

扇图的生成树的计数

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

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

利用图 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 为任意数时）的生成树的数目最大时满足的条件并得到了相关结论。     

求图全部生成树的置换法

介绍了生成树的矩阵算法和求图全部生成树的置换法，这些方法不仅能解决许多实际问题，而且全部求解过程容易通过计算机来实现。     

图Pn×C4的临界群

图的临界群是图的生成树数目的一个加细.它是图的一个精细不变量.确定Pn×C4的临界群的结构.证明了Pn×C4的临界群的Smith标准形总是两个或三个循环群的直和.     

Kirchhoff矩阵树定理的一个推广

Kirchhoff矩阵树定理是图论中的一个重要定理 ,本文对Kinchhoff矩阵树定理进行推广 ,给出图的k -支撑林的数目与其Kirchhof矩阵n -k阶子式的关系     

乘积图生成树的Wiener数问题

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

最小生成树聚类方法研究

由聚类所生成的簇是一组数据对象的集合,在同一个类中的对象之间具有较高的相似度,而不同类中的对象差别较大.图的最小生成树具有最优子结构性质,删除最小生成树的最大边后的两颗子树依然分别是两个子图的最小生成树,因此可由生成图的最小生成树获得聚类.此方法适用于所有欧氏空间数据的聚类.     

最小生成树聚类方法研究

由聚类所生成的簇是一组数据对象的集合,在同一个类中的对象之间具有较高的相似度,而不同类中的对象差别较大.图的最小生成树具有最优子结构性质,删除最小生成树的最大边后的两颗子树依然分别是两个子图的最小生成树,因此可由生成图的最小生成树获得聚类.此方法适用于所有欧氏空间数据的聚类.     

能力集扩展的表格方法

每个具有非对称权重的有向图均可用一个称为“扩展表”的矩阵或表格来表示 .讨论了扩展表中的“圈”和“生成表”的概念及其基本特性 ,给出了一种寻找有向图最小生成树的表格方法——最小生成表法 .研究了最小生成表算法在最优能力集扩展问题中的应用 ,给出了一个算法的具体示例 ,并分析了有关的需研究的问题和可能的拓展     

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

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

基于网络分级优化和Dijkstra算法的最短路径求解改进

对大型复杂网络提出网络分级的思想,根据网络分级的情况定义网络结点的数据结构,然后使用改进的Dijkstra算法和最小生成树算法来计算网络中任意两结点之间的最短路径。     

基于熵的决策可信度分析

从分类的角度进一步阐述了信息熵的概念，使得利用信息熵的方法构造决策树有了更加坚实的数学基础，研究了信息熵与决策可信度的关系，给出了利用信息熵计算决策最大和最小可信度简单、直观易操作的算法，在期望信息熵较小时计算得出的最大和最小可信度是非常接近的，因此可以用它来做估计决策可信度的依据，实验结果也表明计算的结果和实际的决策可信度是非常接近的。