| 图顶点着色问题的质粒DNA计算 |
| |
| 引用本文： | 马莹,殷志祥. 图顶点着色问题的质粒DNA计算[J]. 安徽理工大学学报(自然科学版), 2015, 0(2): 64-67,86 |
| |
| 作者姓名： | 马莹 殷志祥 |
| |
| 作者单位： | 安徽理工大学理学院,安徽 淮南,232001 |
| |
| 摘 要： | 图的着色问题是著名的NP问题,有着重要的实际意义。比如通讯系统的频道分配、考试排考场问题等方面有直接应用。图的着色问题采用DNA计算方法很多,有表面DNA计算,粘贴DNA计算。本文提出质粒DNA计算,首先把顶点着色问题转化为求最大独立集问题,然后给出了图顶点着色问题的质粒DNA分子生物实验,利用限制性内切酶的特性切割有边相连的顶点,得到最大独立集,在试验中特别引入了一个备用试管,最后给出一个具体的实例。实例给出具体的着色方案,证明了该质粒DNA算法有效并且是可行的。
|
| 关 键 词： | DNA计算 顶点着色 最大独立集 质粒 |
DNA Computing Model for the Graph Vertex Coloring Problem by Plasmids |
| |
| MA Ying,YIN Zhi-xiang. DNA Computing Model for the Graph Vertex Coloring Problem by Plasmids[J]. Journal of Anhui University of Science and Technology:Natural Science, 2015, 0(2): 64-67,86 |
| |
| Authors: | MA Ying YIN Zhi-xiang |
| |
| Affiliation: | MA Ying;YIN Zhi-xiang;School of Science,Anhui University of Science and Technology; |
| |
| Abstract: | |
| |
| Keywords: | DNA computing vertex coloring problem maximum independent set plasmid |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
