这两个定义是等价哒。
直观而言，就是这样的图：
二分图有一些神奇的性质，让一些在一般图上复杂度飞天的问题可以在正常时间得到解。（这就是我们研究它的原因鸭！）
当边数最大化的时候，称这个边集为一组最大匹配。
人话：选一些点，使得中间任意两个点之间没有边
人话：让图中的每条边至少有一个顶点在集合里。
（被支配的恐惧
时间复杂度$O(NM)$，空间用邻接矩阵是$O(N^2)$，可以用邻接表优化。
时间复杂度$O(m\sqrt{n})$。
比匈牙利难码难理解，但是应用范围广多了（最大流算法
（会了这个还学什么匈牙利
———————————————————————————
—这里有一大段不知所云感觉没什么luan用的Hall定理—
———————————————————————————
这个名字上风骚的两点让人忍不住觉得naïve。
这个定理就是讲了二分图的最大匹配，最大独立集，最小覆盖之间的关系。
首先设图的点数为N，最大匹配的大小为C
那么有最小覆盖=C，最大独立集=N-C
证明：
首先我们知道最小覆盖和最大独立集是对偶问题。
（把最小覆盖的点删掉，剩下来的就是最大独立集啦
然后就只要证明最小覆盖=最大匹配了
不证了，当结论记叭。（懒
其实是不会证。
EG1
有一个$n*m$的棋盘，其中有一些格子里有怪。
每次操作，可以选择一行或一列攻击，消灭这一行/列的所有怪。
求最少需要几次打掉所有怪。(1e5)
首先建一个二分图，左边$n$个点，代表行；右边$m$个点，代表列。
设这个怪所在的坐标为$(i,j)$，则把左边第$i$个点和右边第$j$个点连起来。
然后求一个最小覆盖就行啦。
EG2
有一个$n*m$的棋盘，其中有些格子放了马。
你要去掉一些马，使它们不能相互攻击。
求留下的马的最大值。(1e5)
因为马走日,所以如果两个格子能够相互攻击，也就意味着这两个格子不同色。
所以冲突必然在黑白两色之间。（阴阳之战，一触即发！
建二分图，一边黑，一边白，如果冲突就连边。
最后求最大独立集就行了。
——————To be continued——————
14/40 怎么还有这么多张PPT？！！！（气哭
原文：https://www.cnblogs.com/qwerta/p/9738698.html