本蒟蒻对于二分图一些定理的理解
先给出一些定理 (常识)
1.对于一个无向图 G，若 G 中的所有回路长度均为偶数，则G为一个二分图。
2.二分图的最小点覆盖 = 最大匹配数。
3.二分图的最大独立集 = n-最小点覆盖 = n-最大匹配数。
4.二分图中最小边覆盖 = 最大独立集
5.最大匹配数 = 左边匹配点 + 右边未匹配点。
一 二分图是什么
二分图又称作二部图，是图论中的一种特殊模型。 设 (G=(V,E)) 是一个无向图，如果顶点V可分割为两个互不相交的子集 ((A,B))，并且图中的每条边 (（i，j）) 所关联的两个顶点i和j分别属于这两个不同的顶点集 ((i in A,j in B))，则称图G为一个二分图。
以上内容摘自百度百科。
翻译成人话就是一张无向图，如果能将它的点集分为两个，且每个点集内部没有边相连，只有两点集间有边相连，那么它就是一个二分图。
二 二分图的判定
（1）证明
那么为啥说
1.对于一个无向图 (G)，若G中的所有回路长度均为偶数，则 (G) 为一个二分图。
我们有如下的证明：（以下内容参照百度百科）
不妨设两个点集分别为 (X) 和 (Y)
1.必要性
(ecause) 点集内部没有边
( herefore) 对于 (G) 中的一个长度为 (n) 的回路 (Z=(a_1,a_2,...a_n) (a_n==a_1)) 其顶点一定在 (X 和 Y) 中交替出现，所以点数一定为偶数。
又 (ecause Z) 为回路，所以其中每个点均连接两条边，即边数等于点数，所以边数为偶数。
2.充分性
现在我们有一个联通的无向图 (G=(V,E)(V为点集，E为边集)) ，且 (G) 中任意回路长度为偶数。那么我们证明其能分为两个点集，且点集内部无边。
我们从 (V) 中选出一个点 (V_0) ，然后我们设：
(X={v|v==v_0 || dis(v,v_0)&1==0})
(Y=V-X)
显然 (X) 不为空。又 (ecause |V| >= 2) 所以 有与 (v_0) 相连的点，所以 (Y) 不为空。
我们设边 ((u,v)) 的两点都在 (X) 中，那么 (dis(u,v_0)==dis(v,v_0)==2*k) 而 (dis(u,v)==1)，所以可以找到一个从 (v_0) 到 (v_0) 的奇数长度的回路，与题设矛盾。( herefore (u,v)) 不会都在 (X) 中。
同理设边 ((u,v)) 的两点都在 (Y) 中，那么 (dis(u,v_0)==dis(v,v_0)==2*k+1) 而 (dis(u,v)==1)，所以可以找到一个从 (v_0) 到 (v_0) 的奇数长度的回路，与题设矛盾。( herefore (u,v)) 不会都在 (Y) 中。
综上所述，原命题得证。
（2）算法
通过上面的论证，我们很容易得出一个判定二分图的算法（染色法）：
①任选一个点染色
②将所有与她相连的点染为相反的颜色
③若有一个点已经染色且与当前定点颜色相同，则G不为二分图
三 二分图的匹配
要提到后面四个定理的话，就必须说一说二分图的匹配。
（1）定义
对于 (G) 中的一个边的集合 (M) ，若M中的所有点均只与一条M中的一条边相连，则 (M) 为 (G) 的一个匹配，其中边数最大的 (M) 为二分图的最大匹配。
说人话：就是选出一些边，使得任意两边没有公共顶点。
（2）最大匹配
如题，就是匹配数最大的匹配。
<1> 求法
每次从一个未匹配点出发，走一条 非匹配边，匹配边...非匹配边的交错路，如果走到了一个未匹配点，那么就找到了一条增广路，将增广路上的匹配边与非匹配边互换，则匹配数加一。
2.最大流
从S向左边的点连一条流量为1的边，左边的点向右边连容量为1的边，右侧的点向T连一条1的边，那么跑出来的最大流为最大匹配数。
<2> 性质
2.二分图的最小点覆盖 = 最大匹配数。
3.二分图的最大独立集 = n-最小点覆盖 = n-最大匹配数。
5.最大匹配数 = 左边匹配点 + 右边未匹配点。
四 蒟蒻关于先前定理的理解
以下内容参照这篇文章
开始前先讲一下概念：
1.最大匹配：见前方二分图的匹配。
2.最小点覆盖：用最少的点，让图中每条边都至少和其中一个点关联。
3.最大独立集：从图中选出一些点，使得其两两间无边的所能选出的最多的点。
4.最小边覆盖：用尽量少的不相交简单路径覆盖有向无环图(DAG)(这里是二分图) G 的所有顶点。
定理1：
对于一个无向图 (G)，若 (G) 中的所有回路长度均为偶数，则 (G) 为一个二分图。
见前方二分图的判定。
定理2：
二分图的最小点覆盖 = 最大匹配数。