構形可約性證明的DNA算法.pdf

1、DNA計算是一門新興的研究領域。1994年，Adleman在著名雜志Science上發(fā)表第一篇關于DNA計算的文章，他用DNA在試管中解決了著名的哈密爾頓路徑問題。DNA計算具有大規(guī)模并行計算的能力，而且與傳統(tǒng)的電子計算機相比能存儲更多的數(shù)據(jù)。目前DNA計算的研究已涉及許多領域，包括生物學、數(shù)學、物理、化學、計算機科學和自動化工程等多領域，包括生物學、數(shù)學、物理、化學、計算機科學和自動化工程等具體應用，是計算概念上的一次革命。

2、四色問題在1852年首次提出。是一個可與費馬猜想相媲美的難題，直到1976年才由哈肯和阿佩爾給出了第一個證明，隨后Robertson等人對他們的方法進行了改進。首先，他們給出了一個不可避免集，證明每個三剖分都至少包含不可避免集中的一個構形。第二步，他們證明每個構形都是可約的，這一部分的證明需要借助于計算機實現(xiàn)，完成第二步的證明大概需要1200個小時!本文探討用DNA計算的方法來解決構形的可約性證明，因為DNA計算具有大規(guī)模并行計算的能力