【摘要】 图的着色问题是著名的NP问题,有着重要的实际意义。比如通讯系统的频道分配、考试排考场问题等方面有直接应用。图的着色问题采用DNA计算方法很多,有表面DNA计算,粘贴DNA计算。本文提出质粒DNA计算,首先把顶点着色问题转化为求最大独立集问题,然后给出了图顶点着色问题的质粒DNA分子生物实验,利用限制性内切酶的特性切割有边相连的顶点,得到最大独立集,在试验中特别引入了一个备用试管,最后给出一个具体的实例。实例给出具体的着色方案,证明了该质粒DNA算法有效并且是可行的。更多还原

【Abstract】 Graph coloring is a famous NP-problem,which has important practical significance,which applies in channel allocation of communication system,examination room arrangement and so on. There are a lot of DNA computing methods for graph coloring problem,such as surface DNA computing,pasting DNA computing. In the paper the plasmid DNA computing for the graph vertex coloring problem was presented. At first,the graph vertex coloring problem was transformed into a vertex of maximum independent set problem. Then the plasmid DNA molecular biological experiment of graph vertex coloring problem was conducted. The vertexes connected with edges were cut by using the feature of restriction enzymes,and the maximum independent set was obtained. In the experiment a spare tube was introduced. At last,the method was illustrated by an example. In the example the final coloring schemes were given. It was verified that the plasmid DNA algorithm is effective and feasible.更多还原