構造對角Ｒａｍｓｅｙ圖的ＤＮＡ算法設計
2009-01-01 00:00:00耿修堂陳智華
計算機應用研究 2009年3期
（華中科技大學 控制科學與工程系， 武漢 430074）
摘 要：Ramsey數問題是一個著名的組合優化問題， 同時也是一個NP完全問題。構造對角Ramsey圖是一個難處理的計算問題，使用窮舉的算法來構造對角Ramsey圖必然導致計算量的指數爆炸，窮舉的DNA算法也不例外。提出了一個構造對角Ramsey圖的遞階式DNA粘貼—剪接算法，該算法通過逐個添加頂點的思想， 逐步刪除了問題的絕大部分非解，在一定程度上緩解了問題解的空間擴散。特別地， 專門針對對角Ramsey數R(5，5)的43階Ramsey圖的構造問題進行了計算分析， 分析結果充分地肯定了該算法的有效性。
關鍵詞：DNA計算; Ramey圖; NP完全問題; 粘貼模型; 剪接模型
中圖分類號：TP183 文獻標志碼：A
文章編號：10013695(2009)03082705
Design of DNA algorithm to construct diagonal Ramsey graph
GENG Xiutang， CHEN Zhihua
(Dept. of Control Science Engineering， Huazhong University of Science Technology， Wuhan 430074， China)
Abstract:Ramsey number problem is a famous optimization problem， and is also a NP complete problem. So constructing diagonal Ramsey graph is an intractable computation problem. To solve the problem with exhaustion method， the space complexity will grow exponentially， and the instance is similar with primitive DNA algorithm. This paper proposed a recursive DNA stickersplicing algorithm to construct diagonal Ramsey graph. The proposed algorithm could delete some incorrect solutions by adding the vertices stage by stage. As a result， the proposed algorithm relieved the need of space computation. Particularly， computational complexity of the presented algorithm was analyzed with the construction of Ramsey graph with 43 vertices for R(5，5). The analysis results of the algorithm show that the presented algorithm is effective.
Key words：DNA computing; Ramsey graph; NP complete problem; sticker model; splicing model
0 引言
DNA計算是一種以DNA與某些相關的生物酶等作為最基本材料的、基于某些生化反應原理的一種新型的分子生物計算方法。自從Adleman[1]在1994年完成的開創實驗以來，眾多學者加入到DNA計算研究領域，例如1995年， Lipton[2]提出了求解可滿足性問題的DNA算法; 1997年， Ouyang等人[3]提出了求解最大團問題的DNA算法; 2006年， Li等人[4]提出了求解3可滿足性問題的DNA算法。
以完成對角Ramsey圖的構造問題為目的，本文提出了一個對角Ramsey圖構造問題的遞階法DNA粘貼—剪接算法。各種DNA算法的第一步通常需要生成一個初始的數據池，這個數據池包含正確、也包括不正確的解；然后使用一系列對應的DNA操作來刪除這些不正確的解，從而保留了正確的解；最后通過DNA檢測操作把這些解檢測出來，即問題的解。然而，這種窮舉的搜索方法會受到問題規模的限制，換句話說，這種窮舉的搜索方法會導致指數增加的DNA數量。正是因為存在這個瓶頸，本文提出了一個構造對角Ramsey圖的遞階法DNA粘貼—剪接算法。該算法采用逐步添加頂點、分層次分隔非解的思想，從而在一定程度上克服了空間爆炸問題。
1 Ramsey數問題
對角Ramsey數問題是一個經典的圖論問題。對該問題的研究，除了理論上的推導證明外，眾多學者也以構造Ramsey圖為方法展開了對該問題的研究。由于該問題的求解難度非常之大，要想得到新的結果或一個新的界也是一件非常困難的事情。本文以DNA計算為研究工具，提出了一個構造對角Ramsey圖的DNA粘貼—剪接算法。
對角Ramsey數問題可以用約會問題來解釋，即如何邀請最少的客人，使得至少有m個人兩兩相互認識或至少有m個人兩兩相互不認識。圖論學中是這樣定義這個問題的: R(m，m)是指最小的正整數n，使得任意的n階圖， 要么含有m階團，要么含有m階獨立集。文獻[5]給出的另外兩個定義如下:
定義1 對于一個階為m的完全圖Km，對角Ramsey數R(Km，Km)定義為滿足下面條件的最小正整數n，使得:若Km的每條邊都染成紅色或藍色，無論如何染色，必定可以找到一個紅色邊的子圖Km或一個藍色邊的子圖Km。這里m≤n。
定義2 設Km是一個階為m的完全圖，對角Ramsey數R(Km，Km)是指滿足下面條件的最小正整數n，使得:對任一n階的圖G，G必包含一個同構于Km的子圖或者G的補圖包含一個同構于Km的子圖。
眾所周知， 對于m＞4的對角Ramsey數精確界的確定問題是一個極其困難的問題。表1給出了部分經典Ramsey數的已知結果。由表1可知， 對角Ramsey數R(3，3)，R(4，4)的精確值已經確定；對角Ramsey數R(5，5)的范圍在43與49之間；對角Ramsey數R(6，6)的范圍在102與165之間；而對角Ramsey數R(7，7)的范圍在205與540之間；等等。
表1 經典Ramsey數的最新結果（k≤10， l≤10）
R(k，l)l=3l=4l=5l=6l=7l=8l=9l=10
k=36[6]9[6]14[6]18[7]23[8]28[9]36[10]40[11]43[12]
k=418[6]25[13]35[14]41[13]49[15]61[16]56[17]84[18]73[19]115[10]92[20]149[21]
k=543[22]49[13]58[14]87[23]80[24]143[25]101[20]216[21]125[17]316[25]143[17]442[16]
k=6102[8]165[16]113[17]298[26]129*495[26]169[17]780[27]179N1 171[26]
k=7205[28]540[29]216N1 031[26]236*1 713[26]289N2 826[16]
k=8282[30]1 870[16]317N3 583[27]377N6 090[27]
k=9565[32]6 588[32]580N12 677[26]
k=10798[31]23 556[33]
表1中“*”表示由Shao近期構造出來的兩個新的下界；“N”表示對應的研究文獻有待于添加。關于對角Ramsey數的研究，在理論上會涉及更多的復雜內容，這些理論知識超出了本文的研究范圍。這里，就對角Ramsey圖的構造問題，談談筆者的一些研究思路。關于對角Ramsey數的研究，如R(5，5)，國內學者許進[34]提出了一個猜想：R(5，5)的Ramsey圖是個自補圖，并且由Shao驗證了R(5，5)的Ramsey圖不可能是正則自補圖。同時，許進等人[35]也提出了一個很有價值的問題：自補圖構造和Ramsey數的關系問題。筆者認為，研究Ramsey數問題，特別是對角Ramsey數問題，從自補圖角度來考慮這個問題很可能是一個不錯的突破口。
這里，有必要對自補圖的研究作一個簡單闡述。關于自補圖的構造問題，自從許進等人[35]在這方面做的工作以來，日本學者[36]在這方面做了一些補充的工作。但是，自補圖構造問題的研究，一個重要的預備知識應該是圖的同構判定問題。因為一個有效的圖同構判定的DNA算法，對于構造對角Ramsey圖DNA算法的設計是至關重要的。
Hsieh等人[37]提出了圖的同構問題的一個DNA粘貼算法。在他們的工作中，提出了圖的同構判定問題可以使用DNA粘貼算法有效地得到處理；特別地，他們提出的算法可以同時完成一組圖的同構判斷問題，這對研究Ramsey圖的構造問題很有利。具體地說，他們主要做了兩方面的工作：a)DNA編碼上他們做了大量的工作，并且結果不錯；b)在初始解的生成上，他們做了比較不錯的工作，可以大大降低實驗誤差?？傊?，他們設計的DNA算法操作比較簡便，極大地降低了實驗難度，其研究工作無疑是對本文研究工作的有力支持，這也肯定了本文的研究工作。
對于對角Ramsey構造問題的研究，對于R(3，3)和R(4，4)而言，當前的電子計算機可以輕松地完成這個任務。但是，當研究R(5，5)時，即便是使用超級的電子計算機，也是無能為力的。正是基于這個現狀，本文設計了一個對角Ramsey圖構造問題的DNA算法。為了詳細地描述該算法，本文以R(3，3)為研究對象，展開對角Ramsey圖構造問題的DNA算法的設計。所有處理過程是并行的，且該方法適合其他對角Ramsey圖構造問題的算法設計。
2 遞階法粘貼—剪接算法
使用DNA計算求解難處理的計算問題時，所面臨的最大的困難就是初始數據池會隨著問題的規模增加呈指數增長。例如，當研究Ramsey數R(5，5)時，對43個點的所有圖進行Ramsey圖判定時，使用最原始的窮舉算法逐個進行判定，問題的計算量為2903！這樣的工作量是傳統的電子計算機遙不可及的。
即便是使用DNA計算求解這樣的問題，不使用改進的DNA算法也是無能為力的。為了降低問題的初始解空間，本文設計了對角Ramsey圖構造問題的遞階法DNA粘貼—剪接算法，這種剪接操作如圖1所示。該算法以各種存儲鏈為處理單元，單元內部使用粘貼操作；各種存儲鏈之間使用的是連接操作，從而達到遞階地處理問題的目的。
對角Ramsey圖構造問題的遞階法DNA粘貼—剪接算法的主要過程如下：
a）使用足量的存儲鏈1以及對應的粘貼鏈生成全部m階的圖，對這些生成鏈進行非解分隔，最后得到一個可行解的集合。
b）以a）所獲得的解為基礎，使用足量的存儲鏈2以及對應的粘貼鏈生成全部m+1階的圖，對這些生成鏈進行非解分隔，最后得到一個新的可行解集合。
c）同理，以b）所獲得的解為基礎，使用足量的存儲鏈i以及對應的粘貼鏈生成全部m+i-1階的圖，對這些生成鏈進行非解分隔，最后得到一個新的可行解集合。直到對存儲鏈m-n+1進行同樣的處理之后，遞階法操作全部結束。
d）這時候的所有可行解，即問題的最終解。具體地說，如果試管里沒有生成鏈，表明沒有發現任何Ramsey圖；如果存在生成鏈，說明找到了一個Ramsey圖。最后，可以通過檢測操作檢測出任意一個解。
3 構造對角Ramsey圖的DNA算法
具體到對角R(3，3)的Ramsey圖構造問題，該算法需要3類存儲鏈、10類粘貼鏈。第一類存儲鏈存儲三個頂點的全部可能存在的圖;第二類存儲鏈存儲第四個頂點與全部三個頂點形成的圖的連接關系;第三類存儲鏈存儲第五個頂點與全部四個頂點形成的圖的連接關系。10類粘貼鏈對應五個頂點之間的十條邊。這三類存儲鏈以及10類粘貼鏈如圖2所示。
由圖2可見，存儲鏈x有三位信息;存儲鏈y有三位信息;存儲鏈z有四位信息。其中粘貼鏈ei，j表示頂點i與頂點j之間存在邊。到此為止，構造R(3，3)的Ramsey圖的遞階法DNA粘貼—剪接算法的簡單過程如下:
a)將足量的存儲鏈x、粘貼鏈e2，1、e3，1、e3，2混合在一起進行退火操作，生成全部可能的三個頂點的圖，對這些生成鏈x進行非解分隔，即刪除全部團為3和全部獨立集為3的圖。
b）將等量的存儲鏈y加入a）得到的生成鏈x中，通過退火，連接操作生成了生成鏈xy;然后加入適量的粘貼鏈e4，1、e4，2、e4，3，通過退火操作生成了全部4階的圖。對這些生成鏈xy進行非解分隔，即刪除全部含團為3和全部包含獨立集為3的圖。
c）將等量的存儲鏈z加入b）得到的生成鏈xy中，通過退火，連接操作生成了生成鏈xyz；然后加入適量的粘貼鏈e5，1、e5，2、e5，3、e5，4，通過退火操作生成了全部5階的圖。對這些生成鏈xyz進行非解分隔，即刪除全部含團為3和全部包含獨立集為3的圖。
d）這時候的所有解即問題的最終解。具體地說，就是試管中要是有解，它們既不含團3，也不含獨立集3。
最后，該算法的詳細過程如下:
a）試管中放入適量的存儲鏈x，接著向試管中加適量的粘貼鏈e2，1、e3，1、e3，2；然后使用退火操作生成了若干生成鏈，這些生成鏈的位信息包含八種可能狀態，即e2，1e3，1e3，2=000，001，010，011，100，101，110，111。下面通過分離操作實現非解分隔，分離工具是固定于試管內壁的核苷酸探針。這里，對應于3類粘貼鏈，總共使用了三種探針。在算法操作的第一步，所有生成鏈x放入試管T1中，使用探針e2，1將試管中的生成鏈x一分為二，由試管T2容納e2，1=0的所有生成鏈x，由試管T3容納e2，1=1的所有生成鏈x。接著使用探針e3，1將試管T2中的生成鏈x一分為二，由試管T4容納e3，1=0的所有生成鏈x，由試管T5容納e3，1=1的所有生成鏈x；同時使用探針e3，1將試管T3中的生成鏈x一分為二，由試管T6容納e3，1=0的所有生成鏈x，由試管T7容納e3，1=1的所有生成鏈x。接著使用探針e3，2將試管T4中的生成鏈x一分為二，由試管T8容納e3，2=0的所有生成鏈x，由試管T9容納e3，2=1的所有生成鏈x；同時使用探針e3，2將試管T5中的生成鏈x一分為二，由試管T10容納e3，2=0的所有生成鏈x，由試管T11容納 e3，2=1的所有生成鏈x。使用探針e3，2將試管T6中的生成鏈 x一分為二，由試管T12容納e3，2=0的所有生成鏈x，由試管T13容納e3，2=1的所有生成鏈x。使用探針e3，2將試管T7中的生成鏈x一分為二，由試管T14容納e3，2=0的所有生成鏈x，由試管T15容納e3，2=1的所有生成鏈x。最后將試管T9、 T10、T11、T12、T13、T14中的所有存儲鏈放入清空的試管T1里，其他的試管中全部是非解。本步操作的分離過程如圖3所示。
b)首先加入適量的存儲鏈y到算法第一步所得到的生成鏈x中；然后通過連接酶連接操作來連接生成鏈x與存儲鏈y得到生成鏈xy；接著，向生成鏈xy中加入適量的粘貼鏈e4，1、e4，2、e4，3，通過退火操作生成新的生成鏈。此時，新的生成鏈xy共有48種狀態，即e2，1e3，1e3，2e4，1e4，2e4，3=001000，001001，001010，001011，001100，001101，001110，001111，010000，010001，010010，010011，010100，010101，010110，010111，011000，011001，011010，011011，011100，011101，011110，011111，100000，100001，100010，100011，100100，100101，100110，100111，101000，101001，101010，101011，101100，101101，101110，101111，110000，110001，110010，110011，110100，110101，110110，110111。分離操作使用到的探針有: e2，1、e3，1、e3，2、e4，1、e4，2、e4，3 。需要處理的對象為3類子圖: v4v2v1，v4v3v1，v4v3v2。刪除子圖為團3的所有圖和子圖為獨立集3的所有圖。對每類子圖的非解刪除處理過程完全類似算法第一步操作，即計算量是第一步操作的三倍。最后，試管里剩下的新解為e2，1e3，1e3，2e4，1e4，2e4，3=001100，001101，001110，010010，010011，010110，011010，011100，011110，100001，100011，100101，101001，101100，101101，110001，110010，110011。這18個4階圖既不含有團3的子圖，也不含有獨立集3的子圖。
表2 所有五個頂點的圖的288種可行解狀態
生成鏈xy位信息生成鏈xyz位信息(e5，1、e5，2、e5，3、e5，4）
0011000000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
0011010000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
0011100000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
0100100000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
0100110000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
0101100000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
0110100000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
0111000000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
0111100000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
1000010000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
1000110000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
1001010000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
1010010000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
1011000000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
1011010000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
1100010000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
1100100000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
1100110000，0001，0010，0011，0100，0101，0110，011101000，1001，1010，1011，1100，1101，1110，1111
c)首先加入適量的存儲鏈z到算法b)所得到的生成鏈xy中；然后通過連接酶連接操作來連接生成鏈z與存儲鏈xy，得到生成鏈xyz；接著，向生成鏈xyz里加入適量的粘貼鏈e5，1、e5，2、e5，3、e5，4，通過退火操作生成新的生成鏈xyz。此時，新的生成鏈xyz共有288種狀態，如表2所示。步驟c)分離操作使用到的探針有e2，1、e3，1、e3，2、e4，1、e4，2、e4，3、e5，1、e5，2、e5，3、e5，4。需要處理的對象為6類子圖: v5v2v1、v5v3v1、v5v3v2、v5v4v1、v5v4v2、v5v4v3。這里同樣刪除子圖為團3的所有圖和子圖為獨立集3的所有圖。對每類子圖的非解刪除處理過程完全類似前面的步驟a)，但計算量是操作a)的六倍。最后，試管中剩下的新解為e2，1e3，1e3，2e4，1e4，2e4，3e5，1e5，2e5，3e5，4=0011011100，0011101010，0100111100，0101100110，0110101001，0111000101，1000111010，1001010110，1010011001，1011000011，1100010101，1100100011。這12個5階圖既不含有團3的子圖，也不含有獨立集3的子圖，它們都是對角Ramsey數的Ramsey圖。對應這12個圖的10位位信息，對應的12個Ramsey圖如圖4所示。
d)步驟c）中已經刪除了全部非解，這時候試管中只要有生成鏈xyz就表明存在Ramsey圖。那么，如何讀出一個生成鏈xyz的位信息呢?該步驟就是要完成這個任務。檢測最后解的DNA操作使用的是分離操作。這里以生成鏈xyz的值是e2，1e3，1e3，2e4，1e4，2e4，3e5，1e5，2 e5，3e5，4=0011011100為例來討論具體的解檢測過程。(a)使用探針e2，1分離生成鏈xyz為兩部分，選擇有解的部分(這里e2，1=0);(b)對有解的試管使用探針e3，1分離為兩部分，選擇有解的部分(這里e3，1=0);(c)對有解的試管使用探針e3，2分離為兩部分，選擇有解的部分(這里e3，2=1);(d)對有解的試管使用探針e4，1分離為兩部分，選擇有解的部分(這里e4，1=1);(e)對有解的試管使用探針e4，2分離為兩部分，選擇有解的部分(這里e4，2=0);(f)對有解的試管使用探針e4，3來分離為兩部分，選擇有解的部分(這里e4，3=1);(g)對有解的試管使用探針e5，1分離為兩部分，選擇有解的部分(這里e5，1=1);(h)對有解的試管使用探針e5，2分離為兩部分，選擇有解的部分(這里e5，2=1)。(i)有解的試管使用探針e5，3分離為兩部分，選擇有解的部分(這里e5，3=0);(j)有解的試管使用探針e5，4分離為兩部分，選擇有解的部分(這里e5，4=0)。檢測結果表明這個解為0011011100。整個檢測操作如圖5所示，圖中實線表示該部分為非空集合，即存在生成鏈xyz。
4 算法分析
結合第3章R(3，3)的5階對角Ramsey圖構造問題的詳細算法描述，分析R(m， m)的n階對角Ramsey圖構造問題的算法復雜性。當問題規模為n，對角Ramsey數為R(m， m)時， 該算法需要存儲鏈種類為Scl(cl為存儲鏈）， 則
Scl=n-m+1(1)
需要粘貼鏈種類為Szl（zl為粘貼鏈）， 則
Szl=∑i=n-1i=1i=n(n-1)/2(2)
需要探針種類為Stz（tz為探針）， 則
Stz=∑i=n-1i=1i=n(n-1)/2(3)
需要測試試管總和為Ssg(sg為試管）， 則
Ssg=（n-m+1)+∑i=n-1i=1i+(2m+1)=(n2+n+2m+4)/2(4)
所以，該算法的空間種類總和為Skj(kj為空間）， 則
Skj=Scl+Szl+Stz+Ssg=（3n2+n+6)/2
（5）
由式(5)可知， 該算法的占用空間復雜度為O(n2)。該算法的分離（fl)操作次數為
Sfl=（2m-1)(1+Cm-1m+Cm-1m+1+Cm-1m+2+…+
Cm-1n-1)+∑i=n-1i=1 i（6）
從操作復雜度的角度考慮， 分離操作是該算法的主要操作。為了方便該算法復雜性的分析，這里以分離操作復雜性來表示本文所提出算法的計算復雜性。隨著問題規模n的增大，m會越來越小，即m< 5 結束語 本文所設計的DNA算法利用了DNA計算的并行處理能力，從而使算法的計算時間復雜度得到了極大的降低。但是計算時間復雜度為O(mnm-1)的計算量也是很可怕的。特別是該算法還沒有對到底需要多少存儲鏈、粘貼鏈進行定量分析，因為要弄清這個問題，還需要大量的圖論知識背景，也是一個非常復雜的問題。好在這個問題并不影響本文的研究主題。 本文的主要工作是設計了一個對角Ramsey圖構造問題的遞階法DNA粘貼—剪接算法。該算法用于構造高階的對角Ramsey圖時的確是很困難，或不能實現。但是當把問題轉移到R(5，5)這個特定問題時，的確具有令人眼前一亮的感覺。由表1可知43≤R(5，5)≤49。當考慮R(5，5)的43階Ramsey圖的構造問題時，根據式(6)可知，該算法需要的操作步數為8 663 382。如前所述，2903的計算空間復雜度是一個天文數據，本文使用了遞階法的處理思想，目的就是要采用逐步添加頂點、分層次地分隔非解，最終降低了這個巨大的計算空間復雜度。 由圖4可知，在對角Ramsey數R(3，3)的5階Ramsey圖的構造算法的步驟c)中，雖然問題規模由原來的210種可能降低到只有12種可能。但是，這12個圖是相互同構的，也就是說，如果能夠刪除這些相互同構的圖，該問題的規?？赡軐⒂稍瓉淼? 024種降低為僅1種可能。所以如何遞階地排除同構的圖，也就是進一步降低算法的計算空間復雜度，也是本文所提出算法即將研究的重點工作。當然，該項工作也必須是基于DNA算法的。 根據本文綜述部分對圖的同構判別的DNA算法的分析，要想把Hsieh等人的思想應用于對角Ramsey圖構造問題的DNA算法設計上，這不是一件僅僅把別人的算法拿過來的簡單的事，還有很多的具體工作需要完成，很多困難需要克服。 參考文獻： ［1］ADLEMAN L M. Molecular computation of solutions to combinatorial problems[J]. Science ，1994，266（11）:10211024. [2]LIPTONRJ. DNAsolutionofhardcomputationalproblems[J].Science，1996，268（28）:542545. [3]OUYANG Qi，KAPLAN P D，LIUShumao，et al. DNA solution of the maximal clique problem[J]. Science， 1997，278(17):446449. [4]LI Dafa，LI Xiangrong，HUANG Hongtao，et al. Scalability of the surface based DNA algorithm for 3SAT[J]. BioSystems， 2006，85(2):9598. [5]CHARTRAND G， ZHANG Ping. 圖論導引[M].范益政，汪毅，龔世才，等譯. 北京：人民郵電出版社， 2007. [6]GREENWOOD R E，GLEASON A M. Combinatorial relations and chromatic graphs[J]. Canadian Journal of Mathematics，1955(7):17. [7]GRAVER J E，YACKEL J. Some graph theoretic results associated with Ramsey’s theorem[J]. Journal of Combinatorial Theory，1968(4):125175. [8]KALBFLEISCH J G. Chromatic graphs and Ramsey’s theorem[D]. Waterloo，Canada: University of Waterloo，1966. [9]McKAY B D，MIN Zhangke. The value of the Ramsey number R(3，8)[J]. Journal of Graph Theory，1992，16(1): 99105. [10]GRINSTEAD C M，ROBERTS S M. On the Ramsey numbers R(3，8) and R(3，9)[J]. Journal of Combinatorial Theory，1982，33:2751. [11]EXOO G. On two classical Ramsey numbers of the form R(3，n)[J].SIAM Journal of Discrete Mathematics，1989，2(4):488490. [12]RADZISZOWSKI S，KREHER D L. Upper bounds for some Ramsey numbers R(3，k)[J]. Journal of Combinat Math Combin Comput，1988，12(4): 207212. [13]McKAY B D，RADZISZOWSKI S P. R(4，5)=25[J]. Journal of Graph Theory， 1995，19(5):309322. [14]EXOO G. Announcement: on the Ramsey numbers R(4，6)， R(5，6) and R(3，12)[J]. Ars Combinatoria，1993，35:85. [15]EXOO G.Applying optimization algorithm to Ramsey problems[C]//ALAVI Y. Graph theory， combinatorics，algorithms and applications. Philadelphia: SIAM， 1989:175179. [16]MACKEY J. Combinatorial remedies[D]. Hawaii: University of Hawaii，1994. [17]EXOO G. Some new Ramsey colorings[J]. Electronic Journal of Combinatorics，1998，5(1):15. [18]EXOO G. Some applications of PQgroups in graph theory[J]. Discussiones Math Graply Theory，2004，24(1):109114. [19]RADZISZOWSKI S，KREHER D L. Search algorithm for Ramsey graphs by union of group orbits[J]. Journal ofGraph Theory，1988，12(1):5972. [20]PIWAKOWSKIK. Applying tabu search to determine new Ramsey numbers[J]. Electronic Journal of Combinatorics，1996，3(1): 14. [21]HARBORTH H，KRAUSE S. Ramsey numbers for circulant colorings[J]. Congressus Numerontium，2003，161:139150. [22]EXOO G. A lower bound for R(5，5)[J]. Journal of Graph Theory，1989，13(1): 9798. [23]SPENCER T. Upper bounds for Ramsey numbers via linear programming[EB/OL].(1993)[2007]. http://www.mathworld.wolfram.com/RamseyNumber.html. [24]CALKIN N J，ERDS P，TOVEY C A. New Ramsey bounds from cyclic graphs of prime order[J]. SIAM Journal on Discrete Mathematics， 1997，10(3):381387. [25]HAANP H. A lower bound for a Ramsey number[J]. Congressus Numerantium，2000，144:189191. [26]XU Xiaodong，XIE Zheng，RADZISZOWSKI S P. A constructive approach for the lower bounds on the Ramsey numbers R(s，t)[J]. Journal of Graph Theory，2004，47(3):231239. [27]XU Xiaodong，XU Zheng，EXOO G，et al. Constructive lower bounds on classical multicolor Ramsey numbers[J]. Electronic Journal of Combinatorics，2004，11(1):3558. [28]HILL R，IRVING R W. On group partitions associated with lower bounds for symmetric Ramsey numbers[J]. European Journal of Combinatorics，1982(3):3550. [29]GIRAUD G. Une minoration du nombre de quadrangles unicolores et son application a la majoration des nombres de Ramsey binaires bicolors[J]. C R Acad Sci Paris A，1973，276:11731175. [30]BURLING J P，REYNER S W. Some lower bounds of the Ramsey numbers n(k，k)[J]. Combinatorial Theory，1972，13:168169. [31]SHEARER J B. Lower bounds for small diagonal Ramsey numbers[J]. Journal of Combinatorial Theory，1986，42(2):302304. [32]SHI Lingsheng，ZHANG Kemin. An upper bound formula for Ramsey numbers[M]. [S.l.]:Preprint， 2001. [33]SHI Lingsheng. Upper bounds for Ramsey numbers[M]. [S.l.]:Preprint， 2002. [34]許進.自補圖理論及應用[M].西安：西安電子科技大學出版社，1999. [35]XU Jin，WONG C K. Selfcomplementary graphs and Ramsey numbers part I: the decomposition and construction of selfcomplementary graphs[J]. Discrete Mathematics，2000，223(13):309326. [36]KAWARABAYASHI K，NAKAMOTO A，ODA Y，et al. On separable selfcomplementary graphs[J]. Discrete Mathematics，2002，257(1):165168. [37]HSIEH S Y，CHEN M Y. A DNAbased solution to the graph isomorphism problem using AdlemanLipton model with stickers[J]. Applied Mathematics and Computation，2008，197(2):672686.
