排序方式: 共有5条查询结果,搜索用时 15 毫秒
1
1.
极大团问题是图论中一个经典的组合优化问题,也是一类NP完全问题,在国际上已有广泛的研究。作者在对其他现有极大团求解算法进行研究之后,设计了一种基于图着色思想的极大团求解算法。基本思想是通过不同的方式对随机图的相应补图进行顶点着色,寻找出所有顶点的极大独立集。而后返回到原图之中找出极大团,并且通过比较删减寻找到随机图的所有极大团。 相似文献
2.
3.
图G的邻点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色,同时要求相邻顶点的色集合也不相同,所用的最少颜色数称为图G的邻点可区别V-全色数.根据邻点可区别V-全染色的约束规则,设计了一种启发式的邻点可区别V-全染色算法.该算法借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功.给出了算法的详细描述以及算法分析和算法测试结果.实验结果表明,该算法有很好的执行效率,并可以得到随机图的邻点可区别V-全色数,验证了邻点可区别V-全染色猜想,并且算法的时间复杂度不超过O(n3). 相似文献
4.
在图 G 的一个正常全染色下,G 中任意一点 v 的色集合是指点 v 的色以及与 v 关联的全体边的色所构成的集合。图 G 的邻点可区别全染色就是图 G 的正常全染色且使相邻点的色集合不同,其所用最少颜色数称为图 G的邻点可区别全色数。设计了一种启发式的邻点可区别全染色算法,该算法根据邻点可区别全染色的约束规则,确定四个子目标函数和一个总目标函数,然后借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。实验结果表明,该算法可以得到图的邻点可区别全色数,并且算法的时间复杂度不超过 O(n3)。 相似文献
5.
针对随机图设计了一种启发式的邻点可区别I 全染色算法,能够求解随机图的邻点可区别I 全色数。该算法根据邻点可区别I 全染色条件,确立了3个子目标函数和1个总目标函数,利用交换规则逐步寻优,直到目标函数值满足要求时结束。给出了详细的算法设计步骤及流程,同时进行了测试和分析,测试结果表明,该算法可以得到随机图的邻点可区别I 全色数,并且算法的时间复杂度不超过O(n3)。 相似文献
1