Ramsey定理在計(jì)算機(jī)領(lǐng)域中的應(yīng)用

PAGE4Ramsey定理在計(jì)算機(jī)領(lǐng)域中的應(yīng)用熊菡（武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北武漢）摘要：本文主要介紹了經(jīng)典Ramsey定理的內(nèi)容，以及Ramsey理論在網(wǎng)絡(luò)規(guī)劃和信息檢索中的應(yīng)用，將數(shù)學(xué)問題引入計(jì)算機(jī)領(lǐng)域進(jìn)行研究和探討。關(guān)鍵詞：Ramsey定理，網(wǎng)絡(luò)規(guī)劃，信息檢索1.引言Ramsey理論作為圖論的一個(gè)重要研究分支，它產(chǎn)生于1930年，起源文章為英國(guó)數(shù)學(xué)家FrankRamsey的《OnaProblemofFormalLogic》。在這篇文章里FrankRamsey討論了在某種條件下無論對(duì)集合如何劃分都能夠產(chǎn)生人們預(yù)期想要得到的子集的現(xiàn)象。后來人們?cè)谒ぷ鞯幕A(chǔ)上不斷擴(kuò)充，確定了Ramsey理論的研究?jī)?nèi)容為：在某種條件下，無論對(duì)一個(gè)大系統(tǒng)（結(jié)構(gòu)）如何進(jìn)行分割，總是能夠得到人們預(yù)期想要得到的子系統(tǒng)（結(jié)構(gòu)）。這里的系統(tǒng)即由相互關(guān)聯(lián)的事物所組成，要研究這種系統(tǒng)可以通過很多種方式進(jìn)行探討，但是“圖”是表達(dá)這種系統(tǒng)的最佳工具，因?yàn)閳D論正是討論“事物”及其“關(guān)系”的一個(gè)數(shù)學(xué)工具。所以圖論理所當(dāng)然地成為研究Ramsey理論的一個(gè)最重要的表達(dá)工具。在計(jì)算機(jī)領(lǐng)域，Ramsey理論同樣也能幫助我們解決一些問題，本文主要研究的是Ramsey理論在網(wǎng)絡(luò)規(guī)劃和信息檢索中的應(yīng)用。2.Ramsey理論及其基礎(chǔ)知識(shí)[問題]試證明任意6個(gè)人當(dāng)中一定至少有3個(gè)人相互認(rèn)識(shí)或者相互不認(rèn)識(shí)。解：首先我們先不失一般性地假設(shè)“認(rèn)識(shí)”是一種什么關(guān)系：認(rèn)識(shí)是相互的，即如果A認(rèn)識(shí)B，則B也認(rèn)識(shí)A；認(rèn)識(shí)是非傳遞的，即如果A認(rèn)識(shí)B，B認(rèn)識(shí)C，但A未必認(rèn)識(shí)C。下面對(duì)這6個(gè)人編號(hào)：A，B，C，D，E，F(xiàn)。任意取一個(gè)人，比如說A，那么根據(jù)“鴿籠原理”A要么至少認(rèn)識(shí)剩下5個(gè)人當(dāng)中的3人，或者至少不認(rèn)識(shí)剩下5個(gè)人當(dāng)中的3人。那么我們先任意取一種情況，比如取A至少認(rèn)識(shí)剩下5個(gè)人當(dāng)中的3人（任意）：B，C，D。那么如果B，C，D三個(gè)人當(dāng)中有任意兩個(gè)人相互認(rèn)識(shí)，比如說是B和C，則A、B、C三人構(gòu)成相互認(rèn)識(shí)的三個(gè)，題目的證；如果三人當(dāng)中都相互不認(rèn)識(shí)，則B、C、D三人構(gòu)成相互不認(rèn)識(shí)個(gè)人，題目也的三得證。對(duì)于另外一種情況，即A至少不認(rèn)識(shí)剩下5個(gè)人當(dāng)中的3人其證明與前面的證明相同。所以題目的結(jié)論是正確的。下面我們用數(shù)學(xué)的語言來描述上面的文字，可以這樣說：對(duì)于有6個(gè)頂點(diǎn)完全圖的邊用2種顏色（比如是紅色和藍(lán)色）進(jìn)行任意染色，則結(jié)果一定是：要么存在一個(gè)紅色的三角形，要么存在一個(gè)藍(lán)色的三角形。定義1.給定正整數(shù)n，r和圖H1，H2，…，Hr，用r種顏色對(duì)完全圖Kn的所有邊進(jìn)行著色，由第i色邊構(gòu)成的子圖記為Gi.如果存在一種著色方法，使得對(duì)所有的i(1≤i≤r)都有HiGi，則稱Kn對(duì)于(H1，H2，…，Hr)可r－著色.如果HlH2…HrH，則簡(jiǎn)稱Kn對(duì)于H可r－著色.定義2.使得Kn對(duì)于(,,…,)不能r－著色的最小正整數(shù)n稱為(經(jīng)典)Ramsey數(shù)R().如果==…==，則把R()簡(jiǎn)寫為Rr(p).定義3.使得Kn對(duì)于(H1，H2，…，Hr)不能r－著色的最小正整數(shù)n稱為廣義Ramsey數(shù)R(H1，H2，…，Hr).如果HlH2…HrH，則把R(Hl，H2，…，Hr)簡(jiǎn)寫為Rr(H).定理1.R(C4,C4)=6定理2.R(C4,C4,C4)=11定理3.若一個(gè)n個(gè)頂點(diǎn)的圖至少有條邊，則它總包含C4。Ramsey定理在計(jì)算機(jī)中的應(yīng)用3.1Ramsey定理在網(wǎng)絡(luò)規(guī)劃中的應(yīng)用分組交換網(wǎng)是采用分組交換技術(shù)的網(wǎng)絡(luò)，它從終端或計(jì)算機(jī)接收?qǐng)?bào)文，把報(bào)文分割成分組，并按某種策略選擇最佳路徑在網(wǎng)中傳輸，到達(dá)目的地后再將分組合并成報(bào)文交給目的終端或計(jì)算機(jī)。分組交換技術(shù)在網(wǎng)絡(luò)設(shè)計(jì)中被廣泛采用。用頂點(diǎn)表示通信設(shè)備，用邊表示通信鏈路，這樣得到一個(gè)圖。假定該圖是完全圖，即任意兩點(diǎn)間都有一條邊相連。在某些應(yīng)用場(chǎng)合，頂點(diǎn)兩兩配對(duì)作為一個(gè)整體。我們希望保證在某些鏈路出故障不能使用時(shí)，任兩對(duì)配對(duì)頂點(diǎn)間都至少有一條鏈路暢通無阻。圖3.1設(shè)頂點(diǎn)x1,x2組成一對(duì)，y1,y2為一對(duì)，z1,z2為一對(duì)，且故障發(fā)生在諸如微波塔、中繼站等中間設(shè)施上，見圖3.1。在此類設(shè)施上的故障將影響所有共享該設(shè)施的鏈路。對(duì)共享同一個(gè)中間設(shè)施的鏈路，我們用同一種顏色來標(biāo)記它們.如上圖表示一個(gè)有三種中間設(shè)施的通信網(wǎng)絡(luò)。在圖中，若標(biāo)記紅色的中間設(shè)施出了故障.那么在頂點(diǎn)對(duì)x1,x2和頂點(diǎn)對(duì)z1,z2之間將沒有可用的鏈路，而這對(duì)應(yīng)于下列事實(shí):四條邊(xi,zj)構(gòu)成一個(gè)單色的C4(4個(gè)頂點(diǎn)的回路)。一般來說，設(shè)計(jì)一個(gè)網(wǎng)絡(luò)需決定中間設(shè)施的數(shù)量以及哪個(gè)鏈路使用哪個(gè)設(shè)施。此外，在任何一個(gè)中間設(shè)施損壞時(shí)，我們希望所設(shè)計(jì)的網(wǎng)絡(luò)中任兩對(duì)配對(duì)頂點(diǎn)間有一個(gè)可使用的鏈路。根據(jù)上面的討論，我們應(yīng)該避免出現(xiàn)單色的C4。已知Ramsey數(shù)R(C4,C4)=6。因此，如果只有兩個(gè)中間設(shè)施，那么存在一個(gè)5個(gè)頂點(diǎn)的網(wǎng)絡(luò)使得可以安排一種不出現(xiàn)單色C4的連接方式。已知Ramsey數(shù)R(C4,C4,C4)=11,所以存在一個(gè)10個(gè)頂點(diǎn)的網(wǎng)絡(luò)，它使用三個(gè)中間設(shè)施且沒有單色的C4。前面說過，設(shè)計(jì)一個(gè)網(wǎng)絡(luò)需要決定中間設(shè)施的數(shù)量以及哪個(gè)鏈路使用哪個(gè)設(shè)施。中間設(shè)施是很昂貴的，因而希望使其數(shù)量盡可能少。所以自然要問:如果有一個(gè)n個(gè)頂點(diǎn)的網(wǎng)絡(luò)，在不出現(xiàn)單色C4的條件下中間設(shè)施的最少個(gè)數(shù)是多少?換句話說，滿足>n的最小的r是多少?比如對(duì)上圖，n=6，由于R(C4,C4)=6，R(C4,C4,C4)=11所以r=3，即我們需要3個(gè)中間設(shè)施。一般情況下，若n個(gè)頂點(diǎn)的圖的n(n-1)/2條邊分成r種顏色類，由鴿巢原理，則必存在某個(gè)類至少有條邊。我們要選擇r使得不存在包含有條邊的類，因此，選r使其滿足<就行，即滿足上述不等式的最小r就是所需要的最少中間設(shè)施數(shù)。3.2Ramsey定理在信息檢索中的應(yīng)用信息檢索是計(jì)算機(jī)科學(xué)中一個(gè)基本而又重要的問題。如何組織數(shù)據(jù)，使用什么樣的查找方法對(duì)檢索的效率有很大的影啊。我們所熟知的在有序表結(jié)構(gòu)上的二分搜索算法是一種很有效的方法，但二分搜索是最好的算法嗎?假設(shè)一個(gè)表有n個(gè)不同的項(xiàng)，其元素取自鍵空間M={1,2,，m}.我們希望找到在表中存儲(chǔ)M的任意n元子集S的方法，使得容易回答下述詢問:x在S中嗎?如何存儲(chǔ)M的n元子集的規(guī)則稱為一個(gè)表結(jié)構(gòu)或(m，n)-表結(jié)構(gòu)。最簡(jiǎn)單的表結(jié)構(gòu)是有序表結(jié)構(gòu)，它是按上升序列出S中的元素。更一般的是按置換排序的表結(jié)構(gòu)，它是固定{1,2,…,n}的一個(gè)置換，根據(jù)此置換的次序列出S中的元素。信息檢索的計(jì)算復(fù)雜性依賴于表結(jié)構(gòu)和搜索策略。復(fù)雜性的度量是最壞情形下確定x是否在S中所需要的詢問次數(shù)。例如，對(duì)于有序表結(jié)構(gòu)，如果用二分搜索，所需要的詢問次數(shù)是[log2(n+1)]。信息檢索的計(jì)算復(fù)雜性f(m，n)定義為所有可能的(m，n)-表結(jié)構(gòu)和搜索策略下的復(fù)雜性的最小值。關(guān)于f(m，n)我們有如下結(jié)論:定理1.對(duì)每個(gè)n，存在數(shù)N(n)使得f(m，n)＝[log2(n+1)]對(duì)所有mN(n)成立。據(jù)此定理，對(duì)充分大的m，就信息檢索來說，用“有序表結(jié)構(gòu)”＋“二分搜索”是最有效的方法。利用下述兩個(gè)引理,可得此定理的證明。[引理1]若m2n-l,n2，則對(duì)于按置換排序的表結(jié)構(gòu)，無論采用何種策略，在最壞情形下要確定x是否在S中至少需要[log2(n+1)]次檢查。[引理2]給定n，存在數(shù)N(n)滿足:當(dāng)mN(n)，且給定一個(gè)(m，n)-表結(jié)構(gòu)，則存在有2n-1個(gè)鍵的集合K,使得對(duì)應(yīng)于K的n元子集的表形成按置換排序的表結(jié)構(gòu)。{證明}：設(shè)n個(gè)鍵的集合S={j1,j2,…jn}以某種次序存放在表結(jié)構(gòu)中，如果j1<j2<...<jn，且ji存放在表中第ui項(xiàng)中，則S對(duì)應(yīng)1,2,…,n的置換u1,u2,...,un。按置換排序的表結(jié)構(gòu)中，每個(gè)n鍵集都對(duì)應(yīng)同一置換。給定一個(gè)(m,n)-表結(jié)構(gòu)，設(shè)={S|S是n個(gè)鍵的集合且對(duì)應(yīng)的置換是u1,u2,...,un}。令q1=q2=…qt=2n-1,t=n!又設(shè)N(n)是Ramsey數(shù)r(q1,q2,...,qt;n)。假設(shè)mN(n)，我們把鍵空間M的n元子集（有序）分成t=n!個(gè)部分，每一部分恰對(duì)應(yīng)一個(gè)集合,其中的n元子集的對(duì)應(yīng)置換都是，根據(jù)Ramsey數(shù)r(q1,q2,...,qk;n)的定義，存在某個(gè)i和M的某個(gè)qi元子集(2n-1元子集)K,K的所有n元子集都屬于某個(gè)。故引理2.2成立。至此，利用Ramsey數(shù)證明了引理2。對(duì)一個(gè)給定的(m,n)-表結(jié)構(gòu)和搜索策略以及mN(n)，可找到滿足引理2的集合K，再由引理1，即使限制在集合K上，在最壞情況下至少需要[log2(n+1)]次檢查。因而有f(m,n)[log2(n+1)]。但我們知道有序表上的二分搜索的最壞情形復(fù)雜性是[log2(n+1)]，故有f(m,n