【摘要】 为了用生化实验的方法解决图的顶点着色问题,基于粘贴模型的巨大并行性,将着色问题转化为可满足性问题,提出一个基于粘贴模型的DNA算法。通过一个实例给出了操作步骤,并对生化反应过程进行了模拟,得出具体的着色方案,证明了该算法的可行性。更多还原

【Abstract】 In order to solve the graph vertex-coloring problem, a DNA algorithm based on sticker model was proposed, which converted the coloring problem to satisfiability problem on the basis of the vast parallelism. The operation steps were given through an instance. And a simulation experiment was carried out to illustrate the biochemical procedures. The final coloring schemes were got. Consequently, the feasibility of the algorithm is proved.更多还原