

二分图

定义¶

二分图，又称二部图，英文名叫 Bipartite graph。

二分图是什么？节点由两个集合组成，且两个集合内部没有边的图。

换言之，存在一种方案，将节点划分成满足以上性质的两个集合。

（图源英文维基）

性质¶

如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。

二分图不存在长度为奇数的环

因为每一条边都是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合。

判定¶

如何判定一个图是不是二分图呢？

换言之，我们需要知道是否可以将图中的顶点分成两个满足条件的集合。

显然，直接枚举答案集合的话实在是太慢了，我们需要更高效的方法。

考虑上文提到的性质，我们可以使用 DFS（图论）或者 BFS 来遍历这张图。如果发现了奇环，那么就不是二分图，否则是。

应用¶

二分图匹配¶

匹配¶

设为二分图，若在的子图中，任意两条边都没有公共节点，那么称为二分图的一个匹配，且的边数为匹配数。

完备匹配¶

设为二分图，，为中一个最大匹配，且，则称为到的完备匹配。

霍尔定理¶

设二分图，则中存在到的完备匹配当且仅当对于任意的，均有，其中，是的邻域。

最大匹配¶

寻找二分图边数最大的匹配称为最大匹配问题。

对此，有解决此问题的 匈牙利算法 ，时间复杂度为。

算法步骤大致如下：

首先从任意一个未配对的点开始，选择他的任意一条边（ - ），如此时还未配对，则配对成功，配对数加一，若已经配对，则尝试寻找的配对的另一个配对（该步骤可能会被递归的被执行多次），若该尝试成功，则配对成功，配对数加一。
若上一步配对不成功，那么重新选择一条未被选择过的边，重复上一步，直到点的所有的边都被选择过为止。
对剩下每一个没有被配对的点执行步骤 1，直到所有的点都尝试完毕。

用下面的二分图为例：

先对节点 1 和 2 尝试匹配，假设他们分别找到了 4 和 5。

接下来对节点 3 尝试匹配，选择边（3-4），但发现 4 已经有匹配了，我们尝试寻找 4 的匹配的其他匹配，即 1 的其他匹配。这个匹配显然只能从未被选择的边里找（灰色的），我们可以遍历 1 的所有边，寻找未被选择的，很容易找到边（1-5）。

我们发现 5 已经被匹配了，所以我们尝试寻找 5 的匹配的其他匹配，即 2 的其他匹配。类似的，可以找到 6。

于是我们得到了新的匹配方案，且该方案比之前的匹配数多一。

可以发现，当尝试对节点 3 进行匹配时，走过了一条路径（3-4-1-5-2-6），最后找到了新的匹配方案，我们把这样的道路叫做 增广路 ，其本质是一条起点和终点都是未匹配节点的路径。

匈牙利算法执行的过程也可以看作是不断寻找增广路的过程，当在当前匹配方案下再也找不到增广路，那么当前匹配方案便是最大匹配了。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
int n, m, e;
vector<int> G[N];  // 使用邻接表来储存边
int match[N], vis[N];
bool dfs(int u) {
  int len = G[u].size();
  for (int i = 0; i < len; i++) {  // 遍历每一条边
    int v = G[u][i];
    if (vis[v]) continue;
    vis[v] = 1;
    if (!match[v] ||
        dfs(match[v])) {  // 如果v没有匹配，或者v的匹配找到了新的匹配
      match[v] = u;
      match[u] = v;  // 更新匹配信息
      return 1;
    }
  }
  return 0;
}
int main() {
  scanf("%d %d %d", &n, &m, &e);
  for (int i = 1; i <= e; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    if (a > n || b > m) continue;
    G[a].push_back(n + b);
    G[n + b].push_back(a);
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {  // 对每一个点尝试匹配
    for (int j = 1; j <= n + m; j++) vis[j] = 0;
    if (dfs(i)) ans++;
  }
  printf("%d", ans);
  return 0;
}

除此之外，该问题还可以转化为最大流问题解决。

设是一个二分图，不妨在图中添加源点和汇点，从向中的所有节点连一条流量为 1 的边，中的所有节点也向连一条流量为 1 的边，并且将和之间的边改成从指向，流量为 1 的边。此时该图的最大流量即为最大匹配数，流量流过的边和点构成的子图即为的最大匹配。

若使用 Dinic 算法，则时间复杂度为。

例题参考：

洛谷 P3386【模板】二分图匹配

最大权匹配¶

设为带边权的二分图，寻找边权和最大的匹配称为最大权匹配问题。

该问题可以转化为费用流问题解决。

设是一个带边权的二分图，不妨在图中添加源点和汇点，从向中的所有节点连一条流量为 1，费用为 0 的边，从和的所有节点向连一条流量为 1，费用为 0 的边，并且将和之间的边改成从指向，流量为 1，费用为边权的边。此时该图的最大费最大流的费用即为最大权匹配的边权和，流量流过的边和点构成的子图（删去新添加的点和边后）即为的最大权匹配。

一般图匹配¶

对于一个图，它的匹配是二元组组成的集合，其中，并且中不存在重复的点。

当最大的时候，我们称为的最大匹配。

该问题可以使用带花树算法或 Tutte 矩阵来解决。

Last update and/or translate time of this article，Check the history
Found smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
Contributor of this article OI-wiki
Translator of this article Visit the original article!
The article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

二分图

定义¶

性质¶

判定¶

应用¶