任意无向图的最小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算法,我们则避开了求基本割集这一复杂步骤。     

单圈图的最小广义Zagreb指标

设G是单圈图,dv表示顶点v的度数.讨论了单圈图G的几个拓扑指标:mG=vVGdvm,mG=vVGdvm,m1G=vVGdvm1,这里m是不小于2的正整数,刻画了单圈图关于3个拓扑指标的最小值.     

基于Global optimization寻找无向完全图的最小生成树

将Global optimization思想引入到寻找无向完全图最小生成树的问题中,提出了Global optimization算法。与Kruskal算法和Prim算法相比之下,此算法避免了求解过程中对生成树中是否出现回路的判断,并在一定程度上降低了时间复杂度。     

任意开关电容网络的Coates图分析

本文提出了一种分析开关电容网络的新方法,该分析方法使得开关电容网络(SCN)在z域等效电路所需元件减少;利用z域的电压控制电荷源(VCQS),进而应用Coates图及增益公式,即可十分方便地求出其传递函数,该法适用于任意的SCN等效电路,文中对两个实例进行了分析,事实证明该法简便、有效、速度快。     

具有最小Wiener指数的双圈图

一个图G的Wiener指数W(G)定义为G中所有点对的距离和,双圈图是一个具有n个点和n+1条边的连通图,我们根据两个圈的相对位置关系把双圈图分成三类,分别在这三类中给出了最小的Wiener指数,然后通过比较三类极值的大小得到了双圈图中具有最小Wiener指数的图。