匈牙利算法详解
Hall定律 通俗易懂？
匈牙利算法得到的结果是稳定的吗？
Hall定理是二分图匹配问题中匈牙利算法的基础。
中文名
Hall定理
适用领域范围
X中的任意k个点至少与Y中的k个点相邻
适用领域范围
二分图匹配问题
推导结论
匈牙利算法
Hall定理：
此定理使用于组合问题中，二部图G中的两部分顶点组成的集合分别为X, Y, X={X1, X2, X3,X4,.........,Xm}, Y={y1, y2, y3, y4 ,.........,yn},G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：
X中的任意k个点至少与Y中的k个点相邻。（1≤k≤m)
本论还有一个重要推论：
二部图G中的两部分顶点组成的集合分别为X,Y, 若∣X∣=∣Y∣,且G中有一组无公共端点的边，一端恰好组成X中的点，一端恰好组成Y中的点，则称二部图G中存在完美匹配。若图G的每个点度数为t，则称二部图G为t---正则的二部图存在完美匹配。
图论基础知识定理？
我觉得完全可以零基础入门，很多内容并未要求额外的知识能力。我自己证明过的定理中，有些证明非常长，但其实就是反证加归纳，只不过可能嵌套几层，看上去很复杂。著名如七桥问题的证明，好像也是除了推理再无其他，并无中学以上的知识点。我认为只需逻辑思维过硬，静得下心，就可以学好图论。 另一方面，图论研究数学对象及其关系，这样的定位使得图论和整个数学都扯得上关系。因此如果要深入，代数几何拓扑组合都需要一定了解。
图论基础知识定理？
Konig定理
首先，为什么这样得到的点集点的个数恰好有M个呢？其次，为什么这样得到的点集可以覆盖所有的边呢？最后，为什么这是最小的点覆盖集呢？
Konig定理
这是图论中很重要的一个定理，于1913年 由匈牙利数学家柯尼希（D.Konig）首先陈述此定理。
定理的内容是：在0-1矩阵中，1的最大独立集合最小覆盖包含的元素个数相同，等价地，二分图中的最大匹配数等于这个图中的最小点覆盖数。
证明
假如我们已经通过匈牙利算法求出了最大匹配（假设它等于M），下面给出的方法可以告诉我们，选哪M个点可以覆盖所有的边。
匈牙利算法需要我们从右边的某个没有匹配的点，走出一条使得“一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现”的路（交错轨，增广路）。但是，现在我们已经找到了最大匹配，已经不存在这样的路了。换句话说，我们能寻找到很多可能的增广路，但最后都以找不到“终点是还没有匹配过的点”而失败。我们给所有这样的点打上记号：从右边的所有没有匹配过的点出发，按照增广路的“交替出现”的要求可以走到的所有点（最后走出的路径是很多条不完整的增广路）。那么这些点组成了最小覆盖点集。
首先，为什么这样得到的点集点的个数恰好有M个呢？答案很简单，因为每个点都是某个匹配边的其中一个端点。如果右边的哪个点是没有匹配过的，那么它早就当成起点被标记了；如果左边的哪个点是没有匹配过的，那就走不到它那里去（否则就找到了一条完整的增广路）。而一个匹配边又不可能左端点是标记了的，同时右端点是没标记的（不然的话右边的点就可以经过这条边到达了）。因此，最后我们圈起来的点与匹配边一一对应。
其次，为什么这样得到的点集可以覆盖所有的边呢？答案同样简单。不可能存在某一条边，它的左端点是没有标记的，而右端点是有标记的。原因如下：如果这条边不属于我们的匹配边，那么左端点就可以通过这条边到达（从而得到标记）；如果这条边属于我们的匹配边，那么右端点不可能是一条路径的起点，于是它的标记只能是从这条边的左端点过来的（想想匹配的定义），左端点就应该有标记。
最后，为什么这是最小的点覆盖集呢？这当然是最小的，不可能有比M还小的点覆盖集了，因为要覆盖这M条匹配边至少就需要M个点（再次回到匹配的定义）。
对两侧添加源汇点后可以从最小割最大流的角度理解。
在原图上对所有的边的左结点和右结点连一条容量无穷大的流（从左结点到右结点），然后再添加源汇顶点，对源点到每个左顶点添加容量为1的流，对每个右顶点到汇点添加容量为1的流。
易知，最大流即为最大匹配数。
我们来研究所有的割，我们将所有左顶点划为A1,A2两部分，右顶点划为B1,B2两部分，并研究从S并A1并B2到T并A2并B1这个割的最小取法（这个划分方式包含了所有可能的割），如若左顶点P到右顶点Q有边，那么最小割中显然不会有“P属于A1且Q属于B1”成立（否则就这一条边割出来就是无穷大，肯定不是最小割），于是最小割中所有的边PQ必满足“P属于A2或Q属于B2”，换句话说，A2，B2中所有顶点组成这个二分图的一个点集覆盖。
下面观察，我们易知，再最小割中，总的割必然等于S到A2的 B2到T的（这些是最小割中所有可能的边了）。而S到A2 B2到T就是A2，B2中所有顶点的个数总和，所以最小割就是满足题意（A2并B2构成最小点集覆盖）的A2并B2中顶点最少的情况，亦即最小点集覆盖，于是乎：
最大匹配数=最大流=最小割=最小点集覆盖