Hall定理的证明

本文主要是介绍Hall定理的证明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、Hall定理的证明

（1）内容：

对于一个具有二部划分（X,Y）的二部图，饱和X的每个顶点的匹配存在的充要条件是对于任意一个X的子集S，都有|N(S)|>=|S|。

（2）理解：

1. 对象：二部图
2. 希望找到一个能够饱和X每个顶点的匹配，即找个一个边不重的边子集用上X中的每个顶点。
3. 对应的充要条件是，对于任意一个X的子集S，S的领域的顶点个数要大于S中顶点的个数。比如，当S=X时，就是要求与X相邻的顶点个数要多于X中顶点的个数。同样的，当任意一个S都满足这样的要求时，就能够找到匹配完X中所有顶点的匹配。

（3）证明

必要性：显然。

充分性：反证法。

1. 假设最大匹配M‘不饱和X中的所有顶点，则存在一个不饱和点u属于X。

2. 构造一个顶点集Z，Z中包含了所有通过最大匹配M’的交错路与u相连接的顶点。

3. S=Z交X，T=Z交Y。

   1. 若u是孤立点，则｜S｜=1，｜N(S)｜=0，显然矛盾
   2. 如果u不是孤立点，则Y中存在与u相连的点v，且在M‘中v被X中的其他某个顶点s匹配了，且Y中不存在不饱和点t与s相连，否则存在M’增广路u->v->s->t，即M‘不是最大匹配。因此u是Z中唯一的M‘不饱和点。

4. 显然S\{u}与T中配对（交错路），即｜T｜=｜S｜-1=｜N(S)｜,矛盾。所以充分性得证

这篇关于Hall定理的证明的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---