启发式算法研究随机图的正常均匀全染色

"随机图的正常均匀全染色算法 (2015年)，尹波埠，李敬文，代素敏，胡腾云，兰州交通大学电子与信息工程学院" 这篇论文关注的是图论中的一个重要问题——随机图的正常均匀全染色算法。正常均匀全染色是图染色的一个变种，它涉及到如何将图的顶点和边分配颜色，使得每个顶点及其相邻边的颜色数量差异不超过1，同时保证所有顶点的色差也保持在一定范围内。在实际应用中，这可以对应于资源分配、网络规划等问题。 目前，对于图的均匀全染色的研究主要集中在特殊类型的图，如完全图和正则图，而对于一般简单连通图的正常均匀全染色算法，尚无成熟的方法。为了解决这个问题，论文提出了一种新的启发式智能算法。该算法基于正常均匀全染色的四个约束规则：点约束、边约束、点边约束和均匀约束。算法的核心步骤包括： 1. **定义目标函数**：算法首先设定四个子目标函数，以及一个综合这些子目标的总目标函数。这些函数用来衡量染色是否满足正常均匀全染色的条件。 2. **迭代交换**：在每个子目标函数内部，通过染色矩阵和色补集合矩阵进行逐步迭代交换。染色矩阵记录每个顶点的颜色，而色补集合矩阵则表示哪些颜色尚未被使用。通过不断调整，直到子目标函数的值降为0，表示该子目标的染色完成。 3. **优化过程**：当所有子目标函数的值都达到0时，总目标函数值也为0，表明染色成功，即实现了正常均匀全染色。 实验结果显示，该算法能够处理8个顶点以内的所有简单连通图，并能计算出它们的均匀全色数。此外，论文还进一步验证了对于任意正整数k，当3 ≤ k ≤ n时（n为图的顶点数），存在一种随机图G，它可以有ι个均匀全染色。算法还在20到400个顶点的范围内选取了72个图进行均匀全染色，通过染色结果绘制了点数与边密度之间的关系图，进一步证明了算法的有效性。 关键词涵盖了“图”、“正常均匀全染色”和“均匀全色数”，表明这是图论领域内关于染色问题的一个技术性研究，具有实际应用价值，特别是在图的优化和调度问题中。该算法的提出，为解决一般简单连通图的正常均匀全染色问题提供了新的思路和工具。