?
關鍵字搜索:
快速導航
Ramsey定理的使用
發布時間: 2019-06-16       瀏覽次數:次

  Ramsey定理的使用_天然科學_專業材料。這是Ramsey定理正在計較機方面的使用,很是有用

  定理正在收集規劃中 正在收集規劃中的使用 第一節 Ramsey 定理正在收集規劃中的使用 一、根本學問 定義 1. 給定正整數 n,r 和圖 H1,H2,…,Hr,用 r 種顏色對完 全圖 Kn 的所有邊進行著色,由第 i 色邊形成的子圖記為 Gi.若是存正在 一種著色方式,使得對所有的 i(1≤i≤r)都有 Hi ? Gi,則稱 Kn 對于(H1, H2,…,Hr)可 r-著色.若是 Hl ? H2 ? … ? Hr ? H,則簡稱 Kn 對于 H 可 r-著色. 定義 2. 使得 Kn 對于( K p , K p ,…, K p )不克不及 r-著色的最小正整數 n 1 2 r 稱 為 ( 經 典 )Ramsey 數 R( p1 , p2 ,..., pr ). 如 果 p1 = p2 =…= pr = p , 則 把 R( p1 , p2 ,..., pr )簡寫為 Rr(p). 定義 3. 使得 Kn 對于(H1,H2,…,Hr)不克不及 r-著色的最小正整數 n 稱為廣義 Ramsey 數 R(H1,H2,…,Hr).若是 Hl ? H2 ? … ? Hr ? H, 則把 R(Hl,H2,…,Hr)簡寫為 Rr(H). 定理 1. R(C4,C4)=6 定理 2. R(C4,C4,C4)=11 則它總包含 C4。 定理 3.若一個 n 個極點的圖至多有 n3 / 2 + n 條邊, 二、分組互換網的設想 分組互換網是采用分組互換手藝的收集, 它從終端或計較機領受 報文,把報文朋分成分組,并按某種策略選擇最佳徑正在網中傳輸, 達到目標地后再將分組歸并成報文交給目標終端或計較機。 分組互換 手藝正在收集設想中被普遍采用。 1 2 1 4 用極點暗示通信設備,用邊暗示通信鏈,如許獲得一個圖。假 定該圖是完全圖,即肆意兩點間都有一條邊相連。正在某些使用場所, 極點兩兩配對做為一個全體。 我們但愿正在某些鏈出毛病不克不及使 用時,任兩對配對極點間都至多有一條鏈通順無阻。 y1 x1 z1 x2 z2 y2 設極點 x1,x2 構成一對,y1,y2 為一對,z1 ,z2 為一對,且毛病發生 正在諸如微波塔、中繼坐等兩頭設備上。正在此類設備上的毛病將影響所 有共享該設備的鏈。對共享統一個兩頭設備的鏈,我們用統一種 顏色來標識表記標幟它們.如上圖暗示一個有三種兩頭設備的通信收集。正在圖 中,若標識表記標幟紅色的兩頭設備出了毛病.那么正在極點對 x1,x2 和極點對 z1 ,z2 之間將沒有可用的鏈,而這對應于下列現實:四條邊(xi,zj)形成 一個單色的 C4(4 個極點的回)。一般來說,設想一個收集需決定中 一般來說, 一般來說 間設備的數量以及哪個鏈利用哪個設備。 此外, 正在任何一個兩頭設 間設備的數量以及哪個鏈利用哪個設備。 此外, 施損壞時, 我們但愿所設想的收集中任兩對配對極點間有一個可利用 施損壞時, 的鏈。 的鏈。按照的會商,我們該當避免呈現單色的 C4。 已知 Ramsey 數 R(C4,C4)=6。因而,若是只要兩個兩頭設備,那 么存正在一個 5 個極點的收集使得能夠放置一種不呈現單色 C4 的毗連 體例。 已知 Ramsey 數 R(C4,C4,C4)=11,所以存正在一個 10 個極點的收集, 它利用三個兩頭設備且沒有單色的 C4。 前面說過, 設想一個收集需要決定兩頭設備的數量以及哪個鏈 利用哪個設備。兩頭設備是很高貴的,因此但愿使其數量盡可能少。 所以天然要問:若是有一個 n 個極點的收集,正在不呈現單色 C4 的前提 下兩頭設備的起碼個數是幾多?換句線 ) n 的最 r 小的 r 是幾多?好比對上圖,n=6,因為 R(C4,C4)=6,R(C4,C4,C4)=11 所以 r=3,即我們需要 3 個兩頭設備。 一般環境下, n 個極點的圖的 n(n-1)/2 條邊分成 r 種顏色類, 若 由 鴿巢道理,則必存正在某個類至多有 1 2 1 4 n(n - 1)/2 條邊。我們要選擇 r 使得 r 不存正在包含有 n3 / 2 + n 條邊的類,因而,選 r 使其滿腳 n(n - 1)/2 1 3 / 2 1 n + n r 2 4 滿腳上述不等式的最小 就是所需要的起碼兩頭設備數。 所需要的起碼兩頭設備數 就行,即滿腳上述不等式的最小 r 就是所需要的起碼兩頭設備數。 滿腳上述不等式 定理正在消息檢索中 消息檢索中的使用 第二節 Ramsey 定理正在消息檢索中的使用 消息檢索是計較機科學中一個根基而又主要的問題。 若何組織數 據,利用什么樣的查找方式對檢索的效率有很大的影啊。我們所熟知 的正在有序表布局上的二分搜刮算法是一種很無效的方式, 但二分搜刮 是最好的算法嗎? 假設一個表有 n 個分歧的項, 其元素取自鍵空間 M={1,2,...., m}. 我們但愿找到正在表中存儲 M 的肆意 n 元子集 S 的方式,使得容易回 答下述扣問:x 正在 S 中嗎?若何存儲 M 的 n 元子集的法則稱為一個表結 構或(m,n)-表布局。最簡單的表布局是有序表布局,它是按上升序 列出 S 中的元素。 更一般的是按置換排序的表布局, 它是固定{1,2,…,n} 的一個置換,按照此置換的次序列出 S 中的元素。 消息檢索的計較復雜性依賴于表布局和搜刮策略。 復雜性的懷抱 是最壞景象下確定 x 能否正在 S 中所需要的扣問次數。例如,對于有序 表布局,若是用二分搜刮,所需要的扣問次數是[log2(n+1)]。 消息檢索的計較復雜性 f(m,n)定義為所有可能的(m,n)-表布局 和搜刮策略下的復雜性的最小值。關于 f(m,n)我們有如下結論: 定理 1. 對每個 n,存正在數 N( n)使得 f(m,n)=[log2(n+1)]對所有 m ≥ N (n)成立。 據此定理,對充實大的 m,就消息檢索來說,用“有序表布局” +“二分搜刮”是最無效的方式。 操縱下述兩個引理,可得此定理的證明。 引理 1 若 m ≥ 2n- l , n ≥ 2,則對于按置換排序的表布局,無論采 用何種策略,正在最壞景象下要確定 x 能否正在 S 中至多需要[log2(n+1)] 次查抄。 存正在數 N(n)滿腳:當 m ≥ N(n), 且給定一個(m, n)引理 2 給定 n, 表布局,則存正在有 2n-1 個鍵的調集 K,使得對應于 K 的 n 元子集的表 構成按置換排序的表布局。 證明: n 個鍵的調集 S={j1,j2,…jn }以某種次序存放正在表布局中, 設 若是 j1 j2 ... jn,且 ji 存放正在表中第 ui 項中,則 S 對應 1,2,…,n 的置 換 u1,u2, ..., un。 按置換排序的表布局中,每個 n 鍵集都對應統一置換。給定一個 (m,n)-表布局,設 δ (u1, u2 ,...,un ) ={SS 是 n 個鍵的調集且對應的置換是 u1,u2, ..., un}。 令 q1=q2=…qt=2n-1,t=n! 又設 N(n)是 Ramsey 數 r(q1,q2,...,qt;n)。假設 m ≥ N (n),我們把鍵 空間 M 的 n 元子集(有序)分成 t=n!個部門,每一部門恰對應一個 調集 δ (u1, u2 ,...,un ) , 此中的 n 元子集的對應置換都是 δ (u1, u2 ,...,un ) ,按照 Ramsey 數 r(q1,q2,...,qk;n)的定義, 存正在某個 i 和 M 的某個 qi 元子集(2n-1 元子集)K,K 的所有 n 元子集都屬于某個 δ (u1, u2 ,...,un ) 。 故引理 2. 2 成立。 至此,操縱 Ramsey 數證了然引理 2。對一個給定的(m,n)-表布局 和搜刮策略以及 m ≥ N (n), 可找到滿腳引理 2 的調集 K, 再由引理 1, 即便正在調集 K 上,正在最壞環境下至多需要[log2(n+1)]次查抄。因 但我們曉得有序表上的二分搜刮的最壞景象 而有 f(m,n) ≥ [log2(n+1)]。 復雜性是[log2(n+1)],故有 f(m,n)=[log2(n+1)],這就證了然定理 1,從 而曉得二分搜刮對大的鍵空間是最好的檢索方式。 參考文獻: [1] A.C. Yao. Should Tables Be Sorted? J. ACM 28(1981),pp.615-628

?