二分图判断以及二分图最大匹配
概念
二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。其中左边的顶集合称为左部,右边的顶集合称为右部。
例如下图中,仅黑点和黑边就是一个二分图,但是加上红色的边,就不是二分图了。
匹配:一个匹配即一个包含若干条边的集合,且其中任意两条边没有公共端点。
下图的红边就是上面二分图的一个匹配:
最大匹配:最大匹配即包含边数最多的匹配。
完美匹配:包含所有顶点的匹配,也叫做完备匹配。
交替路:从未匹配点出发,依次经过未匹配点、匹配点、未匹配点…的路径。
增广路:从一个未匹配点出发,走交替路,如果到达另一个未匹配点(出发的点不算),则这条交替路称为增广路(agumenting path)。
例如下图的加粗路径既是一条交替路,也是一条增广路:
二分图的判定:无向图G为二分图的充分必要条件是,G至少有两个顶点,且其所有回路的长度均为偶数。
因此我们可以用dfs或者bfs染色来判断是不是二分图,如果所有点都和相连的点颜色不同,那么就是二分图。
DFS判断二分图:
1 | // 初始化vis[1]=1 其余为0 |
BFS判断二分图:
1 | queue<int> q; |
匈牙利算法求二分图最大匹配
因为增广路中,未匹配边总是比匹配边多一条,因此我们可以通过不断寻找增广路,并且将该增广路中的匹配边改成未匹配边、匹配边改成未匹配变来增加匹配数。匈牙利算法求最大匹配就是不断寻找增广路并对其“取反”完成的。
我们选取二分图的左部,枚举每个点在右部中找配对,并且总是按右部的顶点的顺序来优先配对。
举个例子:
step1(还未匹配,取左部第一个点和右部第一个点配对):
step2(左部第二个点也能和右部第一个点配对,这时候,右部第一个点的原配尝试更换匹配,如果可以更换,那么右1原配更换配对,左2就与右1匹配,否则,左2放弃匹配!):
step3(满足step2中的原配可以更换匹配,左1更换匹配):
step4(左3与左1在右2上冲突,但是,上图中的这五条边构成了增广路):
因此可以取反,得到另一个匹配:
step5(匹配左4和右3不会发生冲突,完成最终匹配):
因此, 利用匈牙利算法求解最大匹配就是不断找增广路取反的过程。
例题:HDU 2444-The Accomodation of Students
二分图判断+最大匹配
AC代码:
1 | int head[210], ct; |