论文部分内容阅读
随着信息科学与网络技术的快速发展,图论因其直观的图形性和严密的逻辑性,在广大的专家学者中受到了越来越多的关注和研究。许多问题都可以找到与之相匹配的图的模型,例如大规模信息通讯、社交网络、大数据采集及分析、物联网等问题,都有着复杂的网络化、结构化的特点。而图论具有把复杂结构问题抽象转化成以顶点和边表示的清晰结构的特性,以图为工具成为解决这些领域问题的新型且有效的方案,进而抽象为图染色的方法予以解决。因此,对图染色问题的研究与创新是非常有意义的。图的染色问题属于NP完全问题,一些经典的智能算法如遗传算法、粒子群算法、神经网络算法等被用来解决图的染色问题时,仅能解决如正常点染色和正常边染色等单约束条件染色问题,而对于全染色和可区别染色等多约束条件染色问题则到目前为止也没有好的成果发表。本文首先设计并实现了三个解决多约束条件染色问题的染色算法,然后结合已公开发表的部分可区别图染色算法,设计并实现了图染色软件系统（GCSS）。该系统可以为图论研究的学者、爱好者以及应用图染色技术解决现实问题的科研工作者提供一个良好的研究平台。在该系统中,用户只需选择染色方法、图的点数、边密度等参数,就能够正确得到有限点数（100点）以内所有简单连通图的5种可区别染色结果。这些结果为图染色学者和爱好者提供了基础研究数据,也为科研工作者打算采用图论技术解决计算机通信、排课表、任务调度、仓储分配等组合优化问题提供帮助。本文的具体工作如下:（1）介绍了Kp\E(k1,m)图的点可区别边色数猜想,针对该猜想设计并实现了图的点可区别边色数猜想证明算法。详细描述了算法步骤,并对算法的正确性进行了测试,同时对2000个顶点以内的所有Kp\E(k1,m)图的点可区别边色数进行测试,测试结果表明该猜想是成立的。（2）设计并实现了随机图的点可区别均匀全染色算法。算法的整体思路是根据约束条件将染色问题分解成多个子目标问题,当所有子目标问题都被成功解决后,即代表该染色成功,算法结束。文中给出了算法的详细流程及测试案例,并分析了算法的正确性和时间复杂度。（3）基于OpenMP技术设计并实现了随机有向图弧染色并行算法。算法中通过多线程并行搜索染色解空间,从而降低染色成功所需要的时间,提高染色效率。实验结果表明该算法能有效的缩短染色所需时间。（4）基于JNI技术实现图染色算法与Java平台的结合、基于JGraph技术实现染色结果的可视化,进而设计并实现了图染色软件系统。该系统包括以下六个功能模块:图染色介绍模块、图的显示模块、图的生成模块、图染色验证模块、图染色算法模块、图染色猜想证明模块,其中图染色算法模块囊括了目前图染色领域绝大多数的图染色算法,所以该系统可以为图论研究的学者、爱好者以及应用图染色技术解决现实问题的科研工作者提供一个研究平台。