二分图（2粉兔）
以下为随便写的总结，也许应该不严谨二分图定义等
定义：可以分成两个部分使得每一条边的两个点都是不同部分的图是2粉兔。
总结：没有奇环
所以我们可以用染色大法，在连通块内随便找个点染 1 号颜色，然后它连的点都染 2 号颜色，以此类推。每个连通块都染完以后染 1 号颜色的扔到一个部分，染 2 号颜色的扔到另外一个部分。
匹配
定义：
选一些边使得任意两条边都没有公共点（书上定义是图中两两没有公共端点的边构成的边集 \(M\)，若满足 \(M\subseteq E\)，则称为匹配）
匹配点：有匹配边依附的点
（在二分图中↓）
最大匹配：选边最多的匹配
完全匹配：选边个数 \(=\) 点数 \(/2\)（全是匹配点）
最佳匹配：如果每条边带权，则权值和最大的匹配是最佳匹配
最佳完备匹配：权值和最大的完全匹配
增广路：起点终点为非匹配点，路径是非匹配边和匹配边交替的路径
性质：
1.长度为奇数
2.匹配的边集 xor 增广路边集 是比原本匹配边数 \(+1\) 的匹配
3.当一个匹配没有增广路时它就是最大匹配
证明：必要性：一眼丁真
充分性：设 \(M\) 是没有增广路的匹配，\(M'\) 是最大匹配，\(H=(V,M xor M')\)，由 xor 定义得知 \(H\) 中属于 \(M'\) 的边比 \(M\) 多
由匹配的定义得知 \(H\) 中连通块一定是一条链，而且是 \(M\) 的边 和 \(M'\) 的边 交替。
一定有一个连通块 \(M'\) 的边 \(>M\) 的边。
可以发现把这个连通块的 \(M\) 边都换成 \(M'\) 边没有冲突，反证可得，所以有增广路。
算法：
1.匈牙利算法
总结：一直找增广路
流程：先增加一个点，然后沿着 非匹配边-匹配边 的路径走，如果碰到非匹配点直接修改点集
可以发现每个点被遍历一次就好了，多遍历几次不会改变结果，于是打个标记时间复杂度就没问题了
因为加 \(n\) 次点，每次加点最坏情况要遍历整个边集，所以时间复杂度为 \(O(nm)\)
2.网络流
源点连左部点，右部点连汇点，把边的容量都改成 \(1\)
用 dinic 据说是 \(O(n\sqrt n)\)，这是为啥呢？
其他：（不一定是二分图）
边覆盖：任意顶点都被选的边覆盖
若没有孤立点，则 \(|最大匹配|+|最小边覆盖|=|V|\)
如果 \(|最小边覆盖|= 这个点集的大小时，二分图该部点都被匹配。
End！
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 这个有用。 收藏一下 不知道什么时候能用到 懂技术并乐意极积无私分享的人越来越少。珍惜 新版吗？好像是停更了吧。 感谢分享，学习下。 感谢分享，学习下。 过来提前占个楼 感谢，下载保存了 用心讨论，共获提升！ 很好很强大我过来先占个楼 待编辑 谢谢楼主提供！ 懂技术并乐意极积无私分享的人越来越少。珍惜 这个有用。 分享、互助 让互联网精神温暖你我 新版吗？好像是停更了吧。 鼓励转贴优秀软件安全工具和文档！ 前排留名，哈哈哈 用心讨论，共获提升！ 新版吗？好像是停更了吧。
页:
[1]
2