在有向图中寻找哈密顿回路的快速回溯法

本文提出了回路段的新概念。并在此基础上给出了寻找有向图中所有哈密顿回路 的快速回溯法ＱＢ．算法ＱＢ通过合并回路段来生成哈密顿回路，它的回溯树上各顶 点的期望分枝数ｃｑ等于各层当前图可用顶点的最小出度的平均值。对于常规的简单 回溯法ＳＢ，回溯树上各顶点的期望分枝数ｃｓ等于各层当前可用顶点的平均出度的 平均值。显然，ｃｑ总是小于ｃｓ．算法ＱＢ的期望时间为Ｏ（ｎ２（ｃｑ）ｎ），而算法ＳＢ期 望时间为Ｏ（ｎ（ｃｓ）ｎ），ｎ为图中顶点数。     

生成有向图中全部简单回路的一种新算法

提出了生成有向图中全部简单回路的一种新算法.算法的主要思想是对图中顶点进行缩减,在缩减过程中巧妙地利用字符串标记保存图中原有信息,不断减少图中顶点的数量,最终将图缩为一点,逐步得到全部简单回路.这种缩减过程隐藏在矩阵运算中,在运算中不断简化矩阵,从而降低了运算复杂度,提高运算效率.此算法生成的回路中不包含重复的回路,算法结构清晰,易转化为计算机程序.文中给出了算法的详细证明和实例应用.     

关于竞赛图的一些结果

§1 有序定向竞赛图中的哈密尔顿回路令U_1,…,U为竞赛图T中的顶点。令d_(?)~ 为U_i的出度。如果每个U_i恰好指向U_(i 1),…,U_(i d~ ),(modn),其余的顶点指向U_i,则T被称为有序定向的。 Alspach等人曾在这类图中的回路计数问题上作了一些工作。本文将讨论的是这类图中哈密尔顿回路的计数问题。Thomassen曾提出这个问题:在同样的出度序列条件下,那一     

一种大规模稀疏中国邮递员问题快速求解方法

针对现有中国邮递员问题求解方法在大规模稀疏路网图上求解效率的瓶颈,提出一种在可接受时间范围内求得可行解的基于蚁群优化的快速求解方法.该方法针对Euler回路求解的奇偶点图上作业法的第二阶段,采用蚁群算法进行求解,同时根据大规模稀疏路网图的特性基于密度峰值聚类算法对方法进行改进：首先在蚁群算法求解前对大规模稀疏路网图进行聚类分割;其次根据邻近节点覆盖率对分割后的节点群进行合并;最后通过改变部分节点所属聚类使各节点群内部节点个数均为偶数.实验结果表明：在奇偶点图上作业法所能支持的节点规模下,该方法可求得与确定性算法相同的最优解,并在运算时间上达到约10倍的效率优化;且该方法在大规模稀疏路网图下可有效提高计算效率,并在可控时间范围内得到优化的可行解,针对5 000个节点规模的路网图最快可在60 s内完成求解.     

基于图着色的极大团求解算法

极大团问题是图论中一个经典的组合优化问题,也是一类NP完全问题,在国际上已有广泛的研究。作者在对其他现有极大团求解算法进行研究之后,设计了一种基于图着色思想的极大团求解算法。基本思想是通过不同的方式对随机图的相应补图进行顶点着色,寻找出所有顶点的极大独立集。而后返回到原图之中找出极大团,并且通过比较删减寻找到随机图的所有极大团。     

用分层关联方法求简单图中所有Hamilton回路的算法

研究简单图中所有的Ham ilton回路,不但可以判断简单图是否Ham ilton图,并且还可以得到简单图的所有的Ham ilton回路。首先在简单图中建立了初级通路的关联关系,并对初级通路的关联关系进行了分层,在此基础上,设计了求简单图中所有Ham ilton回路的算法。该算法利用简单图中长度为x的初级通路及长度为x的初级通路的分层关联关系逐步求长度为x 1的初级通路及长度为x 1的初级通路的分层关联关系的方法,求得简单图的所有Ham ilton回路。通过理论证明,该算法与已有的求简单图的所有Ham ilton回路的算法相比,原有的求简单图的所有Ham ilton回路算法中大量的重复计算被避免,从而提高了算法的效率。     

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

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

基于可行路径最短路径的一种算法

研究无向连通图最短路径的一种算法.此算法比Dijkstra算法和Floyd算法更具有实用性,能够给出图中任意两个顶点间的最短路径序列、任意两个顶点间的最短路径及任意两点间的所有可行路径的长度.     

应用思维进化计算求解顶点着色问题

应用思维进化计算求解顶点着色问题,给出求解给定图的色数、最小着色的算法。介绍了顶点着色问题的编码与解码方法、特征、信息矩阵的概念,从而应用思维进化计算的趋同和异化求解该问题。实验结果表明该算法是求解顶点着色问题的一种新的有效算法。     

LDPC码的回路分析

LDPC码的短回路极大地影响了其性能,用图的理论来描述LDPC码,从而可以给出所有的回路,以及回路所经过的节点和长度。这种算法非常适合计算机进行搜索。     

基于半定规划的多约束图划分问题

提出一种递归的二分算法,用于求解带顶点权重约束的图划分问题.首先利用内点法求解不加顶点权重约束的半定规划松弛模型,然后利用超平面舍入算法得到满足顶点权重约束的初始可行解,再进一步设计启发式算法对初始可行划分进行局部改进,以得到更优的划分结果.实验结果表明,所设计的算法可在较短时间内得到多约束图划分问题的高质量解.     

唯一有向Euler图的构造

<正> 如果一个有向Euler图的有向Euler环游是唯一的,我们就称之为唯一有向Euler图。本文直接由文 [1] 给出的唯一有向Euler图的充要条件,来证明关于唯一有向Euler图的构造定理,即定理设D是有向Eulcr图,则当且仅当D是由若干个有向回路在入度和出度都是1的顶点上逐个粘接而成时,D是唯一有向Euler图。     

分层算法求解竞赛图上的最小弱顶点覆盖

竞赛图上的弱顶点覆盖问题是一个NP困难问题,本文先定义了竞赛图上的势加权函数,然后利用分层技术给出了一个求解竞赛图最小弱顶点覆盖问题的近似算法,并证明了此近似算法的近似度为3     

非线性化学胞映射数值解的多线程并发运行实现技术

胞映射方法是一种在离散化相空间中求解、描述和揭示复杂非线性化学动力学系统演化过程、吸引域结构、吸引子形态及其内在规律的有效工具。利用胞映射算法技术 ,在双CPU计算机平台上 ,结合多线程并行计算技术实现了复杂非线性系统演化过程的高效运算 ,较好地解决了大规模运算量与高效计算之间的矛盾 ,以及复杂系统演化过程的计算可视化问题     

求解最优巡回路问题算法

为找一种简便、实用的求解最优巡回路的方法,在给定2个基本假设的前提下,在局部上运用D ijkstra算法求出两顶点间的最短旅行费,再求出各顶点间的最短旅行费,得到各节点间的有向图距离矩阵。在全局上运用匈牙利法求出全局最优巡回路,并对出现的局部回路问题进行了讨论,即建立了用“四阶段法”求解无数量限制的最优巡回路问题的算法。用无向图和有向图2个实例进行了计算,验证了求解无数量限制的最优巡回路问题的算法。     

Pythagorean模糊信息系统属性约简的图论方法

信息系统中,属性约简是知识发现问题的一个研究热点,能达到发掘并简化知识的目的。目前已有很多利用辨识矩阵来进行属性约简的研究,但是当数据维数较大时,算法复杂度往往很大。利用加权欧几里得距离来定义二元关系及辨识矩阵,利用信息系统的约简与生成图的最小顶点覆盖等价的关系,将辨识矩阵求解约简的问题转化为求解生成图中最小顶点覆盖的问题,并给出了Pythagorean模糊信息系统中属性约简的算法;在此基础上,利用基于加权欧几里得距离的相似关系,定义了Pythagorean模糊决策信息系统的辨识矩阵,并给出了用最小顶点覆盖的方法求约简算法,最后利用实例验证了算法的有效性。     

非线性化学胞映射数值解的多线程并发运行实现技术

胞映射方法是一种在离散化相空间中求解、描述和揭示复杂非线性化学动力学系统演化过程、吸引域结构、吸引子形态及其内在规律的有效工具。利用胞映射算法技术，在双CPU计算机平台上，结合多线程并行计算技术实现了复杂非线性系统演化过程的高效运算，较好地解决了大规模运算量与高效计算之间矛盾，以及复杂系统演化过程的计算可视化问题。     

中国邮路问题的0-1规划解法

在用“奇偶点图上作业法”求解“中国邮路问题”时,需检查图中的每一个回路.当图中回路较多时,检查不便且易出错.针对此,本文建立了求解“中国邮路问题”的0-1规划模型,并给出了算例。     

基于遗传和启发式算法的混合顶点着色算法

图的着色问题是一种典型的NP-完全问题.提出了基于遗传算法和启发式算法的新型混合顶点着色算法,该算法在实现过程中涉及到染色体的编码方法、适应度函数的设计以及遗传算子的选择等.实验仿真结果表明此算法改善了求解的时间复杂度,可以获得问题高质量的解.     

一类特殊图的顶点染色数

如果图G含有的所有最大团存在公共顶点,且公共顶点的个数为κ,就称此图为第κ类图。据此,本文给出了研究图的顶点染色的一种新方法,并以此研究了一类特殊图的顶点染色及一些图的顶点染色数。