Ramsey定理的應(yīng)用

1、精品文檔第一節(jié)ramsey定理在網(wǎng)絡(luò)規(guī)劃中的應(yīng)用一、基礎(chǔ)知識定義1.給定正整數(shù)n, r和圖hi, h2,，hr,用r種顏色對完 全圖kn的所有邊進行著色，由第i色邊構(gòu)成的子圖記為gi.如果存在 一種著色方法，使得對所有的i(1wgr)都有hi gi,則稱kn對于(hi, h2,，hr)可r 著色.如果hl h2hr h,則簡稱kn對于h可 r 一著色.定義2.使得kn對于(kpi，kp2,，kpr)不能r著色的最小正整數(shù)n 稱為(經(jīng)典)ramsey 數(shù) r( pi,p2,pr).如果 pi= p2= = pr= p,則把 r( pi, p2,., pr)簡寫為 rr(p).定義3.使得kn對于

2、(hi, h2,，hr)不能r 著色的最小正整數(shù) n 稱為廣義 ramsey 數(shù) r(hi, h2,，hr).如果 hi h2 hr h, 則把r(hl, h2,，hr)簡寫為rr(h).定理 i. r(c4,c4)=6定理 2. r(c4,c4,c4)=ii定理3.若一個n個頂點的圖至少有-n3/21n條邊，則它總包含 24c4。二、分組交換網(wǎng)的設(shè)計分組交換網(wǎng)是采用分組交換技術(shù)的網(wǎng)絡(luò)，它從終端或計算機接收 報文，把報文分割成分組，并按某種策略選擇最佳路徑在網(wǎng)中傳輸， 到達目的地后再將分組合并成報文交給目的終端或計算機。分組交換 技術(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è)施出了故障.那么在頂點對xl,x2和頂點對 z1 ,z2之間將沒有可用的鏈路，而這對應(yīng)于下列事實：四條邊(xi,zj)構(gòu)成

4、 一個單色的c4(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è)施是很昂貴的，因而希望

5、使其數(shù)量盡可能少。 所以自然要問：如果有一個n個頂點的網(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種顏色類,由鴿巢原理，則必存在某個類至少有 血-些條邊。我們要選擇 r得不存在包含有2n3/2 :n條邊的類，因此，選r使其滿足就行，即滿足上述不等式的最小r就是所需要的最少中間設(shè)施數(shù)。第二節(jié) ramsey 定理在信息檢索中的應(yīng)用信息檢索是計算機科學(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ù)是 log 2(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) = log 2(n+1)對所有 m n (n) 成立。據(jù)此定理，對充分大的 m ，就信息檢索來說，用“有序表結(jié)構(gòu)”“二分搜索”是最有效的方法。利用下述兩個引理,可得此定理的證明。引理 1 若 m 2n- l , n 2 ，則對于按置換排序的表結(jié)構(gòu)，無論采用何種

8、策略，在最壞情形下要確定x 是否在 s 中至少需要log 2(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=j 1,j2/ jn 以某種次序存放在表結(jié)構(gòu)中， 如果ji j2 . j n,且ji存放在表中第ui項中，則s對應(yīng)1,2,n的 置換 u 1,u 2, ., un 。按置換排序的表結(jié)構(gòu)中， 每個 n 鍵集都對應(yīng)同一置換。 給定一個(m,n)- 表結(jié)構(gòu)，設(shè)(u1,u2,.,un) =s|s 是 n 個鍵的集合且對應(yīng)

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