（運(yùn)籌學(xué)與控制論專(zhuān)業(yè)論文）構(gòu)形可約性證明的dna算法.pdf

捅要 摘要 d n a 計(jì)算是一門(mén)新興的研究領(lǐng)域。1 9 9 4 年，a d l e m a n 在著名雜志s c i e n c e 上 發(fā)表第一篇關(guān)于d n a 計(jì)算的文章，他用d n a 在試管中解決了著名的哈密爾頓 路徑問(wèn)題。d n a 計(jì)算具有大規(guī)模并行計(jì)算的能力，而且與傳統(tǒng)的電子計(jì)算機(jī)相 比能存儲(chǔ)更多的數(shù)據(jù)。目前d n a 計(jì)算的研究已涉及許多領(lǐng)域，包括生物學(xué)、數(shù) 學(xué)、物理、化學(xué)、計(jì)算機(jī)科學(xué)和自動(dòng)化工程等多領(lǐng)域，包括生物學(xué)、數(shù)學(xué)、物理、 化學(xué)、計(jì)算機(jī)科學(xué)和自動(dòng)化工程等具體應(yīng)用，是計(jì)算概念上的一次革命。 四色問(wèn)題在1 8 5 2 年首次提出。是一個(gè)可與費(fèi)馬猜想相媲美的難題，直到1 9 7 6 年才由哈肯和阿佩爾給出了第一個(gè)證明，隨后r o b e r t s o n 等人對(duì)他們的方法進(jìn)行 了改進(jìn)。首先，他們給出了一個(gè)不可避免集，證明每個(gè)三剖分都至少包含不可避 免集中的一個(gè)構(gòu)形。第二步，他們證明每個(gè)構(gòu)形都是可約的，這一部分的證明需 要借助于計(jì)算機(jī)實(shí)現(xiàn)，完成第二步的證明大概需要1 2 0 0 個(gè)小時(shí)! 本文探討用d n a 計(jì)算的方法來(lái)解決構(gòu)形的可約性證明，因?yàn)閐 n a 計(jì)算具有大規(guī)模并行計(jì)算的能 力，能夠大大地減少證明所需的時(shí)間。目前還沒(méi)有這方面的研究。 本文首先簡(jiǎn)述了四色定理證明的證明，然后介紹了平滑三剖分三著色的一些 性質(zhì)和三著色的d n a 算法，在本文的最后分析了著色和符號(hào)匹配體的關(guān)系，給 出了構(gòu)形可約性的d n a 算法。本文的編碼方式十分直觀(guān)、有規(guī)律，算法簡(jiǎn)單易 于實(shí)現(xiàn)。算法具有一定的并行性，能夠大大地減少構(gòu)形可約性證明的時(shí)間。 關(guān)鍵詞：d n a 計(jì)算；四色問(wèn)題；可約性；構(gòu)形 北京工業(yè)大學(xué)理學(xué)碩士學(xué)位論文 a b s t r a c t d n a c o m p u t i n gi sa ne m e r g i n gn e ws t u d ya r e a i n1 9 9 4 ，a d l e m a nd e s c r i b e d h i s p i o n e e r i n gr e s e a r c ho nd n ac o m p u t i n gi ns c i e n c e ，w h e r eh ec o m p u t e da ni n s t a n c eo f t h eh a m i l t o n i a np a t hp r o b l e mw i t hd n ai nt e s tt u b e s t h i si st h ef i r s te x p e r i m e n t a l r e p o r to nd n ac o m p u t i n gs t u d y t h em a i nf e a t u r e so f d n a c o m p u t i n ga r em a s s i v e l y p a r a l l e lc o m p u t i n ga b i l i t ya n dp o t e n t i a le n o r m o u sd a t as t o r a g ec a p a c i t yc o m p a r i n g w i t h c o n v e n t i o n a le l e c t r o n i cc o m p u t e r s ，d n am o l e c u l e sp r o v i d ec o n c e p t u a l l ya r e v o l u t i o ni nc o m p u t i n g ，a n dm o r ea n dm o r ei m p l i c a t i o n sh a v eb e e nf o u n di nv a r i o u s d i s c i p l i n e s t h ef o u r - c o l o rp r o b l e mw a sf i r s tf o r m u l a t e di n18 5 2a n dw a sn o tp r o v e nu n t i l 1 9 7 6 a l o n gw i 也o t h e rp r o b l e m ss u c ha sf e r m a t sl a s tt h e o r e m t h i sc o n j e c t u r ew a s c o n s i d e r e do n eo ft h eg r e a to p e np r o b l e m si nm a t h e m a t i c s i n19 7 6 ，h a k e na n da p p e l g a v et h ef i r s tp r o o f , w h i c hl a t e rw a si m p r o v e db yr o b e r t s o n f i r s t ，t h e ys h o we v e r y p l a n a rt r i a n g u l a t i o nc o n t a i n s o n eo ft h ec o n f i g u r a t i o n si nt h e i ru n a v o i d a b l es e t s e c o n d ，t h e ys h o wt h a te a c hc o n f i g u r a t i o ni sr e d u c i b l e t h es e c o n ds t e pi st h ep a r to f t h ep r o o ft h a tr e q u i r e st h ea i do fac o m p u t e na p p r o x i m a t e l y1 2 0 0h o u r so fc p ut i m e w e r er e q u i r e dt oc o m p l e t et h es e c o n ds t e po ft h ep r o o f i nt h i sp a p e r , w et r yt os o l v e t h ep r o o fo fc o n f i g u r a t i o nr e d u c i b i l i t yu s i n gd n ac o m p u t i n g b e c a u s eo ft h e m a s s i v e l yp a r a l l e lc o m p u t i n ga b i l i t yo fd n ac o m p u t i n g ，w ec a ns h o r t e nt h et i m eo f t h ep r o o f g r e a t l y t h e r ei sn os u c hr e s e a r c hu pt on o w f i r s t ，w ei n t r o d u c et h ep r o o f o f f o u r - c o l o rt h e o r e mi nb r i e f s e c o n d ，w ei n t r o d u c e t h ep r o p e r t yo ft r i c o l o r i n gt os m o o t ht r i a n g u l a t i o na n dt h ed n aa l g o r i t h mo f t r i c o l o r i n g f i n a l l y , w ea n a l y z et h er e l a t i o n s h i pb e t w e e nt h ec o l o r i n ga n dt h es i g n e d m a t c h i n g ，a n dt h e np r o v i d et h ed n aa l g o r i t h mt ot h ep r o o fo fc o n f i g u r a t i o n r e d u c i b i l i t y t h ec o d i n gi nt h i sp a p e ri ss i m p l ea n dd i r e c t ；t h ea l g o r i t h mi se a s yt o c a r r yo u t t h ea l g o r i t h mi sp a r a l l e lt os o m ee x t e n t ，a n di tc a ns h o r t e nt h et i m et o p r o v et h ec o n f i g u r a t i o nr e d u c i b i l i t yg r e a t l y k e yw o r d s ：d n ac o m p u t i n g ；f o u r - c o l o rp r o b l e m ；r e d u c i b i l i t y ；c o n f i g u r a t i o n i i 獨(dú)創(chuàng)性聲明 本人聲明所呈交的論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研 究成果。盡我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他 人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果，也不包含為獲得北京工業(yè)大學(xué)或其它教育機(jī)構(gòu) 的學(xué)位或證書(shū)而使用過(guò)的材料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均 已在論文中作了明確的說(shuō)明并表示了謝意。 簽名：章魚(yú)l 日期： 關(guān)于論文使用授權(quán)的說(shuō)明 塑豎9 本人完全了解北京工業(yè)大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán) 保留送交論文的復(fù)印件，允許論文被查閱和借閱；學(xué)校可以公布論文的全部或部 分內(nèi)容，可以采用影印、縮印或其他復(fù)制手段保存論文。 ( 保密的論文在解密后應(yīng)遵守此規(guī)定) 簽名：軸牝翩簽絲隰鯊鉚 第l 章緒論 1 1d n a 計(jì)算概述 第1 章緒論 計(jì)算機(jī)科學(xué)家把計(jì)算問(wèn)題分為三類(lèi)：容易求解的，困難的和不可求解的。電 子計(jì)算機(jī)在人類(lèi)社會(huì)起到了巨大的促進(jìn)作用，但由于電子計(jì)算機(jī)的存貯量小，運(yùn) 算速度慢，智能化低，而且在圖靈機(jī)上求解計(jì)算困難問(wèn)題所需的時(shí)間往往隨問(wèn)題 規(guī)模呈指數(shù)增長(zhǎng)，這導(dǎo)致人們迫切希望尋找一種能克服上述缺點(diǎn)的新型計(jì)算機(jī)。 1 9 9 4 年，l m a d l e m a n 在著名雜志s c i e n c e 上首先發(fā)表開(kāi)創(chuàng)性論文“m o l e c u l a r c o m p u t a t i o no f s o l u t i o n st oc o m b i n a t o r i a lp r o b l e m s ”。，提出了d n a 計(jì)算的概念， 并成功地解決了著名的h a m i l t o n 路徑問(wèn)題，指出了d n a 計(jì)算潛在的巨大并行性 及待研究的問(wèn)題。1 9 9 5 年，l i p t o n 也在s c i e n c e 雜志上發(fā)表論文。3 ，進(jìn)一步論證 了d n a 計(jì)算可解決完全性問(wèn)題。自此，d n a 計(jì)算引起了國(guó)際上許多學(xué)者的關(guān)注 與興趣，并掀起了d n a 計(jì)算的研究熱潮，成為一個(gè)引人注目的研究方向。 d n a 計(jì)算的并行性使得我們可以用d n a 分子在線(xiàn)性增長(zhǎng)的時(shí)間內(nèi)解決n p 一 完全等計(jì)算困難問(wèn)題，d n a 計(jì)算開(kāi)創(chuàng)了一個(gè)非標(biāo)準(zhǔn)計(jì)算研究的新領(lǐng)域，它使人 們對(duì)計(jì)算的本質(zhì)產(chǎn)生了新的理解和認(rèn)識(shí)。 d n a 是在d n a 計(jì)算中起中心作用的分子，是重要的基因物質(zhì)，它攜帶著生 物的遺傳信息“1 ，d n a 的基本元素是核苷酸。由于化學(xué)結(jié)構(gòu)的不同，核苷酸劃 分為4 類(lèi)堿基：腺嘌呤( a ) 、鳥(niǎo)嘌呤( g ) 、胞嘧啶( c ) 和胸腺嘧啶( t ) 。d n a 由兩條核苷酸鍵組成，這兩條極長(zhǎng)的核苷酸利用堿基之間的氫鍵而結(jié)合在一起 形成一條雙股的螺旋結(jié)構(gòu)，且一股中的堿基序列與另一股中的堿基序列互補(bǔ)a 和t 配對(duì)，c 和g 配對(duì)堿基的上述配對(duì)關(guān)系稱(chēng)為w a t s o n - c r i c k ( w c ) 配對(duì)。遺傳 信息以a 、t 、c 、g 在核苷酸中的排列順序而體現(xiàn)，其排列序列的多樣性構(gòu)成 了豐富的遺傳信息。 d n a 計(jì)算解決問(wèn)題的基本思想是：利用d n a 特殊的雙螺旋結(jié)構(gòu)和堿基互 補(bǔ)配對(duì)原則對(duì)問(wèn)題進(jìn)行編碼，把要運(yùn)算的對(duì)象映射成d n a 分子鏈，在d n a 溶 液的試管里，在生物酶的作用下，生成各種數(shù)據(jù)庫(kù)，然后按照一定的規(guī)則將原 始問(wèn)題的數(shù)據(jù)運(yùn)算高度并行地映射成d n a 分子鏈的可控的生化過(guò)程。最后，利 北京工業(yè)大學(xué)理學(xué)碩士學(xué)位論文 用分子生物技術(shù)如聚合酶鏈反應(yīng)p c r 、聚合重疊放大技術(shù)、克隆、誘變、電泳、 磁珠分離等，破獲運(yùn)算結(jié)果。 從d n a 的原理來(lái)看，它與數(shù)學(xué)操作非常類(lèi)似。單股d n a 可看作由4 個(gè)不同 符號(hào)a 、g 、c 、t 組成的串，就像電子計(jì)算機(jī)中編碼0 和“1 ”一樣，可 表示成四個(gè)字母的集合= a ，g ，c ，t ) 來(lái)譯碼信息。d n a 串可作為譯碼信息， 在d n a 序列上可執(zhí)行一些簡(jiǎn)單操作。這些操作是通過(guò)大量能處理一些基本任務(wù) 的酶來(lái)完成的。也就是說(shuō)，酶可看作模擬在d n a 序列上簡(jiǎn)單的計(jì)算。不同的酶 用于不同的算子“1 。如限制內(nèi)核酸酶可作為分離算子，能夠識(shí)別特定的d n a 短 序列即限制位，任何一個(gè)在其序列中包含限制位的雙鏈d n a 在限制位被酶切 斷。d n a 結(jié)合酶可作為綁結(jié)算子，將一條d n a 鏈的末端連接到另外一條d n a 鏈。d n a 聚合酶具有可作為復(fù)制算子復(fù)制d n a 等功能。復(fù)制反應(yīng)需要一個(gè)單 鏈的向?qū) n a 即模板d n a ，和一個(gè)稍短的被稱(chēng)為引物的寡聚核苷酸且與模板 相連。在這些條件下，d n a 聚合酶對(duì)d n a 的合成有催化作用，通過(guò)在引物的 末端連續(xù)不斷的添加核菅酸來(lái)實(shí)現(xiàn)。外核酸酶可作為刪除算子等“3 。 如果說(shuō)過(guò)去所指的計(jì)算機(jī)是指物理芯片計(jì)算機(jī)，那么d n a 計(jì)算機(jī)則是化學(xué) 反應(yīng)計(jì)算機(jī)。& 口d n a 計(jì)算在本質(zhì)上屬于生化反應(yīng)，為了利用d n a 分子完成給 定的任務(wù)，我們必須借助對(duì)d n a 分子的各種操作技術(shù)。1 9 5 3 年w a s t o n 和c r i c k 發(fā)現(xiàn)d n a 之后，人們發(fā)現(xiàn)許多操作d n a 的方法。如剪切、粘貼、電泳、聚合鏈 反應(yīng)、加熱、退火等。這些操作d n a 的方法有助于人們解決內(nèi)存及信息的輸入和 接收。 經(jīng)常用到的操作有以下幾種“”： ( 1 ) 合成：使游離的堿基形成寡核苷酸的過(guò)程。 ( 2 ) 混合：把兩個(gè)試管中的溶液混合。 ( 3 ) 鏈接：兩條帶有粘頭( 也就是沒(méi)有完全配對(duì)的雙鏈) 的d n a 雙鏈在連接 酶的作用下，按w a s t o n c r i c k 互補(bǔ)配對(duì)原則且將縫隙修補(bǔ)好，從而連接在一起的 過(guò)程。 ( 4 ) 剪切：利用特定的限制性?xún)?nèi)切酶，在d n a 雙鏈的某個(gè)位置切斷形成帶 有粘頭的兩條鏈的過(guò)程。 ( 5 ) 退火和溶解：這是兩個(gè)完全相反的過(guò)程，退火是指兩條互補(bǔ)的d n a 單 第1 章緒論 鏈在溫度逐漸降低的條件下，合成一條雙鏈的過(guò)程；溶解是一條d n a 雙鏈在溫 度升高時(shí)，分解為兩條互補(bǔ)的單鏈的過(guò)程。 ( 6 ) 放大：利用p c r 技術(shù)，游離的堿基與作為模板的鏈配對(duì)連接形成雙鏈， 然后解成單鏈，繼續(xù)這樣的過(guò)程，于是目標(biāo)鏈會(huì)以2 的指數(shù)級(jí)增長(zhǎng)。 ( 7 ) 提取：將含有特定d n a 短鏈的分子提出來(lái)，這要通過(guò)將特定短鏈的互 補(bǔ)鏈吸附在小磁珠上，然后用磁鐵將小磁珠吸出來(lái)的過(guò)程。 ( 8 ) 延長(zhǎng)：這一過(guò)程需要一條已知單鏈模板和一條已存在的、并已與模板的 - - 4 段匹配的引物d n a 序列，要延長(zhǎng)的d n a 序列根據(jù)模板給出的序列結(jié)構(gòu)， 在聚合酶的作用下由5 端到3 端的方向不斷延伸。 ( 9 ) 縮短：通過(guò)外切核酸酶從d n a 分子的末端去掉一個(gè)核苷酸而縮短d n a 分子。 ( 1 0 ) 分離：將d n a 分子置于一有凝膠的電場(chǎng)中，由于d n a 分子帶負(fù)電， 在電場(chǎng)中會(huì)向正極移動(dòng)，長(zhǎng)度大的分子鏈?zhǔn)艿侥z的阻力大，移動(dòng)速度慢，因此 可用此技術(shù)去獲取一定長(zhǎng)度的d n a 分子鏈，也可區(qū)分不同長(zhǎng)度的d n a 分子。 d n a 計(jì)算就是利用這些基本的生物操作的組合來(lái)實(shí)現(xiàn)的。這些操作的組合 形成多種d n a 計(jì)算的數(shù)學(xué)模型，主要是：粘接系統(tǒng)，剪接系統(tǒng)，插入一刪除系 統(tǒng)這三種。 d n a 計(jì)算之所以具有吸引力，是因?yàn)樗哂幸韵聝?yōu)點(diǎn)： ( 1 ) d n a 分子生物算法具有高度的并行性，因而其運(yùn)算速度很快。在 a d l e m a n 的實(shí)驗(yàn)中，通過(guò)適當(dāng)估計(jì)，d n a 串的并行操作數(shù)目可達(dá)木1 0 ”，許多 研究者認(rèn)為，用當(dāng)前技術(shù)使d n a 計(jì)算達(dá)到1 0 ”1 0 2 0 個(gè)串的并行操作是可行的 相比之下，目前最快的巨型計(jì)算機(jī)每秒僅能執(zhí)行l(wèi) o ”個(gè)操作雖然d n a 計(jì)算每個(gè) 操作本身與電子實(shí)現(xiàn)相比非常緩慢，但d n a 反應(yīng)的巨大并行性足以補(bǔ)償d n a 鏈的大規(guī)模并行性可以同時(shí)攻擊一個(gè)計(jì)算問(wèn)題的不同部分，從而可以攻破諸如 數(shù)據(jù)加密標(biāo)準(zhǔn)d e s 這種最艱難的組合問(wèn)題。 ( 2 ) d n a 作為信息的載體其貯存的容量非常之大，d n a 溶液可存儲(chǔ)1 萬(wàn)億 億的二進(jìn)制數(shù)據(jù)，遠(yuǎn)遠(yuǎn)超過(guò)目前所有電子計(jì)算機(jī)的總儲(chǔ)存量。 ( 3 ) d n a 分子生物計(jì)算所消耗的能量只有一臺(tái)電子計(jì)算機(jī)完成同樣計(jì)算所 北京工業(yè)大學(xué)理學(xué)碩士學(xué)位論文 消耗的能量的十億分之一，甚至能自己提供燃料從而實(shí)現(xiàn)自供能。 d n a 計(jì)算的上述特性，即運(yùn)算的高度并行性、大容量、低能耗是目前的計(jì) 算機(jī)和并行計(jì)算機(jī)所無(wú)法比擬和替代的，而a d l e m a n 的實(shí)驗(yàn)表明，生物分子計(jì) 算從理論變成了現(xiàn)實(shí)，這在d n a 計(jì)算的歷史上具有里程碑的意義。正因?yàn)槿绱耍?d n a 計(jì)算機(jī)成為人們所追求的目標(biāo)。 目前的d n a 計(jì)算有幾種主要的形式： ( 1 ) 試管d n a 計(jì)算機(jī)：這是目前大部分d n a 計(jì)算機(jī)的工作形式。其技術(shù)核 心是進(jìn)行并行反應(yīng)的分子游離在液體中。反應(yīng)物、中間產(chǎn)物和輸出分子都混雜 在一起。需要有專(zhuān)門(mén)的步驟把輸出產(chǎn)物分離出來(lái)，分離方法有瓊脂糖電泳、毛 細(xì)管電泳、高壓液相、液質(zhì)聯(lián)用質(zhì)譜等。 ( 2 ) 表面計(jì)算“”：w i s c o n s i n 大學(xué)的研究人員把d n a 計(jì)算所有可能的結(jié)果附 著在固體表面上，然后通過(guò)系列的雜交和酶切來(lái)得到最后的答案。與試管相比， 表面計(jì)算、芯片技術(shù)、微型化技術(shù)以及納米技術(shù)等技術(shù)的綜合可能是d n a 計(jì)算 實(shí)用化的必經(jīng)之路。 ( 3 ) 雜合計(jì)算機(jī)：這種雜合計(jì)算機(jī)實(shí)際上是電子計(jì)算機(jī)與具有高度并行能力 的d n a 計(jì)算單元結(jié)合而成。我們認(rèn)為這是比較可行的第一代實(shí)用型d n a 計(jì)算 機(jī)。s u y a m aa t l 6 提出了雜合計(jì)算機(jī)的概念，電子計(jì)算機(jī)的功能是控制單元，在 電子計(jì)算機(jī)與d n a 計(jì)算單元中間有自動(dòng)化的d n a 分子加工部。 ( 4 ) 生物膜系統(tǒng)：即所謂的p 系統(tǒng)“，尚處于理論探討階段。 ( 5 ) 細(xì)胞式計(jì)算機(jī)：尚處于理論探討階段。即使單細(xì)胞生物也在執(zhí)行著復(fù)雜 而有序的分子計(jì)算過(guò)程。高等細(xì)胞在基因表達(dá)過(guò)程中的剪接以及并行處理過(guò)程， 與電子計(jì)算機(jī)中的數(shù)據(jù)化過(guò)程是相同的“”。 1 。2d n a 計(jì)算研究現(xiàn)狀 i 9 9 4 年以來(lái)，d n a 計(jì)算的高度并行性和高密度存儲(chǔ)等優(yōu)點(diǎn)使得越來(lái)越多的 科學(xué)家致力于這門(mén)學(xué)科的研究，她吸引了大量計(jì)算機(jī)、數(shù)學(xué)、生物分子學(xué)以及化 學(xué)研究者的目光。1 0 年的時(shí)間里，s c i e n c e 、n a t u r e 等頂級(jí)雜志連續(xù)的報(bào)道了這門(mén) 學(xué)科的最新創(chuàng)造成果。其中有理論方面的研究，比較有代表性的研究如d n a 計(jì) 算的通用性“、計(jì)算模型和算法、時(shí)空復(fù)雜性、有效性及容錯(cuò)性模型，也有應(yīng)用 第1 蘋(píng)緒論 方面的研究，比如可滿(mǎn)足性問(wèn)題以及各種n p 問(wèn)題、代數(shù)運(yùn)算、邏輯運(yùn)算、加密 機(jī)制等。 w i n f r e e 對(duì)d n a 自裝配計(jì)算的發(fā)展作出了貢獻(xiàn)，他的關(guān)于二維d n a 格的設(shè) 計(jì)和自裝配的論文影響了后來(lái)d n a 計(jì)算的發(fā)展方向。在他的工作基礎(chǔ)上，d n a 計(jì)算的問(wèn)題解決更具有簡(jiǎn)單性和仿真性。后來(lái)自裝配計(jì)算成為d n a 計(jì)算一個(gè)重 要的研究方面，c h e n g d em a o 等人的論文用d n a 三螺旋分子的自裝配來(lái)實(shí)現(xiàn)加 法和邏輯異或運(yùn)算，a s h i s hg e h a n i 和t h l a b e a n 等人把這種方法用于加密系統(tǒng)， 提出了種基于一次性密碼本的d n a 加密算法。日本的k e n s a k us a k a m o t o 等人 提出的發(fā)卡狀計(jì)算模型解決了可滿(mǎn)足性問(wèn)題，也是建立在d n a 自裝配的基礎(chǔ)上 的。 另一個(gè)很重要性的問(wèn)題是代數(shù)運(yùn)算的d n a 計(jì)算方法。9 6 年g u a m i e r 等人實(shí) 現(xiàn)了用d n a 計(jì)算來(lái)作加法。1 9 9 9 年，j o h n s o l i v e r 提出了矩陣乘法的d n a 計(jì)算 模型。后來(lái)又有人用動(dòng)態(tài)規(guī)劃方法解決了圖的連通性和背包問(wèn)題：符號(hào)決定性問(wèn) 題；道路染色問(wèn)題：以及超標(biāo)量計(jì)算機(jī)代數(shù)問(wèn)題等等。在神經(jīng)網(wǎng)絡(luò)方面，貝爾實(shí) 驗(yàn)室的a p m i l l s ，j r b y u r k e ，p m p l a t z m a n 提出了模擬神經(jīng)網(wǎng)絡(luò)模型的d n a 計(jì)算方法。 基于表面的d n a 計(jì)算是早在9 6 年就提出的一種模型，它的優(yōu)越性在于具有 實(shí)現(xiàn)自動(dòng)操作的潛力。2 0 0 0 年n a t u r e 刊載了q i n g h u al i u 的文章，標(biāo)志著表面上 的d n a 計(jì)算正在逐步完善。 實(shí)現(xiàn)d n a 計(jì)算的自動(dòng)化一直是研究者的個(gè)目標(biāo)，在這方面，比較突出的工 作是以色列著名的可編程生物分子自動(dòng)機(jī)的提出，模擬t u r i n g 機(jī)的裝置可以自動(dòng) 并行的根據(jù)輸入的程序執(zhí)行不同的數(shù)據(jù)處理。2 0 0 3 年趙健等在科學(xué)通報(bào)上發(fā)表 論文，在表面上實(shí)現(xiàn)了可編程的分子自動(dòng)機(jī)。 2 0 0 4 年上海交通大學(xué)b i o x 生命科學(xué)研究中心和中科院上海生科院營(yíng)養(yǎng)科學(xué) 研究所已在試管中完成了d n a 計(jì)算機(jī)的雛形研制工作，在實(shí)驗(yàn)上把自動(dòng)機(jī)與表 面d n a 計(jì)算結(jié)合到一起，標(biāo)志著中國(guó)第一臺(tái)“d n a 計(jì)算機(jī)”在上海問(wèn)世。這一 d n a 計(jì)算機(jī)是在以色列魏茨曼研究所的d n a 計(jì)算機(jī)的基礎(chǔ)上進(jìn)行改進(jìn)后完成 的，其中包括用雙色熒光標(biāo)記對(duì)輸入與輸出分子進(jìn)行同時(shí)檢測(cè)，用測(cè)序儀對(duì)自動(dòng) 運(yùn)行過(guò)程進(jìn)行實(shí)時(shí)監(jiān)測(cè)，用磁珠表面反應(yīng)法固化反應(yīng)提高可控性操作技術(shù)等，以 至最終在一定程度上完成模擬電子計(jì)算機(jī)處理0 ，1 信號(hào)的功能，并可能將來(lái)通過(guò) 北京工業(yè)大學(xué)理學(xué)碩士學(xué)位論文 計(jì)算芯片技術(shù)把電子計(jì)算機(jī)的計(jì)算功能進(jìn)行本質(zhì)上的提升。 1 3d n a 計(jì)算的應(yīng)用 ( 1 ) n p 問(wèn)題：目前d n a 計(jì)算機(jī)最出色的應(yīng)用就是n p 問(wèn)題的解決，而且自從 a d l e m a n 的工作以后，用d n a 計(jì)算能解決的數(shù)學(xué)問(wèn)題的種類(lèi)迅速增長(zhǎng)。近年來(lái) 人們意識(shí)到生物系統(tǒng)內(nèi)可能的越來(lái)越多的n p 問(wèn)題，如在一定條件下的蛋白質(zhì)的 折疊過(guò)程，復(fù)制一長(zhǎng)段d n a 序列所需要的擴(kuò)增引物數(shù)量的選擇等等。很顯然， 如果有的話(huà)，生物系統(tǒng)可能已經(jīng)解決了自己的n p 問(wèn)題。 ( 2 ) 基因分析：利用d n a 計(jì)算的方法來(lái)分析d n a 本身其實(shí)是一個(gè)很有意思 的問(wèn)題。d n a 計(jì)算過(guò)程本來(lái)就是d n a 分子的一系列反應(yīng)過(guò)程，這些過(guò)程的某些 步驟可能可以很好地反映出d n a 分子的一些特性，比如說(shuō)s n p 。用d n a 計(jì)算過(guò) 程來(lái)分析d n a 分子有什么好處呢? 一個(gè)很大的好處是高通量，因?yàn)槌笠?guī)模的 并行性是d n a 計(jì)算的天然特性。如果相關(guān)的檢測(cè)方法能解決的話(huà)，前景將非常 看好。 ( 3 ) 密碼設(shè)計(jì)和密碼破譯：日本學(xué)者嘗試用d n a 分子設(shè)計(jì)并存儲(chǔ)密碼。他們 意識(shí)到d n a 分予是天然的數(shù)據(jù)儲(chǔ)存載體，把二進(jìn)制的密碼以特定的方式轉(zhuǎn)換成 d n a 密碼分子并隱藏在海量的其它d n a 分子當(dāng)中，這些d n a 中還包括鎖定密 碼分子的d n a 鏈，必須用特定的程序才能把密碼分子擴(kuò)增出來(lái)。在密碼破譯方 面，d n a 計(jì)算已經(jīng)展示了其巨大的潛力。a d l e m a n 等描述了l i p t o n 發(fā)展的d n a 計(jì)算方法來(lái)破譯d e s 密碼。這種密碼采用2 5 6 種密鑰加密，現(xiàn)有的計(jì)算機(jī)還幾乎 不可能破解；但是l i p t o n 利用d n a 鏈強(qiáng)大的編碼和并行運(yùn)算能力構(gòu)建出全部可 能的密鑰，經(jīng)過(guò)幾個(gè)月的生物學(xué)操作，最終拿到了密鑰對(duì)應(yīng)的惟一的一條d n a 鏈。 ( 4 ) 科學(xué)家們預(yù)測(cè)，在不久的將來(lái)，d n a 計(jì)算機(jī)可被用來(lái)開(kāi)發(fā)新一代的基因 分型技術(shù)，處理基因組的信息，或用注入到人體內(nèi)的d n a 計(jì)算機(jī)進(jìn)行基因治療。 1 4 研究?jī)?nèi)容和意義 研究學(xué)者們證明了d n a 計(jì)算至少在理論上是通用的和完備的。基于d n a 計(jì) 算的機(jī)器能像我們所用的電子計(jì)算機(jī)一樣進(jìn)行編程，這主要是指d n a 計(jì)算框架 如何能模擬一個(gè)著名的通用計(jì)算模型，例如，它能模擬一個(gè)通用的圖靈機(jī)或元胞 第1 蘋(píng)緒論 自動(dòng)機(jī)。由于d n a 計(jì)算出色的并行能力，研究學(xué)者們已經(jīng)開(kāi)始考慮用它來(lái)解決 一些電子計(jì)算機(jī)很難解決的特殊問(wèn)題。近年來(lái)，國(guó)外發(fā)表了多篇論文，研究運(yùn)用 分子生物學(xué)的技術(shù)來(lái)解決一些實(shí)際問(wèn)題。 四色問(wèn)題又稱(chēng)四色猜想，是世界近代三大數(shù)學(xué)難題之一。1 9 7 6 年由哈肯和阿 佩爾給出了首個(gè)證明，他們?cè)诿绹?guó)伊利諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算機(jī)上，用 了1 2 0 0 個(gè)小時(shí)，作了1 0 0 億判斷，完成了四色定理的證明，轟動(dòng)了世界。此后 羅伯特森等人又給出了改進(jìn)的算法，但是整體來(lái)說(shuō)，這些方法證明起來(lái)所花費(fèi)的 時(shí)間都相當(dāng)長(zhǎng)?；赿 n a 計(jì)算的優(yōu)點(diǎn)，我們?cè)诒疚奶接懹胐 n a 計(jì)算的方法來(lái) 證明四色定理，這里所指的證明是指用d n a 計(jì)算的方法來(lái)實(shí)現(xiàn)四色定理證明中 計(jì)算機(jī)證明的部分，而不包括邏輯證明部分，以其在較短的時(shí)間內(nèi)實(shí)現(xiàn)計(jì)算機(jī)證 明的部分。 雖然人們已經(jīng)證明了d n a 計(jì)算的通用性和完備性，也就是說(shuō)用電子計(jì)算機(jī) 可以解決的問(wèn)題用d n a 計(jì)算也一定能解決，但這都是理論性的，我們?cè)谶@篇文 章中就是要設(shè)計(jì)一個(gè)具體的算法，來(lái)解決四色定理的證明。如果可以解決，顯然 是具有非常大的現(xiàn)實(shí)意義的。 1 5 本章小結(jié) 本章介紹了d n a 計(jì)算的計(jì)算機(jī)制、d n a 計(jì)算常用的生物操作、d n a 計(jì)算 的研究現(xiàn)狀以及d n a 計(jì)算的應(yīng)用，給出了本文的研究?jī)?nèi)容和意義。 2 1 四色定理簡(jiǎn)介 第2 章四色定理證明 四色問(wèn)題又稱(chēng)四色猜想，是世界近代三大數(shù)學(xué)難題之一。 四色問(wèn)題的內(nèi)容是：“任何一張地圖只用四種顏色就能使具有共同邊界的國(guó) 家著上不同的顏色。”用數(shù)學(xué)語(yǔ)言表示，即“將平面任意地細(xì)分為不相重迭的區(qū) 域，每一個(gè)區(qū)域總可以用1 ，2 ，3 ，4 這四個(gè)數(shù)字之一來(lái)標(biāo)記，而不會(huì)使相鄰的 兩個(gè)區(qū)域得到相同的數(shù)字?！边@里所指的相鄰區(qū)域，是指有一整段邊界是公共的。 如果兩個(gè)區(qū)域只相遇于點(diǎn)或有限多點(diǎn)，就不叫相鄰的。因?yàn)橛孟嗤念伾o它 們著色不會(huì)引起混淆。 四色猜想的提出來(lái)自英國(guó)。1 8 5 2 年，畢業(yè)于倫敦大學(xué)的弗南西斯格思里來(lái) 到一家科研單位搞地圖著色工作時(shí)，發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來(lái)，每幅地圖 都可以用四種顏色著色，使得有共同邊界的國(guó)家都被著上不同的顏色?！边@個(gè)現(xiàn) 象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢? 他和在大學(xué)讀書(shū)的弟弟格里斯決心試一試。 兄弟二人為證明這一問(wèn)題而使用的稿紙已經(jīng)堆了一大疊，可是研究工作沒(méi)有進(jìn) 展。 1 8 5 2 年1 0 月2 3 日，他的弟弟就這個(gè)問(wèn)題的證明請(qǐng)教了他的老師、著名數(shù)學(xué) 家德摩爾根，摩爾根也沒(méi)有能找到解決這個(gè)問(wèn)題的途徑，于是寫(xiě)信向自己的好 友、著名數(shù)學(xué)家漢密爾頓爵士請(qǐng)教。漢密爾頓接到摩爾根的信后，對(duì)四色問(wèn)題進(jìn) 行論證。但直到1 8 6 5 年漢密爾頓逝世為止，問(wèn)題也沒(méi)有能夠解決。 1 8 7 2 年，英國(guó)當(dāng)時(shí)最著名的數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問(wèn) 題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問(wèn)題。世界上許多一流的數(shù)學(xué)家都紛紛 參加了四色猜想的大會(huì)戰(zhàn)。1 8 7 8 1 8 8 0 年兩年間，著名的律師兼數(shù)學(xué)家肯普和 泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，大家都認(rèn)為四 色猜想從此也就解決了。 肯普的證明是這樣的：首先指出如果沒(méi)有一個(gè)國(guó)家包圍其他國(guó)家，或沒(méi)有三 個(gè)以上的國(guó)家相遇于一點(diǎn)，這種地圖就說(shuō)是“正規(guī)的”，否則為非正規(guī)地圖。一 張地圖往往是由正規(guī)地圖和非正規(guī)地圖聯(lián)系在一起，但非正規(guī)地圖所需顏色種數(shù) 第2 章四色定理證明 一般不超過(guò)正規(guī)地圖所需的顏色，如果有一張需要五種顏色的地圖，那就是指它 的正規(guī)地圖是五色的，要證明四色猜想成立，只要證明不存在一張正規(guī)五色地圖 就足夠了。 肯普的證明包含兩個(gè)重要的步驟。他先用歸納法證明了一個(gè)圖g 至少存在一 個(gè)頂點(diǎn)v ，使得v 至多與五個(gè)其他的頂點(diǎn)相鄰。我們把這些頂點(diǎn)標(biāo)記為 ”1 ，v 。，m 5 。然后將頂點(diǎn)v 刪除，這樣得到一個(gè)圖g 。= g v 。第二步主要證 明可以四著色的g 可以被重新著色，使得h ，v 。只需要三種不同的顏色進(jìn)行著 色。把這些頂點(diǎn)進(jìn)行著色的方法，現(xiàn)在稱(chēng)之為肯普鏈?？掀真湸笾率沁@樣定義的： 由一些顏色交替的相鄰的國(guó)家所連成的一條鏈。在圖論當(dāng)中，肯普鏈實(shí)際上是相 鄰頂點(diǎn)所組成的序列?？掀兆詈笾匦乱腠旤c(diǎn)v ，將它用第四種顏色進(jìn)行著色 完成了整個(gè)證明。后來(lái)有人指出肯普的證明是錯(cuò)誤的，不過(guò)肯普的證明闡明了兩 個(gè)重要的概念，對(duì)以后問(wèn)題的解決提供了途徑。第一個(gè)概念是“構(gòu)形”。他證明 了在每一張正規(guī)地圖中至少有國(guó)具有兩個(gè)、三個(gè)、四個(gè)或五個(gè)鄰國(guó)，不存在每 個(gè)國(guó)家都有六個(gè)或更多個(gè)鄰國(guó)的正規(guī)地圖，也就是說(shuō)，由兩個(gè)鄰國(guó)，三個(gè)鄰國(guó)、 四個(gè)或五個(gè)鄰國(guó)組成的一組“構(gòu)形”是不可避免的，每張地圖至少含有這四種構(gòu) 形中的一個(gè)( 如圖2 1 ) 。 武 到2 1 構(gòu)形 f i g u r e2 - 1c o n i i g u r a t i o n s 肯普提出的另一個(gè)概念是“可約”性。“可約”這個(gè)詞的使用是來(lái)自肯普的論 證。他證明了只要五色地圖中有一國(guó)具有四個(gè)鄰國(guó)，就會(huì)有國(guó)數(shù)減少的五色地圖。 自從引入“構(gòu)形”，“可約”概念后，逐步發(fā)展了檢查構(gòu)形以決定是否可約的一 些標(biāo)準(zhǔn)方法，能夠?qū)で罂杉s構(gòu)形的不可避免組，是證明“四色問(wèn)題”的重要依據(jù)。 但要證明大的構(gòu)形可約，需要檢查大量的細(xì)節(jié)，這是相當(dāng)復(fù)雜的。 1 1 年后，即1 8 9 0 年，在牛滓大學(xué)就讀的年僅2 9 歲的赫伍德以自己的精確計(jì) 算指出了肯普在證明上的漏洞。他指出肯普說(shuō)沒(méi)有極小五色地圖能有一國(guó)具有五 個(gè)鄰國(guó)的理由有破綻。不久，泰勒的證明也被人們否定了。人們發(fā)現(xiàn)他們實(shí)際上 北京工業(yè)大學(xué)理學(xué)碩士學(xué)位論文 證明了一個(gè)較弱的命題五色定理。就是說(shuō)對(duì)地圖著色，用五種顏色就夠了。 后來(lái)，越來(lái)越多的數(shù)學(xué)家雖然對(duì)此絞盡腦汁，但一無(wú)所獲。于是，人們開(kāi)始認(rèn)識(shí) 到，這個(gè)貌似容易的題目，其實(shí)是一個(gè)可與費(fèi)馬猜想相媲美的難題。 進(jìn)入2 0 世紀(jì)以來(lái)，科學(xué)家們對(duì)四色猜想的證明基本上是按照肯普的想法在 進(jìn)行。1 9 13 年，美國(guó)著名數(shù)學(xué)家、哈佛大學(xué)的伯克霍夫利用肯普的想法，結(jié)合 自己新的設(shè)想；證明了某些大的構(gòu)形可約。后來(lái)美國(guó)數(shù)學(xué)家富蘭克林于1 9 3 9 年 證明了2 2 國(guó)以下的地圖都可以用四色著色。1 9 5 0 年，有人從2 2 國(guó)推進(jìn)到3 5 國(guó)。 1 9 6 0 年，有人又證明了3 9 國(guó)以下的地圖可以只用四種顏色著色；隨后又推進(jìn)到 了5 0 國(guó)。看來(lái)這種推進(jìn)仍然十分緩隉。 高速數(shù)字計(jì)算機(jī)的發(fā)明，促使更多數(shù)學(xué)家對(duì)“四色問(wèn)題”的研究。從1 9 3 6 年就開(kāi)始研究四色猜想的?？?，公開(kāi)宣稱(chēng)四色猜想可用尋找可約圖形的不可避免 組來(lái)證明。他的學(xué)生丟雷寫(xiě)了一個(gè)計(jì)算程序，?？瞬粌H能用這程序產(chǎn)生的數(shù)據(jù)來(lái) 證明構(gòu)形可約，而且描繪可約構(gòu)形的方法是從改造地圖成為數(shù)學(xué)上稱(chēng)為“對(duì)偶” 形著手。他把每個(gè)國(guó)家的首都標(biāo)出來(lái)，然后把相鄰國(guó)家的首都用一條越過(guò)邊界的 鐵路連接起來(lái)，除首都( 稱(chēng)為頂點(diǎn)) 及鐵路( 稱(chēng)為弧或邊) 外，擦掉其他所有的線(xiàn)， 剩下的稱(chēng)為原圖的對(duì)偶圖( 如圖2 2 ) 。到了六十年代后期，?？艘M(jìn)個(gè)類(lèi)似于 在電網(wǎng)絡(luò)中移動(dòng)電荷的方法來(lái)求構(gòu)形的不可避免組。在?？说难芯恐械谝淮我灶H 不成熟的形式出現(xiàn)的“放電法”，這對(duì)以后關(guān)于不可避免組的研究是個(gè)關(guān)鍵，也 是證明四色定理的中心要素。 圖2 - 2 一個(gè)幽的對(duì)偶圖 f i g u r e2 - 2t h ed u a lg r a p ho f ag r a p h 電子計(jì)算機(jī)問(wèn)世以后，由于演算速度迅速提高，加之人機(jī)對(duì)話(huà)的出現(xiàn)，大大 加快了對(duì)四色猜想證明的進(jìn)程。美國(guó)伊利諾大學(xué)哈肯在1 9 7 0 年著手改進(jìn)“放電 過(guò)程”，后與阿佩爾合作編制一個(gè)很好的程序。就在1 9 7 6 年6 月，他們?cè)诿绹?guó) 伊剎諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算杌上，用了1 2 0 0 個(gè)小時(shí)，作了1 0 0 億判斷， 第2 章四色定理證明 終于完成了四色定理的證明，轟動(dòng)了世界。 1 9 9 6 年，美國(guó)數(shù)學(xué)學(xué)會(huì)的電子研究雜志上又發(fā)表了篇關(guān)于四色猜想的證 明。這個(gè)證明是對(duì)阿佩爾和哈肯證明的改進(jìn)。而且，它再一次證實(shí)了阿佩爾和哈 肯計(jì)算機(jī)證明的正確性。這個(gè)新的證明是由羅伯特等人提出的。羅伯特使俄亥俄 州立大學(xué)數(shù)學(xué)系的教授，于1 9 6 9 年獲得沃特盧大學(xué)博士。雖然整個(gè)證明簡(jiǎn)化了， 但是證明的框架與阿佩爾一哈肯的證明是相同的。整個(gè)證明的組織結(jié)構(gòu)如下： ( 1 ) 列出一個(gè)構(gòu)形集。 ( 2 ) 可約性證明：構(gòu)形集當(dāng)中的構(gòu)形不會(huì)出現(xiàn)在四色猜想的極小反例當(dāng)中。因?yàn)?一旦有個(gè)構(gòu)形出現(xiàn)在極小反例當(dāng)中，那么可以給出一個(gè)更小的極小反例。這一 部分的證明與阿佩爾一哈肯的證明一樣，都是用計(jì)算機(jī)來(lái)證明的。 ( 3 ) 證明每個(gè)極小反例都是“內(nèi)部六連通”的三剖分。 ( 4 ) 不可避免性證明：每個(gè)內(nèi)部六連通的三剖分至少包含一個(gè)構(gòu)形。 因此，不存在極小反例。如果不存在極小反例，那么四色猜想是成立的。 新證明主要的優(yōu)點(diǎn)在于： ( 1 ) 不可避免集的數(shù)量從1 4 7 6 個(gè)減到6 3 3 個(gè)： ( 2 ) “放電”規(guī)則從3 0 0 個(gè)減少到3 2 個(gè)： ( 3 ) 尋找一個(gè)平面圖四著色算法的時(shí)間復(fù)雜度由s 3 減到s ： ( 4 ) 不可避免性的證明也得到了改進(jìn)。 這是一百多年來(lái)吸引許多數(shù)學(xué)家與數(shù)學(xué)愛(ài)好者的大事，當(dāng)兩位數(shù)學(xué)家將他們 的研究成果發(fā)表的時(shí)候，當(dāng)?shù)氐泥]局在當(dāng)天發(fā)出的所有郵件上都加蓋了“四色足 夠”的特制郵戳，以慶祝這一難題獲得解決。 “四色問(wèn)題”的被證明僅解決了一個(gè)歷時(shí)i 0 0 多年的難題，而且成為數(shù)學(xué)史 上一系列新思維的起點(diǎn)。在“四色問(wèn)題”的研究過(guò)程中，不少新的數(shù)學(xué)理論隨之 產(chǎn)生，也發(fā)展了很多數(shù)學(xué)計(jì)算技巧。如將地圖的著色問(wèn)題化為圖論問(wèn)題，豐富了 圖論的內(nèi)容。不僅如此，“四色問(wèn)題”在有效地設(shè)計(jì)航空班機(jī)日程表，設(shè)計(jì)計(jì)算 機(jī)的編碼程序上都起到了推動(dòng)作用。 不過(guò)不少數(shù)學(xué)家并不滿(mǎn)足于計(jì)算機(jī)取得的成就，他們認(rèn)為應(yīng)該有一種簡(jiǎn)捷明 快的書(shū)面證明方法。直到現(xiàn)在，仍由不少數(shù)學(xué)家和數(shù)學(xué)愛(ài)好者在尋找更簡(jiǎn)潔的證 明方法。 2 2 四色定理證明 2 2 1 預(yù)備知識(shí) 令r 是一個(gè)圖，礦( 丁) ，e ( t ) 分別代表圖r 所有點(diǎn)和所有邊的集合，其中 y ( ，) ，e ( r ) 都是有限集，任何一條邊和兩個(gè)頂點(diǎn)相連接。( v ) 代表圖t 中一個(gè) 頂點(diǎn)v 的度數(shù)。 如果圖丁能畫(huà)在一個(gè)平面上，且使得丁中除端點(diǎn)外任意兩條邊均不相交，則 稱(chēng)圖r 是可平面的。平面上的圖r 有一個(gè)無(wú)限區(qū)，它的意義在于歐拉公式的應(yīng)用， 因?yàn)闅W拉公式是用在平面或球面上的。對(duì)于一個(gè)可平面圖，其歐拉公式為 p q + ，= 2 ，其中p ，g ，分別是點(diǎn)、邊和區(qū)的個(gè)數(shù)。 在圖論中，任何區(qū)是三角區(qū)的圖稱(chēng)為一個(gè)- - 音t j 分( 如圖2 3 ) 。e 是三角區(qū)r 的 三條邊，則稱(chēng)e 與三角區(qū)，相關(guān)聯(lián)。 、k 芬 圖2 - 3 三剖分示例 f i g u r e2 - 3a ne x a m p l eo f t r i a n g u l a t i o n 一個(gè)圖分為有限區(qū)和無(wú)限區(qū)兩部分，一個(gè)三剖分加上無(wú)限區(qū)稱(chēng)為一個(gè)近三剖 分。 令g 是一個(gè)三剖分或者近三剖分，令k ：五( g ) - 卜1 ，0 ，1 ) 是一個(gè)映射，若 k ( e ) ，k ( ，) ，k ( g ) ) = 1 , 0 ，1 ) ，其中e ，f ，g 是三角區(qū)r 的三條邊，則稱(chēng)，被三著色。 第2 章四色定理證明 如果g 的每個(gè)區(qū)被三著色( 是一個(gè)三剖分) 或者g 的每個(gè)有限區(qū)被三著色( g 是 一個(gè)近三剖分) ，我們說(shuō)k 是g 的一個(gè)邊的三著色。 令七：v ( g ) _ 1 ，2 ，3 ，4 是另一個(gè)映射，對(duì)于g 的任何一條邊，如果它與點(diǎn)“，v 相關(guān)聯(lián)，且有k ( u ) k ( v ) ，則我們稱(chēng)g 被頂點(diǎn)四著色。k 稱(chēng)為g 的一個(gè)頂點(diǎn)四著 色。 后文中凡是提到四著色均指頂點(diǎn)的四著色，而三著色均指邊的三著色。 ( 2 1 ) “”一個(gè)三剖分丁是可以頂點(diǎn)四著色的當(dāng)且僅當(dāng)可以對(duì)它進(jìn)行邊的三著 色。 例如，對(duì)三剖分任意一條邊e ，如果它有兩個(gè)頂點(diǎn)“，v ，可以建立如下對(duì)應(yīng) f 一1 七( “) ，t ( v ) ) = 1 , 2 或者 3 ，4 ) 方式：巾( 8 ) = 0 _ j ( “) ，七( v ) ) = 1 ，3 ) 或者 2 ，4 ) i l 尼( “) ，七( v ) ) = 1 , 4 ) 或者 2 ，3 ) 這樣如果一個(gè)三剖分可以進(jìn)行頂點(diǎn)四著色，那么按照上面的對(duì)應(yīng)方式就可以 進(jìn)行邊的三著色。在做計(jì)算機(jī)程序時(shí)，三著色比四著色來(lái)的更為容易一些，同時(shí) 它們兩者之間的轉(zhuǎn)化卻是非常簡(jiǎn)單的，所以在后面的證明中我們使用三著色。 l 圖2 4 頂點(diǎn)四著色和邊三著色 f i g u r e2 - 4f o u rc o l o r i n go f v e r t i c e s a n dt h r e ec o l o r i n go f e d g e s 對(duì)于每一個(gè)地圖，我們可以把每一個(gè)區(qū)( 區(qū)域或國(guó)家) 看作一個(gè)點(diǎn)，而區(qū)與 區(qū)之間的鄰接關(guān)系看作點(diǎn)與點(diǎn)之間的連線(xiàn)，因此得到一個(gè)點(diǎn)線(xiàn)圖。這不是個(gè)三 剖分。但是通過(guò)適當(dāng)加一些邊它可以成為一個(gè)三剖分。很明顯，如果加邊以后的 三剖分有一個(gè)三著色，那么它可以很容易的轉(zhuǎn)化成原圖的三著色。因此，我們可 以通過(guò)找出加邊后的三剖分三著色的方法來(lái)找出原圖的三著色。 北京工業(yè)大學(xué)理學(xué)碩士學(xué)位論文 2 2 2 構(gòu)形 如果圖r 不可以四著色，而對(duì)于任一個(gè)圖丁。， 若 l v ( t ) 卜i e ( r ) 1 d g ( v ) 。 兩種情況下都有7 。( v ) 5 。 ( 3 ) k 有環(huán)型2 ，環(huán)型定義如下：e ( y f ( v ) 一d a ( v ) 一1 ) ，其中 ”e f f = v v 與世的無(wú)限區(qū)相關(guān)聯(lián)，且g ( 世) 睫連通的 。 四鄰鄰pp 鄰舀 哪哪媽翎哪哪哪 圖2 - 5 部分構(gòu)形 f i g u r e2 - 5p a r to f c o n f i g u r a t i o n s 第2 章四色定理證明 構(gòu)形也是四色定理證明當(dāng)中一個(gè)非常重要的概念，在羅伯特森等人的證明 中共給出了6 3 3 個(gè)構(gòu)形。 在用圖形描述構(gòu)形k 的時(shí)候，一個(gè)辦法是畫(huà)出圖，把( v ) 的值寫(xiě)在對(duì)應(yīng)的 頂點(diǎn)v 的旁邊，但是這樣表示起來(lái)不方便。羅伯特森等人沿用?？说姆椒ㄓ庙旤c(diǎn) 的形狀來(lái)表示k ( v ) 的值，如圖2 - 6 所示： ，y 耳( ”) = 5 7 k ( ”) = 6 o1 k ( ”) = 7 口，y 片( 扣) = 8 v懈( ”) = 9 o ，y ( t j ) = 1 0 圖2 - 6 頂點(diǎn)的形狀 f i g u r e2 - 6t h es h a p e so f v e r t i c e s 兩個(gè)構(gòu)形k 和工是同構(gòu)的，如果存在一個(gè)所在平面的同胚，將g ( k ) 映到 g ( z ) ，y 。映到y(tǒng) 。在 1 9 1 q u 共列出t 6 3 3 個(gè)構(gòu)形，圖2 5 給出了其中的部分構(gòu)形。 與6 3 3 個(gè)構(gòu)形中任何一個(gè)構(gòu)形同構(gòu)的構(gòu)形稱(chēng)為一個(gè)好構(gòu)形。 ( 2 3 ) i t 9 如果丁是一個(gè)極小反例，那么t 中沒(méi)有好構(gòu)形出現(xiàn)。 ( 2 4 ) 1 1 9 】對(duì)于每個(gè)內(nèi)部6 連通的三剖分7 1 ，r 中會(huì)出現(xiàn)一些好構(gòu)形。 由( 2 2 ) 、( 2 3 ) 、( 2 4 ) 可知：極小反例不存在，四色定理是正確的。本文將在 2 2 3 節(jié)中討論( 2 3 ) ，( 2 4 ) 可以在比較短的時(shí)間內(nèi)用手工驗(yàn)證，具體的證明可參照 【19 】。( 2 3 ) 要依靠計(jì)算機(jī)來(lái)進(jìn)行證明，而且需要相當(dāng)長(zhǎng)的時(shí)間，本文的主要目的 就是要用d n a 計(jì)算來(lái)減少證明的時(shí)間。 2 2 3 可約性 一個(gè)回路指一個(gè)非空的圖，且圖中每個(gè)頂點(diǎn)的度數(shù)都是2 。 1 9 1 令世是一個(gè)構(gòu)形，s 是近三剖分。如果： ( 1 ) r 是s 的導(dǎo)出回路，且是s 的無(wú)限區(qū)的邊界。 ( 2 ) g ( k ) 是s 的一個(gè)導(dǎo)出子圖，g ( 世) = s 礦( r ) ，f f ：侗j g ( k ) 的有限區(qū)是 s 的有限區(qū)，c ( k ) 的無(wú)限區(qū)包含r 和s 的無(wú)限區(qū)。 1 5 北京工業(yè)大學(xué)理學(xué)碩士學(xué)位論文 ( 3 ) 任何在s 中不在v ( r ) 中的點(diǎn)v 在s 中的度數(shù)為y 。( v ) 。 則稱(chēng)s 是構(gòu)形k 的關(guān)于環(huán)r 的自由補(bǔ)全圖。 圖2 7 為6 3 3 個(gè)構(gòu)形當(dāng)中的其中一個(gè) 0 ，g 。，g ，與日的無(wú)限區(qū)相關(guān)聯(lián)；若t = 0 ，則g ，與的任何有限區(qū)都不 關(guān)聯(lián)； 4 ) 1 i f ，與g h 和g 。相關(guān)聯(lián)； 5 ) 0 f ，k ( g ，) 0 。 說(shuō)明：本章帶+ 的內(nèi)容源自蔣興鵬的畢業(yè)論文任意地圖四著色問(wèn)題的d n a 算法 第3 章三著色的d n a 算法 v j 圖3 - i 三剖分的脈 f i g u r e3 - 1t h er i b so f t r i a n g u l a t i o n 脈