一种应用于完全图的点可区别强全染色新算法

设f是简单图G的一个正常k-全染色,若G中任意两点所关联的点及其关联边的颜色所构成的集合互不相同,则称f为G的K-点可区别强全染色,k中的最小值为G的点可区别强全色数。针对完全图的点可区别强全染色的特点,提出一种新算法。该算法把需要填充的颜色分为两部分:超色数和正常色数,在分别得到其染色数量和染色次数的前提下先对超色数进行染色以增强算法的收敛性。实验结果表明,该算法能有效地解决完全图的点可区别强全染色问题。     

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

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

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

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

梯图的点可区别全染色（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。     

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

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

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

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

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

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

路图的Smarandachely全染色算法*

设f是简单图G的一个正常的k-全染色,若G中任意两点的点及其关联边的颜色构成的集合互不包含,则称f为G的k-Smarandachely全染色,这样的k中最小者称为G的Smarandachely全色数。针对路图的Smarandachely全染色问题,提出了一种新算法。算法采用三元组编码方式将问题进行转化,按照给定规则生成三元组队列,并对该队列内部排序进行变换调整。同时,给出两个判断函数,根据函数的值判断是否得到问题的解。实验结果表明,该算法可以有效地解决路图的Smarandachely全染色问题。     

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

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

图的点可区别边染色算法研究

针对一般图设计了一种新型的点可区别边染色算法。该算法把概率思想和图染色相结合, 根据点可区别边染色的约束规则确立目标函数, 利用交换规则逐步寻优, 当目标函数的值满足要求时染色成功。给出详细算法步骤并进行了测试和分析, 实验结果表明该算法可以求出满足猜想的点可区别边色数。     

图的Smarandachely邻点可区别边染色算法

为解决图的Smarandachely邻点可区别边染色问题,提出一种基于多目标优化的染色算法。针对每个子问题分别设置子目标函数向量和决策空间,在颜色迭代、顺序交换和强制交换中,子目标逐渐得到最优解,最终使总目标函数符合图的Smarandachely邻点可区别边染色要求。实验结果表明,在1 000个顶点内该算法能够正确地得到随机图的Smarandachely邻点可区别边色数。     

若干多重Mycielski图的邻点可区别I-全色数

根据路和星、圈的多重Mycielski图的结构性质,用穷染递推的方法,讨论了图Mn(Cm)和Mn(Pm),以及Mn(Sm)的邻点可区别I-全染色,得到了图Mn(Sm)和Mn(Pm)的邻点可区别I-全色数等于它们的最大度,图Mn(Cm)的邻点可区别I-全色数在m=4,5时等于它的最大度加1,其余情况等于它的最大度,即分别给出图Mn(Sm)和Mn(Cm)、Mn(Pm)一种染色方案.     

若干多重Mycielski图的邻点可区别Ⅰ-全色数

根据路和星、圈的多重Mycielski图的结构性质,用穷染递推的方法,讨论了图Mn(Cm)和Mn(Pm),以及Mn(Sm)的邻点可区别I-全染色,得到了图Mn(Sm)和Mn(Pm)的邻点可区别I-全色数等于它们的最大度,图Mn(Cm)的邻点可区别I-全色数在m=4,5时等于它的最大度加1,其余情况等于它的最大度,即分别给出图Mn(Sm)和Mn(Cm)、Mn(Pm)一种染色方案。     

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

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

基于Grover算法的图着色问题求解

Grover量子搜索算法是针对非结构化搜索问题设计的著名量子算法，可用于解决图着色、最短路径排序等问题，也可以有效破译密码系统。图着色问题是最著名的NP-完全问题之一，文中首先将图着色问题转化为数学上的无向图；然后采用布尔表达式将其转换为布尔可满足性问题，介绍了量子线路图解决布尔表达式的步骤原理以及图着色问题向布尔可满足性问题的转换过程；最后在IBMQ云平台上，对三节点的2-着色问题以及4-着色问题进行模拟仿真。实验结果验证了使用Grover算法求解图着色问题的可行性，在搜索空间为8的2-着色问题和搜索空间为64的4-着色问题中，分别以近82%和97%的成功概率搜索到目标项。文中使用Grover算法解决了4-着色问题，拓展了该算法在此问题领域上的实验规模，且改进了现有实验的量子线路，使量子位成本更低，结果的成功率更高，展示了Grover算法在大型搜索问题中显著的加速效果。     

Rivas-Eddy RNA二级结构图书嵌入分类的实现方法

书嵌入数是对图进行分类的一个拓扑标准,通常来说,计算一个图的书嵌入数及给出一种嵌入实例都是NP完全问题。针对Rivas-Eddy（R&E）类中RNA分子的二级结构图,从二级结构图的语法出发,通过其交叉关系图的点着色,构造性地得到了RNA分子二级结构图书嵌入的具体实现方法,完成了对RNA分子二级结构的书嵌入分类。该方法具有多项式时间复杂性,为求解NP完全问题提供了有益的参考。     

最近邻分类的多代表点学习算法

经典的k-最近邻算法存在参数k难以确定和分类效率低的缺点.基于模型的kNN算法使用代表点集合构造训练样本的分类模型,克服上述缺点,但需要较高的计算时间代价.文中提出一种高效的多代表点学习算法,用于最近邻分类.运用结构风险最小化理论对影响分类模型期望风险的因素进行分析.在此基础上,使用无监督的局部聚类算法学习优化的代表点集合.在实际应用数据集上的实验结果表明,该算法可对复杂类别结构数据进行有效分类,并大幅度提高分类效率.     

一种基于链暗示技术的Min-CVCB问题的精确算法

随着VLSI(超大规模集成电路)技术的发展,关于可重构阵列二分图的受约束最小点覆盖(Min-CVCB)问题受到了很多文献的关注.作为点覆盖问题的子问题,该问题已被证明是NP-完全问题.人们利用核心化和分支即使给出了时间复杂度为O((ku k1)|G| 1.26ku k1)的目前最好算法,然而仍不能满足实际工程的需要.通过进一步深入分析二分图的结构,对含有权值大于或等于3的块的连通子图分析其可能连接情况后充分利用"链暗示"技术和分枝搜索技术来建立起新的搜索递推关系;对于分枝后的块提出了一种动态规划算法,其可在多项式时间内完成处理.整个参数算法的运行时间为O((ku k1)|G| 1.1892ku k1),极大地改进了目前的最好结果.     

一种室内清扫机器人路径规划算法

清扫机器人作为服务机器人领域中的一个新产品已成为人们家庭当中的重要一员,全覆盖路径规划问题是其重要技术之一。提出一种新的路径规划算法,该算法对室内环境进行栅格模型建模,生成一个无向完全图G,对图 G 采用深度优先搜索和广度优先搜索,并应用拓扑排序动态更新图 G,生成最短全覆盖规划路径,最后用生成树来验证该算法的有效性和可行性。