安徽理工大学学报（自然科学版）
安徽理工大學學報（自然科學版）
안휘리공대학학보（자연과학판）
Journal of Anhui University of Science and Technology (Natural Science)
2015年
3期
17-20
,共4页
最小顶点覆盖%DNA自组装模型%可满足性问题
最小頂點覆蓋%DNA自組裝模型%可滿足性問題
최소정점복개%DNA자조장모형%가만족성문제
minimum vertex cover problem%DNA self-assembly model%satisfiability problem
在分析最小顶点覆盖问题特点的基础上，以5个顶点的图为例，将最小顶点覆盖问题转化为可满足性问题，简化问题的操作难度。再根据DNA 自组装的自发性和并行性等优势，通过建立DNA自组装模型解决可满足性问题，从而解决图的最小顶点覆盖问题。相对于传统算法，本算法只应用了凝胶电泳技术，大大的降低了操作难度和误差。
在分析最小頂點覆蓋問題特點的基礎上，以5箇頂點的圖為例，將最小頂點覆蓋問題轉化為可滿足性問題，簡化問題的操作難度。再根據DNA 自組裝的自髮性和併行性等優勢，通過建立DNA自組裝模型解決可滿足性問題，從而解決圖的最小頂點覆蓋問題。相對于傳統算法，本算法隻應用瞭凝膠電泳技術，大大的降低瞭操作難度和誤差。
재분석최소정점복개문제특점적기출상，이5개정점적도위례，장최소정점복개문제전화위가만족성문제，간화문제적조작난도。재근거DNA 자조장적자발성화병행성등우세，통과건립DNA자조장모형해결가만족성문제，종이해결도적최소정점복개문제。상대우전통산법，본산법지응용료응효전영기술，대대적강저료조작난도화오차。
On the basis of analysis of the characteristics of the minimum vertex cover problem , taking a graph with 5 vertices as an example the minimum vertex cover problem was transformed into a problem of satisfiability , to simplify the operation of the problem .Then according to spontaneity and parallelism of DNA self -assembly and other advantages , by establishing self -assembly model of DNA the satisfiability problem was solved .Thus the minimum vertex cover problem was solved .Compared with the traditional algorithm , in the studied algorithm only gel electrophoresis technology is applied , which greatly reduces the difficulty of the operation and error .
