[科普中国]-存在性定理

存在性定理是一类定性描述。要把某种离散对象按某个确定的约束条件进行安排，如果这种特定的安排是否存在还不确定，就需要首先讨论这种特定安排的存在性问题。

简介存在性定理是一类定性描述。

要把某种离散对象按某个确定的约束条件进行安排，如果这种特定的安排是否存在还不确定，就需要首先讨论这种特定安排的存在性问题。在经典组合数学中，霍尔定理、拉姆齐定理和狄尔沃斯定理是三个主要的存在性定理。1

内容霍尔定理**霍尔定理****使用于组合问题中；**二部图G中的两部分顶点组成的集合分别为X, Y, ， ，G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：X中的任意k个点至少与Y中的k(1≤k≤m)个点相邻。

****霍尔定理**还有一个重要推论：**二部图G中的两部分顶点组成的集合分别为X,Y, 若∣X∣=∣Y∣,且G中有一组无公共端点的边，一端恰好组成X中的点，一端恰好组成Y中的点，则称二部图G中存在完美匹配。若图G的每个点度数为t，则称二部图G为t-正则的二部图存在完美匹配。

本定理是二分图匹配问题中匈牙利算法的基础。

拉姆齐定理在组合数学上，拉姆齐(Ramsey)定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。

6 个人中至少存在3人相互认识或者相互不认识。

该定理等价于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形。

狄尔沃斯定理(Dilworth's theorem)

狄尔沃斯定理亦称偏序集分解定理，是关于偏序集的极大极小的定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真，它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目，由偏序集P按如下方式产生的图G称为偏序集的可比图：G的节点集由P的元素组成，而e为G中的边，仅当e的两端点在P中是可比较的，有限全序集的可比图为完全图。

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学