图的顶点着色问题的DNA算法

图的顶点着色问题是指无向图中任意两个相邻顶点都分配到不同的颜色,这个问题是著名的NP-完全问题,没有非常有效的算法.但在1994年Adleman^1]首次提出用DNA计算解决NP-完全问题,设计出一种全新的计算模式—模拟生物分子DNA的结构并借助于分子生物技术进行计算,使得NP-完全问题的求解可能得到解决.本文首先提出了基于分子生物技术的图的顶点着色问题的DNA算法,算法的关键是对图中的顶点和顶点的颜色进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离,依据分子生物学的实验方法,本文提出的算法是有效和可行的;其次指出了该算法的优点、存在的问题及将来进一步的研究方向.

A DNA Algorithm for Graph Vertex Coloring Problem

Given an undirected graph,the vertex coloring problem is to assign a different color for vertex mutually adjacent.This problem is an NP-complete one and has no effective solving method.But Adleman introduced firstly the DNA computing in 1994,with which the NP-complete problems are likely to be solved.DNA-based algorithm simulates molecular biology structure of DNA by means of molecular biology technological computation.This paper first introduces the DNA algorithm for the vertex coloring problem based on bio-molecular technology.The key of the algorithm is coding for the vertex and the color of the vertex The problem is solved by tube operation that performs the basic core processing and extraction that makes the results visible.On the basis of the experimental bio-molecular method,the algorithm is an effective method.Finally,the advantage and disadvantage are discussed,and the future research directions are pointed out.