-
存在性定理
鎖定
存在性定理是一類定性描述。要把某種離散對象按某個確定的約束條件進行安排,如果這種特定的安排是否存在還不確定,就需要首先討論這種特定安排的存在性問題。
- 中文名
- 存在性定理
- 外文名
- existence theorem
- 適用範圍
- 數理科學
存在性定理簡介
存在性定理是一類定性描述。
要把某種離散對象按某個確定的約束條件進行安排,如果這種特定的安排是否存在還不確定,就需要首先討論這種特定安排的存在性問題。在經典組合數學中,霍爾定理、拉姆齊定理和狄爾沃斯定理是三個主要的存在性定理。
[1]
存在性定理內容
存在性定理霍爾定理
霍爾定理還有一個重要推論:二部圖G中的兩部分頂點組成的集合分別為X,Y, 若∣X∣=∣Y∣,且G中有一組無公共端點的邊,一端恰好組成X中的點,一端恰好組成Y中的點,則稱二部圖G中存在完美匹配。若圖G的每個點度數為t,則稱二部圖G為t-正則的二部圖存在完美匹配。
存在性定理拉姆齊定理
在組合數學上,拉姆齊(Ramsey)定理是要解決以下的問題:要找這樣一個最小的數n,使得n個人中必定有k個人相識或l個人互不相識。
6 個人中至少存在3人相互認識或者相互不認識。
該定理等價於證明這6個頂點的完全圖的邊,用紅、藍二色任意着色,必然至少存在一個紅色邊三角形,或藍色邊三角形。
存在性定理狄爾沃斯定理
(Dilworth's theorem)
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:3次歷史版本
- 最近更新: w_ou