Bipartite Graph

如果一个图的顶点可以被分为两个独立的集合 $U$ 和 $V$，使得每一条边的两个端点分别属于这两个不同的集合（即：集合内部没有边相连），那么这个图就是二分图。

核心性质

1. 无奇环性：一个图是二分图的充要条件是它不包含任何“奇数长度的环”。
2. 染色法：如果你尝试给顶点上色（黑/白），且要求相邻点颜色不同，二分图一定能被完美地染成两种颜色。
3. 核心定理（重要）：
   • 最大匹配数 = 最小顶点覆盖数（König定理）：在二分图中，覆盖所有边所需的最少顶点数等于该图的最大匹配数。

这两个概念是图论，尤其是二分图算法中的核心。我们可以通过直观的定义、生动的例子以及它们之间神奇的数学联系来理解。

---

1. 最大匹配数 (Maximum Matching)

定义

在一个图中，匹配（Matching）是指一组边的集合，其中任意两条边都没有公共端点。也就是说，每个顶点最多只与集合中的一条边相连。

最大匹配数就是这个图中包含边数最多的那个匹配集合的大小。

形象理解：相亲派对

想象一个聚会，男生在一边，女生在另一边（二分图）。如果两个互有好感的人连一条线，那么“匹配”就是成对的情侣。

• 因为一个人不能同时和两个人谈恋爱（公共端点），所以每人只能出现在一对情侣中。
• 最大匹配数就是这个聚会里最多能凑成多少对情侣。

---

2. 最小顶点覆盖数 (Minimum Vertex Cover)

定义

顶点覆盖（Vertex Cover）是指一个顶点的集合，使得图中的每一条边都至少有一个端点在这个集合内。

最小顶点覆盖数就是满足这个条件的顶点集合中，顶点个数最少的那个。

形象理解：监控摄像头

想象一个街道网络，每条路（边）的两头是路口（顶点）。你需要在路口安装摄像头。

• 如果一个路口装了摄像头，它就能监控所有连接到这个路口的街道。
• 你的目标是：用最少的摄像头，监控所有的街道。
• 这个最少的摄像头数量，就是最小顶点覆盖数。

---

3. 两者的神奇联系：König 定理

在普通图中，这两个数值通常不相等。但在二分图中，有一个非常著名的定理——柯尼希定理（König's Theorem）：

在二分图中，最大匹配数 = 最小顶点覆盖数。

为什么相等？（直观逻辑）

1. 为了覆盖最大匹配中的每一条边：因为最大匹配里的边都是互不相邻的，每一条边都必须至少有一个独立的点来覆盖。所以，顶点覆盖数至少等于最大匹配数。
2. 神奇之处：在二分图中，我们总能找到一种方式，只用等同于最大匹配数量的点，就覆盖掉所有的边。

---

4. 对比表

特性	最大匹配 (Maximum Matching)	最小顶点覆盖 (Min Vertex Cover)
关注对象	边的集合	点的集合
约束条件	边与边不能共用点	所有的边都必须被点“碰到”
目标	越多越好（寻找最大集合）	越少越好（寻找最小集合）
应用场景	资源分配、任务指派	监控布局、修补漏洞（如你提到的屋顶题）

在那个题目里：

• 边代表漏洞。
• 点代表行木板或列木板。
• 你想用最少的木板（点）**覆盖所有的**漏洞（边），这就是在求最小顶点覆盖。
• 根据柯尼希定理，你只需要写一个匈牙利算法求出最大匹配数，结果就是答案。

你想看看如何手动模拟一下匈牙利算法寻找“增广路”的过程吗？这对理解算法深度很有帮助。

public int minPlanks(int[][] roof) {
    int m = roof.length;
    int n = roof[0].length;

    // 1. 构建邻接表
    List<Integer>[] adj = new ArrayList[m];
    for (int i = 0; i < m; i++) 
        adj[i] = new ArrayList<>();

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (roof[i][j] == 0) { // 发现漏洞
                adj[i].add(j);
            }
        }
    }

    // 2. Hungarian 匈牙利算法求最大匹配
    int maxMatching = 0;
    int[] match = new int[n]; // 记录每一列匹配到了哪一行
    Arrays.fill(match, -1);

    for (int i = 0; i < m; i++) {
        boolean[] visited = new boolean[n];
        if (dfs(i, adj, visited, match)) {
            maxMatching++;
        }
    }

    return maxMatching;
}

boolean dfs(int u, List<Integer>[] adj, boolean[] visited, int[] match) {
    for (int v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;
            // 如果当前列没被占用，或者能给当前占用的行找到“备胎”
            if (match[v] == -1 || dfs(match[v], adj, visited, match)) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}