计算全部树的撕裂算法

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

λ_(3,q)-连通图的刻画(英文)

连通图G称为λ3,q-连通的如果存在边割S使得G-S有两个阶数分别至少为p和q的连通分支。给出一个图是λ3,q-连通的一些充分和必要条件。     

2和3连通图中的禁止子图与哈密顿性质

证明了如下结果：（１）若Ｇ是２－连通的（Ｋ１，３，Ｐ５，Ｂ）－自由图，或２－连通的（Ｋ１，３，Ｚ２，Ｐ５）－自由图，则Ｇ是哈密顿图，（２）若Ｇ是３－连通的（Ｋ１，３，Ｚ１）－自由图，或３－连通的（Ｋ１，３，Ｚ２，Ｐ５）自由图，或３－连通的（Ｋ１，３，Ｐ５，Ｂ）－自由图，则Ｇ是哈密顿连通的。     

树扩图生成树数的界

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

树扩图的生成树数

连通图的生成树是指该图的极小连通生成子图,本文在Cayley公式的基础上,给出每一树扩图类Pn（t）、K1,n-1（t）、Tn（a1,a2,…,ak;t）、Tn,k（t）中的图的生成树数相同．     

图的路连通问题

如果图Ｇ的每对不同顶点ｕ和ｖ之间都有哈密顿路相连，则称Ｇ是哈密顿连通的；而如果对于所有满足条件以ｄ（ｕ，ｖ）≤ｑ≤ｎ－１的整数ｑ，ｕ和ｖ之间有长为ｑ路相连，则和Ｇ是泛连通的，其中以ｄ（ｕ，ｖ）是ｕ和ｖ间的距离，而ｎ是Ｇ的顶点数。本文证明了下述两个结果：（１）２ｋ＋１个顶点的ｋ正则简单图是哈密顿连通的，（２）ｋ连通国中任何两顶点之间存在ｋ－１条长度不同的路；进而如果Ｇ的顶点数小于２ｋ，则Ｇ是泛连通的。     

关于哈密顿图的一点注记

如果图G含有一个过G中每个顶点恰好一次的圈,则称G是一个哈密顿图。对于含有两个不相邻顶点a和b的图G,本文给出了一些条件,如果G满足这些条件,且G ab是哈密顿图,则G也是哈密顿图。     

邻接树图的连通度

设Ｇ是任一连通图，Ｈ是Ｇ的邻接树图，κ（Ｈ），λ（Ｈ），δ（Ｈ）分别是Ｈ的连通度，边连通度和最小次，则κ（Ｋ）＝λ（Ｈ）＝δ（Ｈ）。     

二连通图的最长圈

本文证明:设G为n阶2连通图,D(x)={y|y∈V(G),d(x,y)≤2},d_d~*(x)表示D(x)中所有的点的度排成的非减度序列:d_1~*,d_2~*,…,d_j~*,d_(j+1)~*,…,d_(|D(x)|)~*中当下标j=d(x)时的度。δ_0=min{d(x)|x∈V(G)},D(δ_(i-1))={x|x∈V(G),d(x)≥δ(i-1)}(i=1,2,…,k),δ_i=min{d_(d(x))~*|x∈D(δ(i-1))}(i=1,2,…,k)且δ_0<δ_1<δ_2<…<δ_(k-1)≤δ_k,则C(G)≥min{n,2δ_k}。此外也给出δ_k的算法。     

最小生成树问题

本文给出了最小生成树的一种计算方法，并介绍微机软件ＹＡＪ（运筹学和计算机）在此问题上的应用。     

具有二分划(A_1;A_2)的二连通偶图的(A_1;A_2)Hamilton连通性

给出了具有二分划(Ａ１,Ａ２)ｎ阶２连通偶图Ｇ(Ａ１,Ａ２),当Ａ１＝Ａ２时为(Ａ１,Ａ２)Ｈａｍｉｌｔｏｎ连通的定义·采用反证法,将图Ｇ(Ａ１,Ａ２)分为若干情况,利用图Ｇ(Ａ１,Ａ２)的２连通性及Ａ１＝Ａ２,证明了若ｎ≤４δ－２,则Ｇ(Ａ１,Ａ２)是(Ａ１,Ａ２)Ｈａｍｉｌｔｏｎ连通的·     

3连通图生成树上的可去边

摘要：设G是3连通图，e是G中的一条边．若G—e是3连通图的一个剖分．则称e是3连通图G的可去边．否则，称e是G的不可去边．本文给出某些3连通图的生成树上可去边的分布情况及数目。     

2-连通正则图中最长ab-路

在 Ｈ．Ａ．Ｊｕｎｇ定理的基础上，讨论Ｔ ２－连通正则图中最长 ａｂ－路 Ｐａｂ的路长。设Ｇ是ｎ阶ｋ正则具有二分类（Ｖ１，Ｖ２）的偶图，对任意ａ，ｂ∈Ｖ（Ｇ）．ａ≠ｂ， 若有或 ａ． ｂ ∈ Ｖ２则称Ｇ有Ｈａｍｉｌｔｏｎ性质。一个非偶图若是Ｈａｍｉｌｔｏｎ连通的，则称为具有Ｈａｍｉｌｔｏｎ性质。限制｛ａ，ｂ｝不是Ｇ的割集，具有上述性质的Ｇ称为有弱Ｈａｍｉｌｔｏｎ性质。作者得到如下定理：令Ｇ是２－连通ｋ正则的图，且｜Ｇ｜≤３ｋ－２（ｋ≥９）．则Ｇ有弱Ｈａｍｉｌｔｏｎ性质。     

k-连通半无爪图的Hamilton性质

半无爪图是包含无爪图的更大的图类。关于k-连通半无爪图,得到以下结果:G是k-连通的半无爪图(k≥2),如果对于G2的任意基数为k 1的独立集X,都有∑d(v)≥n-k,则G是Hamilton图。     

关于Ore的一个定理的简单证明

令G（V,E）是简单图,Ore研究了不相邻两点情况的哈密尔顿连通图。本中,我们进一步研究较好条件的长为2点的哈密尔顿连通图情况。结果不仅比Ore的好而且证明方法更加简单。     

最小生成树边与边的权的调整

图的最小生成树已经有了好算法，但当图增加或删去几条边或少数几条边的边调整时，最小生成树的边、权可能发生变化，用原算法寻找最小生成树时，显得比较麻烦．利用破回路算法给出一个简单的 方法．并给出了相应的示例．     

涉及距离的哈密顿连通图

证明了下面的结论：设Ｇ是ｎ阶３－连通图，如果对任意满足ｄｉｓｔ（ｕ，υ）＝２的顶点｛ｕ，υ）（Ｇ），有ｍａｘ｛ｄ（ｕ），ｄ（υ）｝＋｜Ｎ（ｕ）∪Ｎ（υ）｜≥ｎ＋１，则Ｇ是哈密顿连通的．     

最小支撑树的新算法

从树的等价定义出发,叙述并证明了一种不必考虑圈的求最小支撑树的算法.     

探讨无标度网络(图)的平衡集

无标度网络的无标度性导致其各顶点之间的连接状况(度数)具有严重的不均匀分布性,无法给出无标度网络的具体结构,不能直接观察信息传播的具体路径。基于利用生成树来研究无标度网络(图)的拓扑结构思想,尝试寻找与时间和次要节点无关的无标度网络(图)的普适性结构,研究与生成树密切相关的平衡集,给出一个寻找具有较多叶子生成树的算法。     

关于拓扑指标Z2(G)研究的一个结论

分子的化学与物理性能一般能用分子图的拓扑指标统计地反映出来．反过来，通过对分子图的拓扑指标的研究，以期得到理想的分子具有重要的理论价值和应用背景．文中解决了两个问题：1．对于任意的自然数Z，是否都存在一个简单连通图G，使得Z2(G)=Z?2．对于任意的自然数Z，是否都存在树T，使得T2(T)=Z?