二分图匹配问题定义:有向图中的n个节点分为a、b两个非空集，AB=，且同一集内的点互不相连，该有向图称为二分图，a中点称为二分图
二分图的判定：仅当且图中不存在长度为奇数的环时。
染色法：
voidDFS(intx，int color ) {v[x]=color； for(intI=head[x]； I； I=next[I](inty=ver[I] )； if(v ) y )==0) DFS ) y，3 - color )； elseif(v[y]==color ) flag=0； }}int main () {flag=1； for(intI=1； i=n； I ) if ) v[I]==0) DFS(I，1 )； if(flag==0) cout 'isn't a Bipartite Graph' endl； else cout ' isabipartitegraph ' endl； } 二分图最大匹配
匹配：“任意两条边没有公共端点”的边将合并为图的匹配集。
边数最多的匹配是最大匹配。
相对于匹配s，“匹配边缘” s、“非匹配边缘”s和“赛点”是“匹配边缘”的端点。
增广路:如果在二分图中存在连接两个不匹配点的路径，并且不匹配边和匹配边在路径中交替出现，这就是放大的途径。
在加宽区域中，奇数边是不匹配的边，偶数边是匹配的。
如果将加宽道路的所有边的状态反转，则得到更长的加宽道路。
因此，对于匹配来说，如果该匹配有扩大的途径，则可以用相反的方法使该匹配成为更大的匹配。
因此，最大的匹配一定不存在扩大的途径。
匈牙利算法(扩展路径算法) :
洛谷P3386
# include iostream # include cstring # includecstdiousingnamespacestd； const int N=1e6 50； int n，m，e，u，v，ans； int tot，head[N]，Next[N]，ver[N]，vis[N]，match[N]； inlinevoidadd(intx，int y ) {ver[ tot]=y，Next[tot]=head[x]，head[x]=tot； }boolDFS(intx ) ) for ) intI=head[x]，y； I； I=next[I](if (！ vis[y=ver[i]] ) {vis[y]=1； if (！ match[y]||dfs(match[y] ) {match[y]=x； 返回真； } }返回假； (}int main ) ) {tot=1； 扫描(% d % d % d )、n、m、e )； for(intI=1； i=e； I )扫描(' % d % d )、u、v )； if(u=1v=1u=nv=m ) add (u，v )； }for(intI=1； i=n； I ) )短信(vis，0，sizeof ) vis )； if(DFS ) I ) ) ans； (/printf('%dn '，ans )； cout ans endl； 返回0； (其他匹配)完全匹配)给定二分图，其左部、右部节点数相同，均为n个节点。 如果此二分图的最大匹配包含n条匹配边，则二分图称为具有完全匹配。
多匹配：给出包含左侧节点n个、右侧节点m个的1张。 其中，尽量多选一条边，使第个左部节点至多与k l i kl_i kli条选中的边相连，使第j个右部节点至多与k l j kl_j klj条选中的边相连。
解决方案：网络流
二分图的覆盖和独立集K n o i g Knoig Knoig定理：最小点覆盖=最大匹配
DAG图中最小路径覆盖=节点数-最大匹配数
最大独立集=节点数-最大匹配数