匈牙利算法定理：连接匹配与覆盖的桥梁

⚡ 什么是匈牙利算法定理？

在图论与组合优化领域，匈牙利算法定理（Kőnig's Theorem）是一个基石性的结论。该定理由匈牙利数学家 Dénes Kőnig 于 1931 年提出。它揭示了二部图（Bipartite Graph）中两个看似无关的重要参数之间的深刻联系。

这个定理的重要性在于，它将一个优化问题（求最大匹配）与另一个对偶问题（求最小点覆盖）联系了起来。在一般图中，这两个数值并不相等，但在二部图中，它们严格相等。这一性质为设计高效的算法提供了理论保障。

⚙️ 历史背景与发展

匈牙利算法定理的诞生并非一蹴而就，它是20世纪初图论快速发展的产物。

📐 证明逻辑简述

证明匈牙利算法定理的核心思想是利用增广路（Augmenting Path）的性质。

1. 不等式关系

首先，对于任何图，最大匹配数 最小点覆盖数。这是因为每条匹配边都需要至少一个顶点在点覆盖中，且匹配边之间互不相交，所以至少需要 个点。

2. 构造性证明

对于二部图 ，设 为最大匹配。
① 从 中所有未匹配点出发，寻找所有可能的增广路。
② 定义集合 为所有可以通过交错路（Alternating Path）到达的顶点的集合。
③ 构造点覆盖 。
④ 可以证明， 是一个点覆盖，且 。

由于 且我们构造出了大小为 的点覆盖，因此最小点覆盖数必然等于最大匹配数。

💻 算法实现与代码示例

虽然匈牙利算法定理是一个存在性定理，但在实际编程竞赛和工程应用中，我们通常使用基于增广路的匈牙利算法（也称为KM算法的简化版或DFS/BFS匹配算法）来求解最大匹配。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1005;
vector<int> adj[MAXN]; // 邻接表存储二部图
int match[MAXN]; // match[v] = u 表示右部点 v 匹配左部点 u
bool vis[MAXN];  // 访问标记
// 寻找增广路
bool dfs(int u) {
    for (int v : adj[u]) {
        if (vis[v]) continue;
        vis[v] = true;
        // 如果 v 未匹配，或者 v 的匹配点能找到其他增广路
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}
int hungarian(int n) {
    memset(match, -1, sizeof(match));
    int result = 0;
    for (int u = 1; u <= n; u++) {
        memset(vis, false, sizeof(vis)); // 每次DFS重置访问标记
        if (dfs(u)) result++;
    }
    return result;
}
int main() {
    int n, m, e; // n:左部点数, m:右部点数, e:边数
    cin >> n >> m >> e;
    for (int i = 0; i < e; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    cout << "最大匹配数: " << hungarian(n) << endl;
    return 0;
}

def dfs(u, adj, match, vis):
    for v in adj[u]:
        if vis[v]:
            continue
        vis[v] = True
        # 如果v未匹配，或者v的匹配点能找到增广路
        if match[v] == -1 or dfs(match[v], adj, match, vis):
            match[v] = u
            return True
    return False
def hungarian(n, adj):
    match = [-1]  (n + 1) # 假设右部点编号从1到n
    result = 0
    for u in range(1, n + 1):
        vis = [False]  (n + 1)
        if dfs(u, adj, match, vis):
            result += 1
    return result
示例用法
adj = {1: [2, 3], 2: [2], 3: [3]} # 左部1->右部2,3; 左部2->右部2; 左部3->右部3
print("最大匹配数:", hungarian(3, adj))

🚀 实际应用场景

匈牙利算法定理及其相关算法在计算机科学、运筹学和日常生活中有着广泛的应用。

🔗 网友们还关心

在深入研究匈牙利算法定理的过程中，许多学习者往往会遇到一些相关的概念混淆或进阶问题。以下是网民高频关注的周边知识。

💡 深度拓展：为什么非二部图不成立？

很多网友会问，为什么匈牙利算法定理只适用于二部图？让我们看一个反例：三角形图（3个顶点，3条边，形成一个环）。

• 最大匹配：只能选1条边（因为选2条边会共享顶点），所以最大匹配数为1。
• 最小点覆盖：为了覆盖3条边，至少需要2个顶点（例如选顶点A和B，可以覆盖AB、AC、BC中的AB、AC、BC？不对，选A和B只能覆盖AB, AC, BC中的AB和AC，BC未被覆盖。选A和B不能覆盖BC。选A和C覆盖AB, AC, BC。所以最小点覆盖数为2）。

在此例中，最大匹配数(1) < 最小点覆盖数(2)。这证明了匈牙利算法定理在非二部图中失效。二部图的“无奇圈”特性是保证该定理成立的关键。

❓ 常见问题解答 (FAQ)