连通图的基本割集多项式生成所有支撑树的一种证明

连通图必存在支撑树，且支撑树一般不唯一。如何得到连通图的所有支撑树，是图论中讨论的一个重要问题。利用基本割集对应的子图多项式生成所有支撑树是一个简单可行的方法^[1]，现有的对这种方法的理论证明较繁琐。本文给出一种较直观的证明，说明该方法可生成全体互异的支撑树。     

若干图类的生成树数

连通图的生成树是该图的极小连通生成子图。本文求出了所有梯形图、扇形图和轮形图生成树的棵数，分别给出了它们的递推关系式和通项表达式．     

边权相同的最小生成树改进算法

针对当赋权连通图中存在权值相同的多条边时,传统的Kruskal算法不能计算出全部的最小生成树,提出了求解最小生成树的改进算法.实验结果表明,改进算法可以得到一个赋权连通图的所有最小生成树,进而为决策者提供更全面的最优决策方案.     

图的局部连通性与上可嵌入性

研究局部连通图中支撑树的变换. 给出L.Nebesk定理的一个新证明, 并将其推广得到一类新的上可嵌入图.     

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

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

简单有向连通图关联矩阵右逆的图特征及应用

研究ｎ阶简单有向连通图的ｎ－１传导矩阵,引入了图真值向量及运算,得出ｎ阶简单有向连通图关联矩阵右逆的图特征;提出了一种寻找简单有向连通图全部生成树的方法。     

树扩图生成树数的界

连通图的生成树是指该图的极小连通生成子图．在Cayley公式的基础上，给出树扩图生成树数的上下界．     

次优树问题

本文基于“最优树算法”,在赋权连通图关于最优树的基本圈中,通过边权的比较,得到了次优树的算法,並给出了证明,从而解决了如何把一个赋权连通图的所有生成树按权的大小进行排序的一种方法。由此对工程设计中经常迂到的“连线问题”,可以给出各种不同的设计方案,供决策部门选择。     

4连通图中生成树上的可去边

图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割端片的性质给出某些4连通图中在特定子图上可去边的分布情况,得到了最小度至少为5或围长至少为4的4连通图中在其生成树上存在至少两条可去边;同时也得到了最小度至少为5的4连通图中在其生成树外存在至少两条可去边.     

赋权连通图的最小树图的连通情况

以G的生成树为点,两点相邻的充要条件是两颗生成树只相差一条边,这个图称为G的生成树图。连通图的生成树图是连通的,本文对此进行推广,证明了赋权连通图的最优树图也是连通的。     

固定直径的树的Harary指数

图G的Harary指数定义为图中所有点对的反距离之和.给出了固定直径的树的Harary指数的第二大值,并刻画了对应的极图.     

计算全部树的撕裂算法

提出一种求连通图的全部树的方法，该方法采用撕裂大图分为两个连通片，然后添加撕裂边，便生成全部生成树，该方法可用于计算机并行运算，适用于大网络的计算机辅助分析。     

无向色图的Hamilton性

本文应用群论方法，证明了有限交换群的连通无向色图Ｇ（Ｆ，Ｓ）是Ｈａｍｉｌｔｏｎ图。并由此得到：（ｉ）Ｂｏｏｓｃｈ—Ｔｉｎｄｅｌｌ猜想的另一证明；（ｉｉ）有限交换群Ｆ具有对称色集Ｓ的连通色图Ｄ（Ｆ，Ｓ）是有向Ｈａｍｉｌｔｏｎ图。     

网络图上的分段线性分式规划模型及有效算法

为了得到网络图上分段线性分式规划问题的有效算法，借助于线性规划问题的单纯形方法及网络图上修改支撑树的迭代方法，论证了一个基本可行解是否最优解的判别准则，并给出了网络图上分段线性分式规划问题的一个有效算法。为进一步解决网络图上非线性目标函数的优化问题提供了依据。     

一种计算复杂网络可靠度的新算法

利用基于基本互补划分（ＥＣＰ）求复杂网络的树的原理，发展了一种新的求不交化树的方法，从而能有效地计算一个复杂网络的全可靠度     

立方图中的路因子和圈因子

给定连通图集合Φ,对图G的生成子图F,如果F的每个分支都同构于集合Φ的一个元素,则F被称为G的Φ-因子.最近Kawarabayashi 等证明了:2-连通立方图有一个{Cn|n≥4}-因子和{pn|n≥6}-因子,其中Cn表示阶为n的圈,Pn表示阶为n的路.Kano等给出了每一个阶至少为8的立方偶图有{Cn|n≥6}-因子和{pn|n≥8}-因子的结论,并且提出猜想:阶至少为6的3-连通立方图有{Cn|n≥5}-因子和{pn|n≥7}-因子.现给出这个猜想的证明.     

带约束边的最优树问题

本文给出了求解一个赋权图中含有约束边的最优树的两种算法和证明。并在此基础上,给出了关于含有约束边最优树的一些推广问题的算法和证明。