存在性定理是一類定性描述。要把某種離散對(duì)象按某個(gè)確定的約束條件進(jìn)行安排，如果這種特定的安排是否存在還不確定，就需要首先討論這種特定安排的存在性問(wèn)題。
在經(jīng)典組合數(shù)學(xué)中，霍爾定理、拉姆齊定理和狄爾沃斯定理是三個(gè)主要的存在性定理。
內(nèi)容
霍爾定理
霍爾定理使用于組合問(wèn)題中；二部圖G中的兩部分頂點(diǎn)組成的集合分別為X, Y, ， ，G中有一組無(wú)公共點(diǎn)的邊，一端恰好為組成X的點(diǎn)的充分必要條件是：X中的任意k個(gè)點(diǎn)至少與Y中的k(1≤k≤m)個(gè)點(diǎn)相鄰。
霍爾定理還有一個(gè)重要推論：二部圖G中的兩部分頂點(diǎn)組成的集合分別為X,Y, 若∣X∣=∣Y∣,且G中有一組無(wú)公共端點(diǎn)的邊，一端恰好組成X中的點(diǎn)，一端恰好組成Y中的點(diǎn)，則稱二部圖G中存在完美匹配。若圖G的每個(gè)點(diǎn)度數(shù)為t，則稱二部圖G為t-正則的二部圖存在完美匹配。
本定理是二分圖匹配問(wèn)題中匈牙利算法的基礎(chǔ)。
拉姆齊定理
在組合數(shù)學(xué)上，諾曼·拉姆齊(Ramsey)定理是要解決以下的問(wèn)題：要找這樣一個(gè)最小的數(shù)n，使得n個(gè)人中必定有k個(gè)人相識(shí)或l個(gè)人互不相識(shí)。
6 個(gè)人中至少存在3人相互認(rèn)識(shí)或者相互不認(rèn)識(shí)。
該定理等價(jià)于證明這6個(gè)頂點(diǎn)的完全圖的邊，用紅、藍(lán)二色任意著色，必然至少存在一個(gè)紅色邊三角形，或藍(lán)色邊三角形。
狄爾沃斯定理
(Dilworth's theorem)
狄爾沃斯定理亦稱偏序集分解定理，是關(guān)于偏序集的極大極小的定理，該定理斷言：對(duì)于任意有限偏序集，其最大反鏈中元素的數(shù)目必等于最小鏈劃分中鏈的數(shù)目。此定理的對(duì)偶形式亦真，它斷言：對(duì)于任意有限偏序集，其最長(zhǎng)鏈中元素的數(shù)目必等于其最小反鏈劃分中反鏈的數(shù)目，由偏序集P按如下方式產(chǎn)生的圖G稱為偏序集的可比圖：G的節(jié)點(diǎn)集由P的元素組成，而e為G中的邊，僅當(dāng)e的兩端點(diǎn)在P中是可比較的，有限全序集的可比圖為完全圖。
參考資料 >