[Algorithm]Maximum Matching of Bipartite Graph/二分图的最大匹配

二分图

所谓二分图，指的是顶点可以分成两个不相交的集合U和V，使得所有的边的两个端点分别位于集合U和V中。换句话说，任意U中的两点或者任意V中的两点，他们之间不会有边相连，也就是说U和V是独立集。如图所示，下图就是一个标准的二分图：

图1

验证一个图是否是二分图的方法也很简单，只需要看我们是否能把所有的节点分为两个集合即可，相邻的边一定不在一个集合当中。值得注意的一点是二分图不一定是连通的，所以对于所有的component我们都需要验证。

例题：

Is Graph Bipartite?

最大匹配/Maximum Matching

首先我们要定义几个概念(1)：

• 匹配：匹配是图的一组边的集合，其中任意两条边不存在公共顶点。
• 匹配边：处于匹配集合当中的边。
• 匹配点：匹配边经过的点。
• 未匹配边：不处于匹配集合当中的边。
• 未匹配点：没有匹配边经过的点。
• 最大匹配：一个图的左右匹配当中，含有匹配边最多的那一个。可能有多个。
• 完美匹配：存在某个匹配，使得图中所有的点都是匹配点。不一定存在。

如下图所示，红边表示匹配边。图2和图3都是图1的匹配，其中图3是最大匹配。图1不存在完美匹配，因为无论如何左边至少会有一个节点失配：

图2

图3

对于一个二分图，我们可以跑匈牙利算法来找出它的最大匹配。在介绍算法之前，我们还需要引入几个概念(1)：

• 交替路径：从未匹配点开始，依次经过未匹配边、匹配边、未匹配边...的路径叫做交替路径。
• 增广路径：以未匹配点结尾的交替路径。

对于下图来说，2->6，4->7->3->6都是增广路径。

图4

增广路径的一个特点就是，如果我们把其中匹配边换为非匹配边，非匹配边换为匹配边，我们可以多找到一个匹配。拿图4中的4->7->3->6举例，如下图所示：

图5

所以，如果当前匹配仍然存在增广路径，就意味着我们可以不断改进匹配，让匹配数增加(这个思路和最大流很像)。所以匈牙利算法的核心思路就是，不断地寻找增广路径改进匹配，直到当前匹配不存在增广路径，意味着当前匹配就是最大匹配。

具体来说，对于给定的二分图g，和两个顶点的集合U和V，U和V满足条件g中所有边的顶点一个处于U一个处于V。匈牙利算法就是对于集合U或者V里的所有顶点，依次找增广路径。如果我们可以找到，我们改进匹配；否则我们直接去下一个点。

这个算法有几个细节我们需要注意。首先是我们只需要在U或者V的集合里跑，不需要所有点都跑。因为如果存在从U开始的增广路径，那么其一定结尾在V中的非匹配点，反之亦然。所以从V开始的增广路径的数量和从U开始的是一样的，我们每找到一条，两边的数量都减1，所以我们只需要在一边找即可。其次，我们每个点只需要找一次增广路径，这是因为：

• 如果当前点没有找到增广路径，那么之后其也不会出现增广路径。因为改进匹配的时候，原来是匹配点的仍然是匹配点。只有首位两个非匹配点会变成匹配点。不会出现匹配点变成非匹配点的情况。所以仍然不可能从这个点找到以新出现的非匹配点结尾的交替路径。
• 如果当前点找到了增广路径，那么它永远都会是匹配点。

最后一点，如果是需要我们建图的情况。因为二分图是无向图，一般建无向图的时候，对于边u和v(u in U, v in V)，我们要在v的neighbors中加入u，u的neighbors加入v。但是如果只为了跑匈牙利算法的话我们不需要，如果我们从U集合这边找的话，只有U中的节点需要知道他们的邻居，而对于V中的节点，我们只需要知道他们匹配的节点就可以了，如果没有匹配，意味着我们找到了增广路径；否则，我们取V中匹配点接着dfs。代码如下：

	int hungarian(vector<int>& g, int U, int V)
	{
	vector<int> matchU(U, -1), matchV(V, -1);
	int matches = 0;
	for (int u = 0; u < U; ++u)
	{
	vector<bool> visited(U, false);
	if (matchU[u] == -1 && dfs(g, matchU, matchV, visited, u))
	++matches;
	}
	return matches;
	}
	bool dfs(vector<int>& g, vector<int>& matchU, vector<int>& matchV, vector<bool>& visited, int u)
	{
	if (visited[u])return false;
	visited[u] = true;
	int start = g[u], len = matchV.size();
	for (int v = start; v < len; ++v)
	{
	if (matchV[v] == -1 || dfs(g, matchU, matchV, visited, matchV[v]))
	{
	matchV[v] = u;
	matchU[u] = v;
	return true;
	}
	}
	return false;
	}

view raw hungarian_algorithm.cpp hosted with ❤ by GitHub

时间复杂度O(V * E)，因为对于U或者V中的所有节点我们都要run dfs。空间复杂度O(V)。

最小点覆盖，最小路径覆盖，最小边覆盖，最大独立集和最大团

首先我们介绍涉及的概念：

• 最小点覆盖：选取最小的点集合，覆盖图中所有的边
• 最小边覆盖：选取最小的边集合，覆盖图中所有的点
• 最大独立集：选取最大的点集合，使得两两顶点之间没有边相连
• 最大团：选取最大的点集合，使这个子图成为一个完全图。所谓完全图，指的是图中所有顶点两两之间都有边相连
• 最小路径覆盖：在DAG中，选取最少的路径条数，使其覆盖了DAG中所有的顶点。在这里我们只讨论不相交路劲，也就是说每个顶点仅有一条路径与之关联。

这些性质和最大匹配有这密不可分的关系，在二分图中，如果顶点数为N：

• 最小点覆盖 = 最大匹配(Konig定理)
• 对于不存在孤立点的二分图，最小边覆盖 = N - 最大匹配
• 最大独立集 = N - 最大匹配
• 最大团 = 补图的最大独立集，补图要是二分图。存在图G，如果图G'的顶点数和G相同，并且G'满足条件，对于不同的顶点u和v，如果u和v在G中有边相连，那么在G'中无边相连；反之，如果u和v在G中无边相连，那么在G'中有边相连，那么我们称G'为G的补图

最小路径覆盖我们稍后介绍，首先我们来看Konig定理，其证明如下(2)  :

上面介绍匈牙利算法的步骤是，从左边每一个点开始寻找增广路径。但是如果我们当前已经找到最大匹配，我们就不可能在找到增广路径，但是依然存在交替路径(以匹配点结尾)。如果我们从左边的所有非匹配点开始，寻找交替路，并且把所有经过的顶点做上标记。对于图3来说，其对应的标记如下图所示：

图6

我们取左边所有未标记的点，和右边所有标记了的点，如图6所示为{3, 4, 6}，这就是最小点覆盖。

假设最大匹配为M，按上述方法取得的点集合为V。那么这个方法取得的点数也为M。这是因为我们选取的点和匹配边是一一对应的。首先，左边不在V中和右边在V中的点都必为匹配点。其次，对于一条匹配边来说:

• 要不是两端都没有标记的。对应当前边没有被选做交替路的情况。
• 要不是两端都有标记。因为如果走交替路而右端有标记了，那么必然可以通过匹配边走到左边从而左边也被标记。

V中取的顶点覆盖的所有边，其要不是左端点没有被标记(那么肯定两端没有标记)，要不就是右端标记了的点(两端都标记了点)，自然覆盖所有的匹配边。
而对于所有的非匹配边，其也只有以下情况:

• 左端点为非匹配点，右端点为匹配点。其左右必然同时被标记，所以必然被选入V的右边端点覆盖。
• 左端点为匹配点，右端点为非匹配点。其左右必然不被标记，所以必然被选入V的左边端点覆盖。
• 两端都为匹配点(如果两端都为非匹配点说明此时不是最大匹配)。对于两端都是匹配点的非匹配边，其要不是两端都没标记，要不是两端都有标记。因为能到达左边的匹配点的话，必然可以通过非匹配边到达右边的匹配点，剩下的分析和之前类似。

M必然为最小点覆盖，因为M个匹配边无论如何都需要M个点去覆盖，所以最大匹配=最小边覆盖，证明完毕。
最小边覆盖的证明比较简单，首先图中不存在孤立的点，否则不存在最小边覆盖。对于M个匹配边，其可以覆盖2 * M个匹配点。那么剩下的N - 2 * M个点，因为不存在匹配边，所以一条边最多覆盖一个没有被覆盖的点，所以总共需要M + N - 2 * M = N - M条边。最小边覆盖 = N - 最大点覆盖，得证。
对于最大独立集，首先除了2 * M个匹配点，剩下的N - 2 * M个顶点一定组成独立集，因为属于左边集合的顶点之间没有边相连，右边同理。并且左边和右边的点两两之间也没有边相连，否则又会多出一个匹配。其次，对于每一条匹配边对应的两个匹配点u和v，u和v不可能同时与非匹配点相连，否则会多出一条增广路径，与当前匹配是最大匹配矛盾。所以u和v其中之一可以放到独立集里，我们可以得到大小为N - M的独立集。显而易见这个是最大独立集，因为对于M个匹配边，肯定有M个匹配点不会在独立集里，所以这个是最大独立集，最大独立集 = N - 最大匹配得证。最大团等于补图的最大独立集显而易见，前提是补图是二分图。
对于DAG的最小路径覆盖问题，我们也可以转化为二分图的最大匹配问题(3)。我们按照如下方式构建二分图：

• 对于DAG中的每个顶点v, 我们拆分成v和v'两个顶点
• 对于DAG中的没一条u->v，我们在二分图中建立一条u到v'的无向边

显而易见这个图是二分图，如下例子所示(3)：

图7

在这个二分图的基础上，找到最大匹配即可。最小路径覆盖 = DAG中的顶点数 - 对应二分图的最大匹配，因为对应二分图中每一条匹配边对应的是原图DAG中的一条有向边，如上所示，如果最大匹配是[1, 3']和[3, 4']，那么对应DAG中路径1和3都有后继结点，所以其不可能为一条路径的终点，因为一个顶点只关联一条路径。假设最大匹配为M， 那么剩下的N - M个顶点没有后继结点才会成为路径的终点，所以一共有N - M条路径。这个肯定是最小的路径数目，因为我们找的是最大匹配，也就是让尽可能多的顶点有后继结点，从而不成为路径的终点。证明完毕。

例题(待补充)

References:
(1)https://www.renfei.org/blog/bipartite-matching.html
(2)http://www.matrix67.com/blog/archives/116
(3)http://www.cnblogs.com/icode-girl/p/5418461.html