霍尔定理

霍尔定理，此定理用在组合数学中，又称霍尔婚配定理，由飞利浦· 霍尔于1935年证明。

霍尔定理简述霍尔定理： **此定理使用于组合问题中；**二部图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---正则的二部图存在完美匹配。 本定理是二分图匹配问题中匈牙利算法的基础。

霍尔定理详解设给定任意集合S和S的子集的任意有限系(1):

子集系(1)的相异代表元的一个完全集[complete set of distinet representatives，简记为C.D.R.——这是霍尔的原始用语，后来的文献一般称为相异代表系(system of distinet representatives)，简记为SDR]是指S的m个相异元素的一个集合: ，使得对于每个 ，有英国数学家霍尔(P.Hall，1904——1982)在1935年发表的“论子集的代表元中指出：“为使(1)存在一个C.D.R.，则下面的条件是充分的，即对每个 ，任意选取(1)的k个集合，其中都将包含至少k个S的元素.”由于此前霍尔已经指出该条件的必要性是显然的，因此他给出的实际上是一个充要条件。至于以图论术语表述的霍尔定理，则可以在贝尔热的《图的理论及其应用》(1955)中找到原型：“(设G是一个具有二分部(X，Y)的二部图，R(A)表示 时Y中与A的至少一个点相邻接的点的集合，)X能被匹配到y当且仅当对于所有的集合 有 。”1

霍尔定理有时也被人们称为“婚配定理”，因为它对于美国数学家哈尔莫斯(P.R.Halmos，1916一2006)和法乌甘(H.E.vaughan)在“婚配问题”(1950)一文中所表述的如下问题：“假设一批小伙儿中的每一位都与一定数目的姑娘相识，问在什么条件下每位小伙儿都能与他认识的一位姑娘结婚？”提供了解答，即必须要使任意一组无个小伙儿认识至少k个姑娘.因此霍尔定理的条件有时也被称为“婚配条件”.然而“婚配问题”的提法最早却出自德国数学家外尔(H.Weyl，1885一1955)的一篇文章。1

“婚配定理”这一名称也常被赋予属于柯尼希四的下述定理：“每个正则二部图都具有一个一度因子；每个k度正则二部图都可分离出k个一度因子。”它们可作为霍尔定理的推论。这时相应的婚配问题也常以“跳舞问题”的面目出现：“设有n个男孩和n个女孩的一次聚会，每个男孩恰好认识其中的k个女孩，每个女孩也恰好认识其中的k个男孩.间有没有可能使他们跳舞时都与彼此认识的人结成舞伴?’’上述推论对此给出了肯定的回答。1

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所