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

《图的点可区别边染色算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第３１卷第３期计算机应用研究Ｖｏｌ．３１Ｎｏ．３２０１４年３月ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓＭａｒ．２０１４图的点可区别边染色算法研究李敬文，张云寒，陈志鹏，孙亮（兰州交通大学电子与信息工程学院，兰州７３００７０）摘要：针对一般图设计了一种新型的点可区别边染色算法。该算法把概率思想和图染色相结合，根据点可区别边染色的约束规则确立目标函数，利用交换规则逐步寻优，当目标函数的值满足要求时染色成功。给出详细算法步骤并进行了测试和分析，实验结果表明该算法可以求出满足猜想的点可区别边色数。关键词：经典算法；一般图；点可区别边染色；概率思想；约束规则；交换规

2、则中图分类号：ＴＰ３０１文献标志码：Ａ文章编号：１００１３６９５（２０１４）０３０７６００５ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１４．０３．０２９ＲｅｓｅａｒｃｈｏｆａｌｇｏｒｉｔｈｍｓｆｏｒｖｅｒｔｅｘｄｉｓｔｉｎｇｕｉｓｈｉｎｇｅｄｇｅｃｏｌｏｒｉｎｇｏｆｇｒａｐｈｓＬＩＪｉｎｇｗｅｎ，ＺＨＡＮＧＹｕｎｈａｎ，ＣＨＥＮＺｈｉｐｅｎｇ，ＳＵＮＬｉａｎｇ（ＳｃｈｏｏｌｏｆＥｌｅｃｔｒｏｎｉｃ＆ＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＬａｎｚｈｏｕＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ７３００７０，Ｃｈｉｎａ）Ａｂｓｔｒ

3、ａｃｔ：Ｔｈｉｓｐａｐｅｒｄｅｓｉｇｎｅｄａｎｅｗａｌｇｏｒｉｔｈｍｆｏｒｖｅｒｔｅｘｄｉｓｔｉｎｇｕｉｓｈｉｎｇｅｄｇｅｃｏｌｏｒｉｎｇｏｆｇｒａｐｈｓ．Ｔｈｉｓｎｅｗａｌｇｏｒｉｔｈｍｈａｄｃｏｍｂｉｎｅｄｐｒｏｂａｂｉｌｉｔｙｔｈｏｕｇｈｔａｎｄｇｒａｐｈｃｏｌｏｒｉｎｇ，ｅｓｔａｂｌｉｓｈｅｄｏｂｊｅｃｔｉｖｅｆｕｎｃｔｉｏｎａｃｃｏｒｄｉｎｇｔｏｔｈｅｃｏｎｓｔｒａｉｎｔｒｕｌｅｓｏｆｖｅｒｔｅｘｄｉｓｔｉｎｇｕｉｓｈｉｎｇｅｄｇｅｃｏｌｏｒｉｎｇ，ｕｓｅｄｅｘｃｈａｎｇｅｒｕｌｅｓｔｏｏｐｔｉｍｉｚｅｔｈｅｒｅｓｕｌｔｓｇｒａｄｕａｌｌｙ，ａｃｃｏｍｐｌｉｓ

4、ｈｅｄｃｏｌｏｒｉｎｇｗｈｅｎｔｈｅｖａｌｕｅｏｆｏｂｊｅｃｔｉｖｅｆｕｎｃｔｉｏｎｍｅｔｔｈｅｒｅｑｕｉｒｅｍｅｎｔｓ．Ｔｈｅｐａｐｅｒａｌｓｏｄｅｓｃｒｉｂｅｄｔｈｅａｌｇｏｒｉｔｈｍｓｔｅｐｓｉｎｄｅｔａｉｌ，ｔｅｓｔｅｄａｎｄａｎａｌｙｚｅｄｉｔ．Ａｎｄｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｅｄｇｅｃｈｒｏｍａｔｉｃｎｕｍｂｅｒｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｇｏｔｃｏｎｆｏｒｍｓｔｈｅｃｏｎｊｅｃｔｕｒｅｏｆｖｅｒｔｅｘｄｉｓｔｉｎｇｕｉｓｈｉｎｇｅｄｇｅｃｏｌｏｒｉｎｇｏｆｇｒａｐｈｓ．Ｋｅｙｗｏｒｄｓ：ｃｌａｓｓｉｃａｌａｌｇｏｒ

5、ｉｔｈｍｓ；ｇｅｎｅｒａｌｇｒａｐｈｓ；ｖｅｒｔｅｘｄｉｓｔｉｎｇｕｉｓｈｉｎｇｅｄｇｅｃｏｌｏｒｉｎｇ；ｐｒｏｂａｂｉｌｉｔｙｔｈｏｕｇｈｔ；ｃｏｎｓｔｒａｉｎｔｒｕｌｅｓ；ｅｘｃｈａｎｇｅｒｕｌｅｓ图的染色问题是现代图论中最主要的研究课题之一，无论简单连通图中任意两个相邻的边都分配到不同的颜色，同时保在理论上还是工程应用上均有良好的应用背景。１９９３年，证各个顶点的关联边构成的色集合不同。［１］Ｂｕｒｒｉｓ等人首先介绍并研究了点可区别边染色（或称强边染ｆ［８，９］定义１对于图Ｇ（Ｖ，Ｅ），ｆ：Ｅ（Ｇ）→｛１，２，…，ｋ｝满［２］色），Ｂａｌｉｓｔｅｒ等人作了更深入的研究

6、，得到了一些好的结果；足对任意相邻的边ｅ１和ｅ２，有ｆ（ｅ１）≠ｆ（ｅ２），则称ｆ是Ｇ的一２００２年和２００４年张忠辅教授先后提出了图的邻点可区别边个ｋ边染色，简记做ｋＰＥＣ。［３］［４］染色和图的邻点可区别全染色，该问题与强边染色的研［８，９］定义２对于图Ｇ（Ｖ，Ｅ），ｆ为Ｇ的一个ｋ边染色，点ｕ究具有同样的深度。本文在深入研究上述理论的基础上进而为Ｇ的任意一点，令Ｃ（ｕ）＝｛ｆ（ｕｖ）ｕｖ∈Ｅ（Ｇ）｝，若ｕ，ｖ∈提出新的强边染色算法。Ｖ（Ｇ）且ｕ≠ｖ有Ｃ（ｕ）≠Ｃ（ｖ），则称ｆ为Ｇ的ｋ点可区别边染随着信息技术的飞速发展，图染色问题不仅仅是纯数学理色（或称强边染色或ｏ

7、ｂｓ染色），简记为Ｇ的ｋＶＤＥＣ，称χ′ｓ论方面所要研究的课题，而且发展成为与其他领域交叉的一门学科。与此同时，一些经典的智能优化算法如遗传算法［５］、神（Ｇ）为Ｇ的点可区别边色数。其中χ′ｓ（Ｇ）＝ｍｉｎ｛ｋ｜Ｇ的所有［６］［７］ｋＶＤＥＣ｝。经网络算法、模拟退火算法等也被广泛地应用到解决图［１０，１１］的染色问题中来。应用结果表明，一方面这些经典智能优化算定义３设Ｇ（Ｖ，Ｅ）为一个简单图，ｎｉ为Ｖ（Ｇ）中度法仅仅应用于经典染色问题而不适用于可区别染色问题，另一为ｉ的个数，其中δ（Ｇ