Ramsey定理的應(yīng)用

1、第一節(jié) Ramsey定理在網(wǎng)絡(luò)規(guī)劃中的應(yīng)用一、基礎(chǔ)知識定義1.給定正整數(shù)n, r和圖Hi, H2,，Hr，用r種顏色對完 全圖Kn的所有邊進(jìn)行著色，由第i色邊構(gòu)成的子圖記為Gi如果存在 一種著色方法，使得對所有的i(1E環(huán))都有H二Gi，則稱Kn對于(Hi, H2,，Hr)可r 著色.如果Hl三出三三Hr三H，則簡稱Kn對于H可 r 著色.定義2.使得Kn對于(Kpi,Kp2,Kpr)不能r 著色的最小正整數(shù)n 稱為(經(jīng)典)Ramsey數(shù)R(皿p2,., pr).如果pi = P2二二Pr = p，則把 R( Pi, P2,Pr)簡寫為 Rr(p).定義3.使得Kn對于(Hi，H2,，Hr)不

2、能r 著色的最小正整數(shù) n稱為廣義Ramsey數(shù)R(Hi, H2，Hr).如果H H三H H, 則把R(H|, H2，,Hr)簡寫為Rr(H).定理 1. R(C4,C4)=6定理 2 R(C4,C4,C4)=11定理3.若一個n個頂點的圖至少有In3/2 -丄n條邊，則它總包含C4。24二、分組交換網(wǎng)的設(shè)計分組交換網(wǎng)是采用分組交換技術(shù)的網(wǎng)絡(luò)，它從終端或計算機(jī)接收 報文，把報文分割成分組，并按某種策略選擇最佳路徑在網(wǎng)中傳輸， 到達(dá)目的地后再將分組合并成報文交給目的終端或計算機(jī)。分組交換 技術(shù)在網(wǎng)絡(luò)設(shè)計中被廣泛采用用頂點表示通信設(shè)備，用邊表示通信鏈路，這樣得到一個圖。假 定該圖是完全圖，即任意兩

3、點間都有一條邊相連。在某些應(yīng)用場合， 頂點兩兩配對作為一個整體。我們希望保證在某些鏈路出故障不能使 用時，任兩對配對頂點間都至少有一條鏈路暢通無阻。設(shè)頂點xi,X2組成一對，yi,y2為一對，zi ,z2為一對，且故障發(fā)生 在諸如微波塔、中繼站等中間設(shè)施上。在此類設(shè)施上的故障將影響所 有共享該設(shè)施的鏈路。對共享同一個中間設(shè)施的鏈路，我們用同一種 顏色來標(biāo)記它們.如上圖表示一個有三種中間設(shè)施的通信網(wǎng)絡(luò)。在圖 中，若標(biāo)記紅色的中間設(shè)施出了故障 那么在頂點對Xi,X2和頂點對 Zi ,Z2之間將沒有可用的鏈路，而這對應(yīng)于下列事實：四條邊(Xi,Zj)構(gòu)成 一個單色的C4(4個頂點的回路)。一般來說，

4、設(shè)計一個網(wǎng)絡(luò)需決定中 間設(shè)施的數(shù)量以及哪個鏈路使用哪個設(shè)施。此外，在任何一個中間設(shè)施損壞時，我們希望所設(shè)計的網(wǎng)絡(luò)中任兩對配對頂點間有一個可使用 的鏈路。根據(jù)上面的討論，我們應(yīng)該避免出現(xiàn)單色的C4。已知Ramsey數(shù)R(C4,C4)=6。因此，如果只有兩個中間設(shè)施，那 么存在一個5個頂點的網(wǎng)絡(luò)使得可以安排一種不出現(xiàn)單色 C4的連接 方式。已知Ramsey數(shù)R(C4,C4,C4)=11所以存在一個10個頂點的網(wǎng)絡(luò)， 它使用三個中間設(shè)施且沒有單色的 C4。前面說過，設(shè)計一個網(wǎng)絡(luò)需要決定中間設(shè)施的數(shù)量以及哪個鏈路 使用哪個設(shè)施。中間設(shè)施是很昂貴的，因而希望使其數(shù)量盡可能少。 所以自然要問：如果有一個n

5、個頂點的網(wǎng)絡(luò)，在不出現(xiàn)單色 C4的條件 下中間設(shè)施的最少個數(shù)是多少？換句話說，滿足R(C4,C4,C4) >n的最 r小的r是多少？比如對上圖，n=6,由于R(C4,C4)=6, R(C4,C4,C4)=11 所以r=3，即我們需要3個中間設(shè)施。一般情況下，若n個頂點的圖的n(n-1)/2條邊分成r種顏色類，由 鴿巢原理，則必存在某個類至少有 血衛(wèi)2條邊。我們要選擇r使得r不存在包含有丄n3/2條邊的類，因此，選r使其滿足24n(n-1)/2.1 3/21v nnr 24就行，即滿足上述不等式的最小r就是所需要的最少中間設(shè)施數(shù)。第二節(jié)Ramsey定理在信息檢索中的應(yīng)用信息檢索是計算機(jī)科學(xué)

6、中一個基本而又重要的問題。 如何組織數(shù) 據(jù)，使用什么樣的查找方法對檢索的效率有很大的影啊。 我們所熟知 的在有序表結(jié)構(gòu)上的二分搜索算法是一種很有效的方法，但二分搜索 是最好的算法嗎？假設(shè)一個表有n個不同的項，其元素取自鍵空間M=1,2,，m.我們希望找到在表中存儲 M的任意n元子集S的方法，使得容易回 答下述詢問：x在S中嗎？如何存儲M的n元子集的規(guī)則稱為一個表結(jié) 構(gòu)或(m，n)-表結(jié)構(gòu)。最簡單的表結(jié)構(gòu)是有序表結(jié)構(gòu)，它是按上升序 列出S中的元素。更一般的是按置換排序的表結(jié)構(gòu)，它是固定1,2,n 的一個置換，根據(jù)此置換的次序列出S中的元素。信息檢索的計算復(fù)雜性依賴于表結(jié)構(gòu)和搜索策略。 復(fù)雜性的度

7、量 是最壞情形下確定x是否在S中所需要的詢問次數(shù)。例如，對于有序 表結(jié)構(gòu)，如果用二分搜索，所需要的詢問次數(shù)是 log2( n+1)。信息檢索的計算復(fù)雜性f(m, n)定義為所有可能的(m, n)-表結(jié)構(gòu)和搜索策略下的復(fù)雜性的最小值。關(guān)于f(m, n)我們有如下結(jié)論：定理1.對每個n,存在數(shù)N( n)使得f(m, n) = log2(n+1)對所有 m _N (n)成立。據(jù)此定理，對充分大的m,就信息檢索來說，用“有序表結(jié)構(gòu)”+ “二分搜索”是最有效的方法。利用下述兩個引理，可得此定理的證明引理1若m_2n- l , n _2,則對于按置換排序的表結(jié)構(gòu)，無論采 用何種策略，在最壞情形下要確定x是

8、否在S中至少需要log2(n+1)次檢查。引理2給定n，存在數(shù)N(n)滿足:當(dāng)m_N(n)，且給定一個(m, n)- 表結(jié)構(gòu)，則存在有2n-1個鍵的集合K,使得對應(yīng)于K的n元子集的表 形成按置換排序的表結(jié)構(gòu)。證明：設(shè)n個鍵的集合S=ji,j2,jn 以某種次序存放在表結(jié)構(gòu)中， 如果ji <j2< . <jn,且ji存放在表中第Ui項中，則S對應(yīng)1,2,n的置 換 Ui,U2,，Un。按置換排序的表結(jié)構(gòu)中，每個n鍵集都對應(yīng)同一置換。給定一個 (m,n)-表結(jié)構(gòu)，設(shè)(u1,U2,.,un)=S|S是n個鍵的集合且對應(yīng)的置換是Ui ,U2, ., Un。令 q1=q2= qt=2n

9、-1,t二n!又設(shè) N(n)是 Ramsey數(shù) r(q1,q2,.,q;n)。假設(shè) m_N (n)，我們把鍵 空間M的n元子集(有序)分成t=n!個部分，每一部分恰對應(yīng)一個 集合(u1,U2,.,un),其中的n元子集的對應(yīng)置換都是-(U1,U2,.,Un)，根據(jù) Ramsey數(shù) 心山2,.耳；n)的定義，存在某個i和M的某個q元子集(2n-1 元子集)K,K的所有n元子集都屬于某個 心山2,.也)。故引理2. 2成立。至此，利用Ramsey數(shù)證明了引理2。對一個給定的(m,n)-表結(jié)構(gòu) 和搜索策略以及mN (n),可找到滿足引理2的集合K，再由引理1, 即使限制在集合K上，在最壞情況下至少需要log 2(n+1)次檢查。因 而有f(m,n) logyn+1)。但我們知道有序表上的二分搜索的最壞