任意无向图的最小R边连通扩充

研究了以最少边集扩充一个任意无向图为R边连通图这一优化问题。给出了一个复杂度为O(|V|~5)的算法。利用该算法可最优地将所研究图形中任意两点达到所要求的边连通度。它发展了K边连通最优扩充的研究,从而使图的边连通扩充的研究在应用于网络结线的可靠性设计方面更具有实际意义。     

无向树图的k点连通最小扩充

解决了以最少边集扩充一个任意无向树图为k点连通图这一优化问题,提出了一个计算复杂度为D(|V|~4)的算法。为进一步研究可靠网络的计算机辅助设计打下基础。     

任意无向加权图K点连通扩充的逐次改善算法

为了对网络的可靠性寻求较好的近似算法,研究了任意无向不加权图情况下的极小K 点连通扩充算法;在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理,并加以证明.最终推出了任意无向加权图K点连通最小扩充的逐次改善算法,应用该算法作了大量例题,得到比较满意的效果.为解决任意无向加权图最小扩充问题给出了一种新途径.     

基于改进遗传算法的无向加权图的k点连通扩充

加权图的连通扩充问题已被证明是NP完全问题，作者提出一种改进遗传算法来解决无向加权图的k点连通扩充问题，通过改进遗传算法中的交叉和变异操作有效地改善了群体的效果，有助于搜索解空间中新的区域，能以较大概率搜索到全局最优，仿真结果表明，该算法在原来简单遗传算法上做了进一步改善，为解决加权图的扩充问题提供了新的方法。     

无向图的一个距离不等式

对任一无向图Ｇ（Ｘ，Ｅ），顶点集Ｘ＝｛ｘ１，ｘ２，…，ｘｎ｝，任给三点ｘｉ，ｘｊ，ｘｋ，若两两之间存在距离，则成立不等式：ｄ（ｘｉ，ｘｊ）Ｇ＋ｄ（ｘｉ，ｘｋ）Ｇ＋ｄ（ｘｊ，ｘｋ）Ｇ≤２ｎ－２。     

简单无向连通图的k阶幂图的指数集

设Ｇ为简单无向图，以Ｖ＝Ｖ（Ｇ）为顶点集，以Ｅ＝｛（ｕ，ｖ）｜ｄ（ｕ，ｖ）≤ｋ｝为边集的图称为Ｇ的ｋ阶幂图。ｎ阶简单无向连通图的ｋ（ｋ≥２）阶幂图的指数集。     

含一个割点的连通图的最小特征值

一个图的无符号拉普拉斯最小特征值在某个图类中的所有图中达到最大时常称为极大图;通过利用特征向量方程研究特征值的方法,对只含有一个割点的连通图的无符号拉普拉斯最小特征值进行了研究,且得到了最小特征值的值,从而得到了只含有一个割点的具有相同阶数的所有的连通图中最小特征值的极大值,并且刻画了最小特征值取到极大值时所对应的极大图的结构.     

无向Kautz图的限制性连通度和限制性容错直径

证明直径为ｌ且最小和最大度分别为３和４的无向Ｋａｕｔｚ图具有限制性连通度４，且其限制性容错直径至多ｌ＋１４。     

简单无向图的同构判定问题的研究

图的同构判定问题是图论学科的基本问题之一,但是要判定两个图是否同构却是一件非常不简单的事情。本文旨在研究简单无向图的同构判定问题;并提出了一种新的简单无向图同构的必要条件。     

关于最小可行图的一个结果

给出了关于（Ｘ１，Ｘ２，Ｘ３，Ｘ４）的可行图Ｇ＝ＵＧｉ是最小可行图的充分必要条件：Ｇ是连通单圈图；或Ｊ∈（１，２，３，４），当∩Ｘｉ≠时，∩Ｇｉ是树，对任意整数ｎ给出了关于（Ｘ１，Ｘ２，…Ｘｎ）的最小可行图的若干性质，推广了已有的结果。     

基于Prim算法最小生成树优化的研究

通过Prim算法的研究寻找局部最优解的迭代过程,用布尔向量U和V-U表示集合中的边,根据权值的关系找到快速有效的算法来构造最小生成树.从理论上分析了算法的性质和时间复杂度.通过实例分析, 证明了该算法有效性并在现实生活中得到的广泛应用.     

赋权图中第二大特征值和最小特征值的界

运用ｎ阶非负矩阵Ｂ＝（ｂｉｊ）≥０的第二大特征值的界的结果,研究了ｎ阶赋权图Ｇ的邻接矩阵在行和相等时最大特征值的值和第二大特征值θ２（Ａ（Ｇ））以及最小的特征值θｎ（Ａ（Ｇ））的界．     

两个图算法的改进

Minty算法和Mayeda—Seshu算法是求无向连通图树清单的两个直观算法,它们都比矩阵算法节省计算时间。然而,它们仍然较复杂。本文分别对这两个算法提出了改进措施,大大降低了计算复杂性。改进后的算法既简单又直观易懂。对于Minty算法,我们提出了一个不完全算法;对Mayeda—Seshu算法,我们则避开了求基本割集这一复杂步骤。     

图的最小覆盖的逻辑算法

给出了利用命题逻辑公式的析取范式和主析取范式求图的全部极小覆盖和最小覆盖以及全部极小边覆盖和最小边覆盖的一般算法．     

图的最小最大分支

在图的顶点数和边数给定的一类图簇中，主要对图的最小最大连通分支的大小以及结构进行了研究，并且得到若干有意义的结果，这些结果为最小最大连通分支的应用提供了理论基础。     

基于DPCNN的无向赋权图的最小生成树的求解

 利用脉冲耦合神经网络(PCNN,Pulse Coupled Neural Network)的脉冲波并行传播特性,在其时延脉冲耦合神经网络(DPCNN,Delay PCNN)的基础上提出了一种求解无向赋权图最小生成树的新算法.算法针对最小生成树的权值总和最小且连通的性质,结合时延脉冲耦合神经网络脉冲波的并行传播,通过求解无向赋权图的最短路径并对其连通性进行判断,采用迭代的方法,成功地求解了无向赋权图的最小生成树.最后给出了仿真实验,证明了该方法的有效性,与传统算法比较有一定的优势.