完全图的点可区别强全染色算法

根据图的点可区别全染色的定义,结合完全图的对称性,提出一种新的点可区别强全染色算法。该算法将需要填充的颜色分为超色数和正常色数2个部分,在得到染色数量和染色次数的前提下,对超色数进行染色以增强算法收敛性。实验结果表明,该算法具有较低的时间复杂度。     

完全图的点可区别全染色算法

设f是图G的一个正常的k-全染色,若G中任意两点的色集不同,则称f为G的k-点可区别全染色,简记为k-VDTC of G,,并称最小的k为G的点可区别全色数。该文针对完全图的点可区别全染色的特点提出了分类顺次着色算法,该算法首先按照一定的规则对元素进行分类然后对元素进行顺次着色,同时给出关联锁表,根据关联锁表判断是否得到问题的解。实验结果表明:该算法有效地解决了完全图的点可区别全染色问题。     

随机图的点可区别V-全染色算法

图[G]的点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色,同时要求所有顶点的色集合也不相同,所用的最少颜色数称为图[G]的点可区别V-全色数。根据点可区别V-全染色的约束规则,设计了一种启发式的点可区别V-全染色算法,该算法借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。给出了算法的详细描述、算法分析和算法测试结果,对给定点数的图进行了点可区别V-全染色猜想的验证。实验结果表明,该算法有很好的执行效率并可以得到给定图的点可区别V-全色数,并且算法的时间复杂度不超过[O(n3)]。     

随机图的点可区别全染色算法

点可区别全染色(VDTC)是指在满足正常全染色的基础上,还要使得图中由顶点颜色和其关联边颜色构成的顶点色集合也不同,所使用的最少颜色数称为点可区别全色数.提出了一种针对随机图的点可区别全染色算法,算法的基本思想是对图G中的边随机地进行预染色,查找存在边染色不正常的冲突集,然后根据规则逐步迭代,直至使目标函数的值满足要求,此时说明染色成功.实验结果表明,算法能够有效地求得给定点数随机图的点可区别全色数,算法时间复杂度不超过O(n3).     

随机图的邻点可区别VI-均匀全染色算法

邻点可区别[VI]-均匀全染色是指图中任意两条相邻边分配不同的颜色,且任意两个色类（点或边）的颜色个数最大相差为1,同时确保相邻顶点的色集合不同,其所用的最少颜色数称为图的邻点可区别[VI]-均匀全色数。提出了一种针对随机图的邻点可区别[VI]-均匀全染色算法,该算法依据染色条件设计了三个子目标函数和一个总目标函数,并依据交换规则逐步迭代寻优,直至染色结果满足总目标函数的要求。同时给出了详细的算法执行步骤,并进行了大量的测试和分析,实验结果表明,该算法可以高效地求出给定顶点数的图的最小邻点可区别[VI]-均匀全色数。     

梯图的点可区别全染色（n≡5（mod8））

一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素及其本身所构成的色集合不同。其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法：三角排序。利用该排序的结果证明了当n≡5（mod8）和C4n-1/2＋2〈m≤C4n/2＋2时,梯图Lm≌Pm×P2的点可区别全色数为n。     

梯图的点可区别全染色（n≡4（mod8））

一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素及其本身所构成的色集合不同,其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法：三角排序。利用该排序的结果证明了当n≡4（mod8）和C4n-1/2＋2〈m≤C4n/2＋2时,梯图Lm■Pm×P2的点可区别全色数为n。     

梯图的点可区别全染色（n=7（mod8））

一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素所构成的色集合不同,其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法——三角排序,利用该排序的结果证明了当n=7（mod8）且Cn-1^4/2＋2〈m≤Cn ^4/2＋2时,梯图Lm≌Pm×P2的点可区别全色数为n。     

多目标优化的图的邻点可区别均匀V-全染色算法

图的邻点可区别均匀V-全染色（AVDEVTC）是指在满足邻点可区别V-全染色的基础上,还要保证每种颜色的使用次数相差不超过1,把完成AVDEVTC所用的最少颜色称为图的邻点可区别均匀V-全色数（AVDEVTCN）。针对图的AVDEVTC问题,提出了一种基于多目标优化的染色算法。设计了一个总目标函数和四个子目标函数,在染色矩阵上通过每个点的颜色集合的迭代交换操作,使得每个子目标函数都达到最优,进而满足总目标函数的要求,完成染色。经过理论分析和实验对比表明,8个顶点以内的所有简单连通图都存在AVDEVTC,且图的AVDEVTCN介于最大度加1与最大度加2之间。实验结果表明,该染色算法能够在较短的时间内正确地计算出1000个顶点以内的图的AVDEVTCN。     

随机图的正常均匀全染色算法

目前对图的均匀全染色的研究仅限于一些如完全图、正则图等特殊图,还没有发现用于研究一般简单连通图的正常均匀全染色的算法。为了研究一般图的正常均匀全染色,根据正常均匀全染色的点约束、边约束、点边约束和均匀约束四个约束规则,设计了一种新的启发式智能算法。首先,该算法确定四个子目标函数和一个总目标函数;然后,在每个子目标函数内借助染色矩阵及色补集合矩阵逐步迭代交换,直到子目标函数值为0时,子目标染色完成;最后,当每个子目标函数值都为0时,总目标函数值为0,染色成功。实验结果表明,该算法可以生成8个点以内的所有简单连通图,并能对每个生成图进行正常均匀全染色,得到其均匀全色数,且验证得对任意的正整数k,当3≤ k≤ 9时,随机图G都有k-均匀全染色。同时在20到400个点之间选取了72个图,用所提算法对其进行均匀全染色,并依据染色结果绘制了它们的点数-边密度-所需色数关系图。     

解决图着色问题的一种新禁忌搜索算法

为了解决典型的组合优化问题——图顶点着色问题,结合增强SEQ算法和禁忌搜索算法的优点与缺点,提出一种基于增强SEQ的新禁忌搜索算法(SEQTS)。该算法利用增强SEQ算法较强的构造较优解的能力来为禁忌搜索算法构造多个较优初始解,然后进行多初始解禁忌搜索以找到全局最优解。计算机实验的结果表明该算法(SEQTS)有较好的寻优能力,增强了该算法的有效性。     

一种求解图着色问题的蚁群遗传算法

遗传算法在图着色问题上已经得到广泛的应用,但对于顶点数较多的图,使用此类算法进行着色的结果就显得不够理想,运行效率也不够高。由于遗传算法具有全局收敛性,蚁群算法具有局部收敛性,因此,将遗传算法和蚁群搜索算法融合,提出一种新的解决图着色问题的蚁群遗传算法。该算法先利用蚁群算法快速地为遗传算法搜索到较好的初始解,然后利用遗传算法进一步遗传优化,同时在优化解上加强信息素强度,并反馈给蚁群搜索。实验结果表明,改进的算法在解决顶点数较大的图着色问题上有明显的优势。     

求解图着色问题的进化稳定策略蚁群算法

针对图着色问题,在传统的启发式蚁群算法的基础上提出一种进化稳定策略蚁群算法。进化稳定策略蚁群算法针对蚁群算法的隐含并行性,利用变换因子自适应地更新信息素,动态自适应地调节启发式因子的作用参数,增强算法的搜索能力,加快算法的收敛速度,同时避免了传统蚁群算法容易陷入局部最优的问题。通过给地图着色的仿真实验结果表示,该方法对图着色问题的求解是可行、有效的,通过大量实验表明算法在求解质量上优于启发式蚁群算法。     

用"递增"算法求完全图的所有哈密顿回路

本文给出求解完全图的所有哈密顿回路“递增”算法。即从Kn的哈密顿回路求Kn 1的哈密顿回路。任意给出一个图,可以根据结点数先求其完全图的所有哈密顿回路,在所有哈密顿回路中去掉那些在实际图中有不存在边的哈密顿回路,最后得到任意图的所有哈密顿回路,如果全部去掉,则该图不是哈密顿图。     

一种新的图聚类算法研究

图聚类是基于各种标准如结点标号、边标号、公共子图等条件将图数据集实例划分不同类集群,这将对结构化图空间及增强对图数据的理解有着重要作用。针对此问题提出基于结构化的图聚类算法。与目前有关的算法相比,该算法不产生新图或原图分解成零碎子图,也不依赖计算最大共同子图的相关操作。实验结果表明,这种方法在现实分子图数据集上对结构聚类可行、有效。     

基于协同进化PSO的分类器学习算法

微粒群算法是一种简单、随机的进化群体算法,能够有效地解决数学性质比较复杂的优化问题。神经网络分类器能够解决复杂的非线性空间上分类的问题,它的训练学习算法要求更简单有效。文中将微粒群优化算法应用于神经网络分类器的学习,并加入协同进化机制以增强其性能。实例表明协同PSO算法的优越性。     

图的一种双链式存储结构

本文提出了图的一种双链式存储结构，比以往的图的链式存储结构有更好的灵活性，并在图的各种算法的实现显示了较好的时空复杂性，具有其它存储结构所不具备的各种优点。     

直线与Bzier曲面求交的分割迭代综合法

本文所介绍的适合光线跟踪算法的直线与B(?)zier曲面求交的方法,采用了空间一般位置的圆柱和长方体作为曲面包围盒,并综合利用了分割法的稳定性和牛顿迭代法的效率,从而加快了用光线跟踪技术生成Bzier曲面的真实感图形的速度。     

最小谣传图的一个有效算法

谣传是信息网络中结点之间的一种常见的、重要的信息交换方式，在谣传过程中，每一个结点都得到ｋ个结点的信息，这个概念在计算机网络及其它信息、通信网络的设计中有着重要的意义，本文把“权”的概念引入到谣传问题中来，从而定义了最小谣传图，并给出了最小谣传图的一个好算法。     

一种改进的Ford-Fulkenson算法在选题系统中的应用研究

介绍了经典的二分图的匹配算法Ford-Fulkenson,并作了改进,在毕业设计选题系统中进行了应用,能在学生的志愿和老师的要求之间进行自动匹配,使负责选题的工作人员能从冗杂的课题需求中尽量准确的达成匹配,从而提高院校的教学质量.