求最优树的顺序破圈法

最优树问题在生产实践中有广泛的应用。木文给出了一种求最优树的力法——顺序破圈法。它比管梅谷教授所提出的方法——破圈法,证明简单、计算方便。容易在计算机上实现。     

用图论理论正确掌握破圈法

用图论中有向树和赋权图的理论指出了一些书中所讲破圈法的错误，同时也点出了求网络图中关键路线的两种新方法，详细说明了如何正确使用破圈法。     

破圈法解动态规划中的最短路问题

运筹学动态规划多阶段决策中的最短路问题有多种解法。把求最小树的破圈法扩展用于有向图中解最短路问题,较之常用的Dijkstra方法更直现快捷。     

独弦圈的算术性

一个（ｐ，ｑ）一图Ｇ被称为（ｋ，ｄ）是一算术的，如果其顶点用不同的非负整数标号，使其边值为一个等差级数ｋ，ｋ＋ｄ，ｋ＋２ｄ，．．．，ｋ＋（ｑ－１）ｄ，其中每条边值是相邻两顶点的标号和，本文证明独弦圈是算术图。     

几类乘积图的圈覆盖

文献［１］提出猜想：每个２─连通ｎ阶简单图都有一个圈覆盖Ｃ，使得｜ｃ｜≤（２ｎ－１）／３。此猜想至今尚未完全证实。本文对路、圈、完全图的若干笛卡尔乘积图和张量乘积图证实了猜想是正确的。     

Fan定理的简捷证明

本文研究的图是简单图Ｇ ,限于本文的使用 ,记Ｆａｎ =ｍｉｎ{ｍａｘ{ｄ(ｘ) ,ｄ( ｙ) }|ｄ(ｘ ,ｙ) =2 }.Ｆａｎ定理[1 ] 　 2连通ｎ阶图Ｇ ,Ｆａｎ≥ｎ/2 ,则Ｇ是哈密尔顿图 (Ｈ图 ) .证明　假设Ｇ不是Ｈ图 .记Ｇ的一最长圈为Ｃｍ:Ｘ1 Ｘ2 …ＸｍＸ1 ,因Ｇ是 2连通的 ,记Ｘｉ,Ｘｊ 为和Ｇ -Ｃｍ 的一分支Ｇ1 中 ｙ1 ,ｙ2 相邻的两点 ,且满足 {Ｘｉ+1 ,Ｘｉ+2 ,… ,Ｘｊ- 1 }中没有点和Ｇ1 中点相邻 .情况 1　ｄ( ｙ1 ) <ｎ/2 ,且ｄ( ｙ2 ) <ｎ/2 .此时由Ｆａｎ≥ｎ/2 ,知ｄ(Ｘｉ+1 )≥ｎ/2 ,ｄ(Ｘｊ- 1 )≥ｎ/2 ,因Ｃｍ 为最长圈 ,所以 ( …     

失效树分析的一种算法

本文介绍相干失效树的一种确定性算法:比特变换——分类去冗算法。本算法程序如稍加改动,即可用于非相干失效树的计算。     

每个直径不大于2的图的线图是泛圈的或4圈或5圈

图的直径是指图的顶点间的最大距离，该文证明了每个直径不大于２的图的线图是泛圈的或是４圈或５图，且所给条件是最好可能的。     

完全图的Hamilton圈分解

在文[3]中,Hoffman等证明了完全图Kn中最多边不交的Hamilton圈个数为「n-1/2」.然而根据文[3]中的证明方法,要具体表示出这「n-1/2」个边不相交Hamilton圈是非常困难的.文章给出了完全图的Harailton圈分解的一种简便方法.     

树的等价定义及其证明

本文给出并证明了树的七种等价定义。     

简单图中哈密尔顿圈的个数

给出了计算简单图中哈密尔顿圈个数的几个公式,并对简单图中哈密尔顿圈个数的上下界进行了讨论。     

哈密尔顿图与泛圈图的几个性质的探讨

让NC＝min｛U（x)∪N(y)||x,y∈V(G),xy不属于E（G|｝,R.J.Faudree等曾得到NC≥n-δ,则G是哈密尔顿图。本文进一步研究NC≥n-δ-1的哈密顿性，推广了文前人的结果。     

S—控制圈的一个充分条件

设Ｇ是ｋ—连通的ｎ阶图，ｋ≥２，若对于Ｇ中的满足（对任意的任意（ｋ＋１）—独立集Ｘ，有则Ｇ中存在Ｓ—控制圈．     

最优树的若干问题

利用图的关联矩阵，给出了最优树的矩阵算法，并对当图的一条边的权发生改变后，如何利用原最优树求现最优树作了探讨。     

图的长控制圈

设G是具有一个控制圈的图 ,证明了如果在G的每一个圈C上总存在点ν0 ,使得dR(ν0 ) >1,其中R =V(G) \V(C) ,那么G必包含一个长度至少为min{n ,2NC2 (G) -1}的控制圈 ;如果G的每一个控制圈为偶圈 ,那么 ,G包含一个长度为min{n ,2NC2 (G) }的控制圈 ,从而证明了R .Shen和F .Tian的猜想 .