拉姆齊法則_拉姆齊法則詳解（拉姆齊定理有哪些）?以下由小編為大家?guī)?lái)介紹。
1903年，弗蘭克·拉姆齊出生于英國(guó)倫敦，后來(lái)進(jìn)入劍橋大學(xué)三一學(xué)院學(xué)習(xí)數(shù)學(xué)，成為了一名杰出的數(shù)學(xué)家、哲學(xué)家和經(jīng)濟(jì)學(xué)家?？上於视⒉牛?930年就病逝于倫敦。但是在短短的歲月中，他
1903年，弗蘭克·拉姆齊出生于英國(guó)倫敦，后來(lái)進(jìn)入劍橋大學(xué)三一學(xué)院學(xué)習(xí)數(shù)學(xué)，成為了一名杰出的數(shù)學(xué)家、哲學(xué)家和經(jīng)濟(jì)學(xué)家。可惜天妒英才，1930年就病逝于倫敦。但是在短短的歲月中，他在數(shù)學(xué)和其它領(lǐng)域做出了許多貢獻(xiàn)。今天所要談?wù)摰氖撬?930年發(fā)表的論文《形式邏輯上的一個(gè)問(wèn)題》所提出來(lái)的拉姆齊定理。
拉姆齊定理(Ramsey Theorem)是圖論中的一個(gè)重要概念，它被表述為對(duì)于任一具有N個(gè)頂點(diǎn)的完全圖(complete graph)，所有的頂點(diǎn)之間可以用紅色或藍(lán)色的線條連接，圖中肯定會(huì)呈現(xiàn)出完全一致的大子集——要么全紅，要么全藍(lán)。我們也可以先通過(guò)確定一致子集的大小，再根據(jù)拉姆齊定理反推出能夠形成該子集所需的完全圖。
△ 完全圖是指所有頂點(diǎn)間兩兩相連構(gòu)成的圖。（圖片來(lái)源：Lucy
Reading-Ikkanda/QuantaMagazine）
拉姆齊定理還有一個(gè)簡(jiǎn)單易懂的版本叫“友誼定理”：六個(gè)人當(dāng)中至少有三個(gè)人相互認(rèn)識(shí)（朋友）或者相互不認(rèn)識(shí)（陌生人）。但為什么這個(gè)定理是正確的？為什么完全圖中的這些不同顏色的線條不能被完全打亂？數(shù)學(xué)家Jonathan Jedwab用一系列圖形直觀的解釋了這個(gè)定理為什么是正確的。
讓我們看一個(gè)簡(jiǎn)單的示例——一個(gè)六邊形的完全圖可以形成最少三條顏色一致的線組成的子集。這是為什么呢？
把這六個(gè)點(diǎn)看成六個(gè)人，其中任何一人與另一人必定處于認(rèn)識(shí)或者不認(rèn)識(shí)的狀態(tài)。若認(rèn)識(shí)，我們將二人用紅線連接；若不認(rèn)識(shí)，則用藍(lán)線連接。因此在這個(gè)社交小圈子中，每個(gè)人都輻射出五條線與其他五人相連，并且其中至少三條線的顏色相同。這意味著無(wú)論你怎樣連接這些人，結(jié)果一定會(huì)出現(xiàn)一個(gè)全紅或者全藍(lán)的三角形。
（圖片來(lái)源：QuantaMagazine）
首先我們來(lái)看1，從他身上發(fā)射出的五條線中，像之前說(shuō)過(guò)的至少有三條線顏色相同。假如他認(rèn)識(shí)2、4、5，則這三條線便是紅色。
（圖片來(lái)源：QuantaMagazine）
再看2和5，假如2和5相識(shí)，則2與5間的連線也是紅色，從而得到一個(gè)紅色的三角形。我們看看是否有方法避免這樣的三角形產(chǎn)生，所以假定2與5互不相識(shí)，并將2、5之間用藍(lán)色線條標(biāo)記。
（圖片來(lái)源：QuantaMagazine）
接下來(lái)再思考4和5的關(guān)系，同樣的，為了避免1、4、5形成紅色三角形，我們假設(shè)4、5也互不相識(shí)。
（圖片來(lái)源：QuantaMagazine）
最后考慮2和4的關(guān)系，結(jié)果發(fā)現(xiàn)不論2月4相識(shí)與否，都會(huì)形成一個(gè)紅色或藍(lán)色的三角形。于是一個(gè)單色的小色塊集合便會(huì)出現(xiàn)，拉姆齊定理得到印證。
（圖片來(lái)源：QuantaMagazine）
用這種方法研究更大的集合中樣本時(shí)，比如數(shù)百萬(wàn)、數(shù)千萬(wàn)、數(shù)億的人群，能看到組成的單色色團(tuán)由大量相同顏色的線段組合而成。但究竟這個(gè)“大量”有多大呢？數(shù)學(xué)家們并不能確定，在已知一個(gè)單色子集的大小前，我們無(wú)法知道形成它所需要的完全圖的最小大小。
拉姆齊定理也如其他許許多多日常使用的工具一樣——它相當(dāng)有用，但我們卻不盡了解其背后所有的工作原理。
