1. 概念
假设图\(G=(V,E)\)是无向图，若顶点集\(V\)可以分成两个互不相交的子集\((A,B)\)，且任意边\((i,j)\)两端点分别属于两子集，则图\(G\)是二分图
判断方法：染色法
匹配：无公共点的边集
匹配数：边集中边的个数
最大匹配：匹配数最大的匹配
增广路：设M是一个匹配，如果存在一条连接两个未匹配点的路径p,使得属于M和不属于M的边交替出现
性质：增广路长度一定为奇数，头尾不属于M，将奇偶互换后可以得到更大的匹配
2. 匈牙利算法
-
置M为空
-
找出一条增广路p,进行取反得到更大的M
-
重复此过程，直到不存在增广路
具体步骤：
依次考虑左侧未匹配的点，一个右侧的点能与它匹配当且仅当它未被匹配或存在增广路
此时，递归左侧的点，为其寻找右侧匹配的点，用标记避免重复搜索
标签：二分,匹配,增广,笔记,学习,子集,属于 From： https://www.cnblogs.com/wangsiqi2010916/p/18498340