CAJ | 학술논문

最大匹配问题是找给定图G中任意两条边都没有公共端点的最大边集,是NP完全问题.算法的关键是将数学问题转换到DNA链上,对图中的每条边进行适当的编码,利用生物操作及生物酶产生链及最终链的分离.给出了基于分子生物技术的图的匹配问题的DNA计算的试管方式.结果表明,提出的算法是有效可行的.
최대필배문제시조급정도G중임의량조변도몰유공공단점적최대변집,시NP완전문제.산법적관건시장수학문제전환도DNA련상,대도중적매조변진행괄당적편마,이용생물조작급생물매산생련급최종련적분리.급출료기우분자생물기술적도적필배문제적DNA계산적시관방식.결과표명,제출적산법시유효가행적.
The Maximum Matching problem is to find the largest edge sets that any two sides haven't the public end in graph G.This is the famous NP-complete problem which offer the test-tube ways of DNA computing based on matching methods of molecular biotechnology graph.The key of arithmetic is mapping the math problems on DNA chains,coding each edge of the graph correctly and using routine biologic operation and biologic enzyme,chains and to separate final chains was produced.The result shown that the arithmetic to be raised is effective and feasible.