一些具有非固定步循环图中生成树的个数

虽然没有简单易行的方法计算一般图中生成树的个数,对一些无向且具有非固定步循环图,可以给出简单的方法确定其中的生成树个数所满足的递推关系和渐进性质.     

循环图中生成树的个数

一般图中生成树的计数目前还没有简单有效的方法，对循环图中生成树的个数给出了简单的在线性时间内即可实现的计算方法，并应用到若干个具体的循环图。     

LSI布线设计中的最优树算法研究

本文讨论了在集成电路的布线设计中所碰到的求无向完全图的最优生成树问题,提出了一种求最优树的上三角阵算法(简称M-算法) .描述了支持这种算法的数据结构.对完全图G(n,e),M-算法的计算复杂性是O(n~3),空间复杂性是O(n~2),在相同的空间复杂性条件下,比直接用Kruskal算法要优越.     

基于改进Wang-代数生成连通图全部树的方法研究

提出了一种求连通图全部树的方法,通过对Wang-代数的改进,在生成连通图的全部树时,无需进行环和运算,从而减少算法的时间复杂度;同时能求得图的全部树,并且能保证同一个树不会重复产生,克服了传统Wang-代数法求连通图的全部树时产生的冗余项问题.算例表明方法的正确性和可行性,可有效地应用于复杂电网络的拓扑分析.     

一类树Hosoya指标的研究

设G是一个分子结构图模型,即为一个具有n个顶点的连通图.则图G的Hosoya指标Z(G),是指图G中匹配的个数,包括空集. 该文讨论了四叶树Hosoya指标的第二大、第三大、第四大值.     

图色数的一种求法

利用组合数学中图转化成树的思想,从图中一顶点出发,按照图的邻接矩阵中各顶点间边存在的情况,建立各级树,根据要着色的顶点与已着色顶点间边存在的情况,给所要着色的顶点着色.当所有顶点都已着色后,所用颜色个数就是图的色数.     

可分拟满Steiner树的结构性质与最优生成算法的研究

研究可分拟满Steiner树的结构性质与最优可分拟满Steiner树的生成算法.     

两类图在球面和环面上的嵌入

图在不同亏格曲面上的嵌入往往有相关关系,因此,分析一些图类在小亏格曲面上的嵌入是一项有意义的工作.本文利用刘彦佩教授提出的嵌入的联树模型研究了两类图在球面和环面上的嵌入特征,分别得到了它们的嵌入个数.     

中国展览馆问题与平图的4着色

提出了中国展览馆问题,目的就在于解决：①任意图的4着色问题;②任意图的生成树的构造与计数问题。阐明了解决对偶图4着色问题和任意C（p,q）的生成树的构造与计数问题的基本思路．提出了基于森林E分解的对偶图的顶点4着色方法和基于2颗被分解的对偶树T^A和T^B进行任意图的生成树构造的方法．介绍了森林Fi的3种分解方法．     

流量约束最小生成树问题的分枝定界算法

研究流量约束最小生成树问题(CMST),它是通讯和网络优化设计中最为基础和重要的问题之一.给出一种分枝定界算法,详细阐述了算法的原理、搜索过程,数值结果表明,该算法是有效的,并且有较好的计算性能.     

标号完全多部图的非平凡有根支撑森林的计数

文[1]中,柳柏濂与黄凤英研究了标号完全二部图的非平凡有根支撑森林的计数问题.在本文中,我们对该问题进行了自然地推广,解决了标号完全多部图的非平凡有根支撑森林的计数问题.进一步地.我们获得了标号完全多部图的包含s个s(≥0)平凡树的有根支撑森林的计数公式.     

轮图相关图的临界群

图的临界群是图的生成树数目的一个加细.它是图的一个精细不变量.确定了修改轮图的临界群的结构,给出了它们的临界群的Smith标准形的精确形式,证明了它们的临界群总是循环群或两个循环群的直和.     

树与路的冠图的临界群(英文)

图的临界群是图生成树数目的一个加细.它是图的一个精细不变量,与图的Laplacian矩阵密切相关.将冠图分为点冠图和边冠图,通过在整数环Z上实施一系列的行列变换来计算整数矩阵的Smith标准型,从而确定了点冠图Tm○Pn和边冠图Tm◇Pn的临界群的代数结构.进一步,证明了点冠图Tm○Pn和边冠图Tm◇Pn的临界群的Smith标准型分别为m和2(m-1)个循环群的直和,同时给出了图Tm○Pn和Tm◇Pn的生成树数目.     

双圈图的代数连通度排序

Abreu指出"用代数连通度对树进行全排序仍然是个公开的问题".同时,郭继明对树和连通图用代数连通度进行了排序.受到上述研究成果的启发,按照代数连通度从大到小的顺序确定双圈图的前五大值,以及达到这些值的图.     

一些由它的Laplacian谱确定的树

探讨了“哪些图由它的Laplacian谱确定?”的问题.利用同谱图的线图的特点,证明了一些特殊结构的树,如梳图,烷的一个同分异构体的分子图,恰有两个Laplacian特征值大于2的树(包括双星图)等,各自由它们的Laplacian谱确定.     

树的拓扑指标Z_1(G)

分子图的拓扑指标Z1(G)是反映分子物理和化学性质的重要拓扑指标,在n个顶点的树中具有最大Z1(G)和最小Z1(G)的树的基础上确定了n个顶点的树中具有次大,第三大及第四大Z1(G)的树.     

关于简单图的Chartrand问题的下界

本文证明任意一个圈秩为ρ的简单连通图G若含有m个端点及n个端点的撑树,且m < n,则对任意的m < k < n,G至少含有ρ+1个具有k个端点的支撑树.     

阶数最小的A(H)=4的非树图

本文构作了全部阶数最小的A(H)=4的非树图，它们的阶数为7．