基于粘贴和删除系统的图着色问题分析

摘要

Graph coloring problem is a NP-complete one of graph and combinatorial optimization.The computational time increases exponentially with the size of the researched problem solved using the usual methods.Thus it is impossible to settle it efficiently.Sticker system and deletion system are the language generated mechanisms based on sticking and deleting operations respec-tively.In this paper,graph coloring problem was combined with the number of bad edges and transformed into a problem of searching for the longest sequence.On the basis,the chromatic number and all the color classes of graph were obtained using the parallelism of two formal mod-els: sticker system and deletion system.Compared with the existing DNA algorithm for graph coloring problem,the proposed algorithm is of lower complexity.%图着色问题是图与组合优化中的一个NP-完全问题.现有算法在求解图着色问题时,计算复杂性随着待解问题规模的增大呈指数增长.粘贴系统和删除系统是分别基于粘贴运算和删除运算的两种语言生成器.文中将图着色问题和图的坏边数结合起来,将图着色问题转化成搜索最长序列的问题,然后利用粘贴系统和删除系统的并行性,得到了图的色数及其所有色类.与已有求解图着色问题的DNA算法相比,新的算法具有较低的复杂性.