Hall定理(霍尔定理)证明及推广

引言

网络上有许多Hall定理的证明，但是对于Hall定理的几个推广的介绍却少之又少，因此本文来简单介绍一下

注：为了使这篇文章看起来简单易懂，本文将不会使用图论语言，会图论的朋友们可以自行翻译为图论语言。

背景：

在遥远的地方有一个神奇国家，这个国家有n个男生和m个女生（n  m）。每个男生都喜欢着若干个女生(注：这个国家不存在基佬，即男生不能喜欢男生)，现在男生们希望每位男生都可以找到一位自己喜欢的女生作为女朋友（注：不能与他人共享女朋友）。

1. 霍尔定理

霍尔定理声称每位男生都可以找到一位自己喜欢的女生作为女朋友当且仅当从这n个男生中任取若干个男生（不妨为k个）都有 至少被他们中1个男生喜欢的女生数量大于等于k人。

霍尔定理证明：

1）必要性：必要性是显然的：如果k个男生喜欢的女生总共只有小于等于k-1个，那么显然一定至少有一个可怜鬼找不到女朋友

2）充分性：下对男生个数n归纳证明霍尔定理的充分性成立。

n=1时显然成立，若小于n时均成立，n时：

如果任取若干个男生（不妨为k个（k不等于n））都有 至少被他们中1个男生喜欢的女生数量大于等于k+1人

那么我们将随便一个男生与一个他喜欢的女生组为男女朋友，之后将他们去掉。不难发现剩下的人依旧满足霍尔定理的条件但此时男生只剩下n-1个，由归纳假设知：成立

如果存在若干个男生（不妨为k个（k不等于n））满足至少被他们中1个男生喜欢的女生数量恰好为k人

那么由归纳假设知：这k个男生与k个女生可以组为k对男女朋友，将这k对男女朋友去掉。不难发现剩下的人依然满足霍尔定理条件（如果有若干的男生不满足，那么这些男生与去掉的那k个男生在初始时就不满足条件），由归纳假设知：成立。

综上，n时成立，所以霍尔定理的充分性成立。

证毕。

2. 霍尔定理-加强1

然而现实是残酷的，不可能每个人都能找到属于自己的女朋友，因此男生们希望最多有a（a<n）个人找不到自己的女朋友，那么此时的充要条件又是什么呢？

霍尔定理-加强1 声称：最多可以有a个男生找不到自己的女朋友当且仅当从这n个男生中任取若干个男生（不妨为k个）都有 至少被他们中1个男生喜欢的女生数量大于等于k-a人。

霍尔定理-加强1 证明：

1）必要性：必要性依旧是显然的，如果k个男生喜欢的女生总共只有小于等于k-a-1个，那么显然一定至少有a+1个可怜鬼找不到女朋友

2）充分性：充分性的证明与霍尔定理充分性的证明基本相同，还是对男生个数n归纳证明。

n=a,a+1时显然成立，若小于n时均成立，n时：

如果任取若干个男生（不妨为k个（k不等于n））都有 至少被他们中1个男生喜欢的女生数量大于等于k-a+1人

那么我们将随便一个男生与一个他喜欢的女生组为男女朋友，之后将他们去掉。不难发现剩下的人依旧满足霍尔定理-加强1的条件但此时男生只剩下n-1个，由归纳假设知：成立

如果存在若干个男生（不妨为k个（k不等于n））满足至少被他们中1个男生喜欢的女生数量恰好为k-a人

那么由归纳假设知：这k个男生与k-a个女生可以组为k-a对男女朋友（有a个可怜鬼找不到女朋友），将这k个男生与k-a个女生去掉。不难发现剩下的人满足霍尔定理条件（注意是霍尔定理不是霍尔定理-加强1）（如果有若干的男生不满足，那么这些男生与去掉的那k个男生在初始时就不满足条件），由霍尔定理知：成立。

综上，n时成立，所以霍尔定理-加强1的充分性成立。

3. 霍尔定理-加强2

为了更加深入了了解这个国家（大雾） 我们穿越到了古代，在古代这个国家还是有n个男生与m个女生，只不过这时候男生们的标配不再是1个女朋友了，他们需要1位妻子与4位小妾（大大雾） ，男生们希望每位男生都可以找到五位自己喜欢的女生作为女朋友（注：不能与他人共享女朋友）。那么此时的等价条件又是什么呢？

霍尔定理-加强2声称：每位男生都可以找到五位自己喜欢的女生作为女朋友当且仅当从这n个男生中任取若干个男生（不妨为k个）都有 至少被他们中1个男生喜欢的女生数量大于等于5*k人。

霍尔定理-加强2 证明：

众所周知，数学家喜欢把未知的问题化归为已知的问题，那么这个问题该怎么化归呢？

很显然我们需要穿越回近代来考虑这个问题。在近代找1位妻子与4位小妾是犯法的，因此这些男生被五马分尸了（太可怜了），每一位男生都被分为了5块（太太可怜了），每个男生的5块尸首分别被他的5个女朋友保存着。诶？等等，你发现了什么？这不就是霍尔定理吗？只不过从男生找女朋友变为了男生的尸首找女朋友（尸首还能找女朋友？？？），在古代每个男生能找到5位女朋友等价于在近代他的每个尸首都能找到1位女朋友（害怕）因此由霍尔定理他的等价条件就是从5n个尸首中任取若干个（不妨为k个） 都有：至少被他们中1个尸首的主人喜欢的女生数量大于等于k个，而显然的这等价于从这n个男生中任取若干个男生（不妨为k个）都有 至少被他们中1个男生喜欢的女生数量大于等于5*k人。于是霍尔定理-加强2就被我们证完了（神奇吧！）

霍尔定理-加强2 推广：

在古代也是有阶级之分的，每个人的需求也是不同的，如果第i个男生希望找r(i)个女朋友那么此时的等价条件又是什么呢？

很容易猜到第i位男生都可以找到r(i)位自己喜欢的女生作为女朋友当且仅当从这n个男生中任取若干个男生（不妨为k个）都有 至少被他们中1个男生喜欢的女生数量大于等于S人，其中S为这k个男生的r(i)之和。