拉姆齊數

拉姆齊數(Ramsey number)是圖論的重要函式之一，它是一個以兩個正整數作為變數的函式。拉姆齊數是拉姆齊定理的重要參數。

在組合數學上， 拉姆齊（Ramsey）定理是要解決以下的問題：要找這樣一個最小的數n ，使得n個人中必定有k個人相識或l個人互不相識。

這個定理以弗蘭克·普倫普頓·拉姆齊命名， 1930年他在論文On a Problem in Formal Logic （《形式邏輯上的一個問題》）證明了R(3,3)=6。

基本介紹

• 中文名：拉姆齊數
• 外文名：Ramsey number
• 領域：數學
• 提出者：弗蘭克·普倫普頓·拉姆齊
• 意義：圖論的重要函式之一
• 常用表達：r(m,n)

簡介

拉姆齊數(Ramsey number)是圖論的重要函式之一。它是一個以兩個正整數作為變數的函式。設m和n為正整數。所謂拉姆齊數，常用r(m ,n)表示，是指符合一定條件的p(圖的階數)的最小值。任何一個p階的圖G，若不含完全圖Km作為一個子圖，則必有一個含n個節點的獨立集。一個(m,n)拉姆齊圖是指階為r(m,n)-1，既不含m個節點的完全圖作為子圖，也不含n個節點的獨立集的圖。設k1,k2,...,kq是q個正整數，所謂廣義拉姆齊數r(k1,k2,.. ,kq)，是指符合下列條件的p的最小值：對於p階完全圖Kp，用q種色(cl,c2,...cq)對Kp的邊任意著色，則存在某一色ci，所有著這一種色的邊的導出子圖包含Kki作為一子圖。對於正整數m,n，所謂邊拉姆齊數rl(m,n)，就是指符合如下條件的p的最小值：對於任何一個p階的圖，其上必有m條邊兩兩互不相鄰，或有n條邊以同一節點為端點。關於r(m,n)的存在性，是由拉姆齊(Ramsey , F. P.)首先給出的。

圖論

圖論〔Graph Theory〕是數學的一個分支。它以圖為研究對象。圖論中的圖是由若干給定的點及連線兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關係，用點代表事物，用連線兩點的線表示相應兩個事物間具有這種關係。

圖G=（V,E）是一個二元組（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。為了避免符號上的混淆，我們總是默認V∩B=Ø。集合V中的元素稱為圖G的定點（或節點、點），而集合E的元素稱為邊（或線）。通常，描繪一個圖的方法是把定點畫成一個小圓圈，如果相應的頂點之間有一條邊，就用一條線連線這兩個小圓圈，如何繪製這些小圓圈和連線時無關緊要的，重要的是要正確體現哪些頂點對之間有邊，哪些頂點對之間沒有邊。

圖論本身是套用數學的一部份，因此，歷史上圖論曾經被好多位數學家各自獨立地建立過。關於圖論的文字記載最早出現在歐拉1736年的論著中，他所考慮的原始問題有很強的實際背景。

定義

拉姆齊數，用圖論的語言有兩種描述：

對於所有的N頂圖，包含k個頂的團或l個頂的獨立集。具有這樣性質的最小自然數N就稱為一個拉姆齊數，記作R(k,l)；

在著色理論中是這樣描述的：對於完全圖Kn的任意一個2邊著色(e1,e2)，使得Kn[e2]中含有一個k邊形，Kn[e1]含有一個l邊形，則稱滿足這個條件的最小的n為一個拉姆齊數。（注意：Ki按照圖論的記法表示i階完全圖）

拉姆齊證明，對與給定的正整數數k及l，R(k,l)的答案是唯一和有限的。

拉姆齊數亦可推廣到多於兩個數：

對於完全圖Kn的每條邊都任意塗上r種顏色之一，分別記為 e1,e2,e3,...,er ，在Kn中，必定有個顏色為e1的l1邊形，或有個顏色為e2的l2邊形……或有個顏色為er的lr邊形。符合條件又最少的數n則記為R(l1,l2,l3,...,lr;r)。

拉姆齊數的數值或上下界

已知的拉姆齊數非常少，保羅·艾狄胥曾以一個故事來描述尋找拉姆齊數的難度：“想像有隊外星人軍隊在地球降落，要求取得R(5,5)的值，否則便會毀滅地球。在這個情況，我們應該集中所有電腦和數學家嘗試去找這個數值。若它們要求的是R(6,6)的值，我們要嘗試毀滅這班外星人了。”

顯然易見的公式：

1°R(1,s)=1

2°R(2,s)=sR(l1,l2,l3,...,lr;r)=R(l2,l1,l3,...,lr;r)=R(l3,l1,l2,...,lr;r) （將li的順序改變並不改變拉姆齊的數值）

R(3,3)等於6的證明

證明：在一個K6的完全圖內，每邊塗上紅或藍色，必然有一個紅色的三角形或藍色的三角形。

• 任意選取一個端點P ，它有5條邊和其他端點相連。
• 根據鴿巢原理，5條邊的顏色至少有3條相同，不失一般性設這種顏色是紅 色。
• 在這3條邊除了P以外的3個端點，它們互相連結的邊有3條。
• 若這3條邊中任何一條是紅色，這條邊的兩個端點和P相連的2邊便組成一個紅色三角形。
• 若這3條邊中任何一條都不是紅色，它們必然是藍色，因此，它們組成了一個藍色三角形。
• 而在K5內，不一定有一個紅色的三角形或藍色的三角形。 每個端點和毗鄰的兩個端點的線是紅色，和其餘兩個端點的連線是藍色即可。這個定理的通俗版本就是友誼定理。

一個圖集對完全圖的拉姆齊數

本文中的圖都是指簡單圖。用G表示一個圖，Kn表示一個n階完全圖。拉姆齊數r（G，Kn）表示滿足如下條件的最小正整數N：當用紅藍兩種顏色給N階完全圖著色時，要么紅色圖中含有G，要么藍色圖中含有Kn。設C表示一個圈圖集，拉姆齊數r（C，Kn）表 示 滿 足 如 下 條 件 的 最 小 正 整 數N：若圖F是一個N階圖，則圖F至少含有C的一個元素，或者F含有Kn。圖Kk+C是指：頂點集由Kk和C的頂點組成，邊集由Kk和C的所有邊，另外還有連線Kk和C的頂點之間的所有邊組成。

拉姆齊定理定義

在組合數學上，拉姆齊(Ramsey)定理是要解決以下的問題：要找這樣一個最小的數n，使得n個人中必定有k個人相識或l個人互不相識。

拉姆齊定理的通俗表述：

6 個人中至少存在3人相互認識或者相互不認識。

該定理等價於證明這6個頂點的完全圖的邊，用紅、藍二色任意著色，必然至少存在一個紅色邊三角形，或藍色邊三角形。

註：這個定理以弗蘭克·普倫普頓·拉姆齊命名，1930年他在論文On a Problem in Formal Logic[2]（《形式邏輯上的一個問題》）證明了R(3,3)=6。