共查询到18条相似文献,搜索用时 46 毫秒
1.
为研究以最少边集扩充一个任意无向图为R点连通图这一尚未解决的优化问题,通过将无向图点连通问题转化为有向图边连通问题,采用增广扩充的方法,提出了一个复杂度为O(|V|^5)的算法.利用该算法可最优地将给定无向图中任意2点达到所要求的点连通度.它发展了K点连通最优扩充的研究,从而使图的点连通扩充的研究在应用于网络设计的可靠性设计方面更具有实际意义. 相似文献
2.
加权图的连通扩充问题已被证明是NP完全问题,作者提出一种改进遗传算法来解决无向加权图的k点连通扩充问题,通过改进遗传算法中的交叉和变异操作有效地改善了群体的效果,有助于搜索解空间中新的区域,能以较大概率搜索到全局最优,仿真结果表明,该算法在原来简单遗传算法上做了进一步改善,为解决加权图的扩充问题提供了新的方法。 相似文献
3.
任意无向图的最小R边连通扩充 总被引:2,自引:2,他引:2
研究了以最少边集扩充一个任意无向图为R边连通图这一优化问题。给出了一个复杂度为O(|V|~5)的算法。利用该算法可最优地将所研究图形中任意两点达到所要求的边连通度。它发展了K边连通最优扩充的研究,从而使图的边连通扩充的研究在应用于网络结线的可靠性设计方面更具有实际意义。 相似文献
4.
5.
为了对网络的可靠性寻求较好的近似算法,研究了任意无向不加权图情况下的极小K 点连通扩充算法;在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理,并加以证明.最终推出了任意无向加权图K点连通最小扩充的逐次改善算法,应用该算法作了大量例题,得到比较满意的效果.为解决任意无向加权图最小扩充问题给出了一种新途径. 相似文献
6.
设k是正整数,D是极小k边连通简单有向图.Mader猜测(见Combinatorics,Paul Erd6s is Eighty (V01.2),Budapest,1996)D中至少有k 1个出度为k的点.在k=1时,Mader已证明成立.考虑志≥2,运用Edmonds等人在研究组合优化问题中引入的对无交叉组的树表示,证明了在志≥2时,D中至少有3个出度为k的点. 相似文献
7.
郭欢 《重庆工商大学学报(自然科学版)》2012,29(9):14-17
一个图的无符号拉普拉斯最小特征值在某个图类中的所有图中达到最大时常称为极大图;通过利用特征向量方程研究特征值的方法,对只含有一个割点的连通图的无符号拉普拉斯最小特征值进行了研究,且得到了最小特征值的值,从而得到了只含有一个割点的具有相同阶数的所有的连通图中最小特征值的极大值,并且刻画了最小特征值取到极大值时所对应的极大图的结构. 相似文献
8.
9.
10.
可移动社区依托于移动自组网,其特征决定了社区网络的临时性通信范围的有限性以及网络拓扑结构的高度动态性.利用图论的理论和方法,提出了一种基于k边连通最小生成子图的网络拓扑管理算法,算法以能量消耗等因素衡量链路的代价值,通过减少高代价的冗余链路来优化拓扑结构,能够较好地适应可移动社区拓扑管理的需求.实验结果表明:该拓扑管理算法有效地减少了网络整体能量损耗,延长了网络的生命周期. 相似文献
11.
12.
13.
14.
生成无向图全部树的一种新算法 总被引:1,自引:1,他引:1
房大中 《天津大学学报(自然科学与工程技术版)》1988,(4)
本文提出一种生成无向图G全部树的算法。它应用图的邻接下三角矩阵L$为图的数据结构,通过L$矩阵的一系列变换而完成。算法的时间复杂度为o(K(n-1)),空间复杂度是O((n-1)~2),式中n和K分别表示G的结点数和计算林树梢个数。此外文章还报道了一个图论性质的猜测,文章最后讨论了选择结点序列加速算法过程的方法。 相似文献
15.
作者针对传统k-means初始点的选择提出基于最小距离的优化算法。首先构造数据点集的带权无向图,更新数据点间的最小距离,然后利用最小距离获取数据点的密度函数,通过数据点的密度获取初始聚类中心,最后根据带权无向图中的路径长度获取邻近数据点形成初始聚类,对初始聚类内的数据点平均得到该类簇的聚类中心。实验结果表明,在相同的条件下所提算法在聚类效果上优于传统的k-means算法。 相似文献
16.
关联规则是数据挖掘研究领域的重要内容之一,在无向项集图的罐础上,结合RSAA算法,提出了一种新的挖掘关联规则的算法,用以发现数据库中有价值的稀有数据.通过将该算法与RSAA算法的分析比较,证明了其在获得频繁项集的效率上具有更好的性能。 相似文献
17.
介绍了模拟退火算法的基本思想 ,并应用它成功地解决了通讯网络极小生成树的优化计算问题。计算结果表明 :该算法能有效地跳出局部极小值并快速地收敛于全局最优值。说明模拟退火算法是一个通用的、具有概率爬山的、强有力的组合优化算法 相似文献
18.
本文在工艺尺寸链树形图的概念及其建立过程的基础上,提出了利用树形图进行工艺尺寸计算、公差确定、余量确定及校核等整体解算方法。本方法可方便地用于计算机程序实现。 相似文献