定义
如果一张无向图可以分为两个集合，并且两集合内部的店没有边相连，则称该图为二分图。
判定
染色法
任意选择一个点开始染色，将与它相连的点染上相反的颜色，当出现矛盾时，说明不是二分图，否则为二分图。
二分图的最大匹配
定义
匹配：设 G 为二分图，若其子图 M 满足任意两条边之间无公共节点，则为二分图的匹配。
最大匹配：当 M 的边数最多时，为二分图的最大匹配。
匹配边：属于 M 的边，非匹配边同理。
交替路：从一个不属于 M 的点出发，依次经过不属于 M 的边、属于 M 的边……所形成的链为交替路。
增广路：从一个不属于 M 的点出发，走交替路，若能到达另一个不属于 M 的点，则经过的路径成为增广路。
增广路的性质
非匹配边数 - 匹配边数 = 1。
交换增广路的匹配边与非匹配边时，我们发现，匹配边多了一条，且仍然符合匹配的性质。
匈牙利算法
不断寻找增广路，将最广路上的匹配边与非匹配边互换，直到找不到增广路为止。