编辑“︁二分图匹配”︁

{{DISPLAYTITLE:二分图匹配}}

'''二分图匹配'''是图论中的一个重要概念，广泛应用于任务分配、网络流、社交网络分析等领域。本文将详细介绍二分图的定义、匹配的概念、相关算法及其实际应用。

== 二分图与匹配的定义 ==

=== 二分图 ===
一个'''二分图'''（Bipartite Graph）是指顶点集 <math>V</math> 可以被划分为两个不相交的子集 <math>U</math> 和 <math>V</math>，使得图中的每一条边的两个顶点分别属于 <math>U</math> 和 <math>V</math>。即不存在 <math>U</math> 内部或 <math>V</math> 内部的边。

数学定义：
<math>G = (U, V, E)</math>，其中 <math>E \subseteq U \times V</math>。

=== 匹配 ===
在二分图中，'''匹配'''（Matching）是指一组边的集合，其中任意两条边没有共同的顶点。如果匹配中的边数达到最大可能值，则称为'''最大匹配'''（Maximum Matching）。如果一个匹配覆盖了图中的所有顶点，则称为'''完美匹配'''（Perfect Matching）。

== 二分图匹配的算法 ==

=== 匈牙利算法 ===
'''匈牙利算法'''（Hungarian Algorithm）是求解二分图最大匹配的经典算法，其时间复杂度为 <math>O(VE)</math>，其中 <math>V</math> 是顶点数，<math>E</math> 是边数。

==== 算法步骤 ====
1. 初始化匹配为空。
2. 对于每个未匹配的顶点 <math>u \in U</math>，尝试通过增广路径找到匹配。
3. 增广路径是指从 <math>u</math> 出发，交替经过未匹配边和匹配边，最终到达一个未匹配的顶点 <math>v \in V</math>。
4. 如果找到增广路径，则反转路径上的边的匹配状态（未匹配的边变为匹配，匹配的边变为未匹配），从而增加匹配数。

==== 代码示例 ====
以下是用 Python 实现的匈牙利算法：

<syntaxhighlight lang="python">
def bpm(u, match_to, visited, graph):
    for v in range(len(graph[0])):
        if graph[u][v] and not visited[v]:
            visited[v] = True
            if match_to[v] == -1 or bpm(match_to[v], match_to, visited, graph):
                match_to[v] = u
                return True
    return False

def max_bipartite_matching(graph):
    num_u = len(graph)
    num_v = len(graph[0])
    match_to = [-1] * num_v
    result = 0

    for u in range(num_u):
        visited = [False] * num_v
        if bpm(u, match_to, visited, graph):
            result += 1
    return result

# 示例输入：二分图的邻接矩阵表示
graph = [
    [1, 1, 0],
    [0, 1, 1],
    [1, 0, 0]
]
print("最大匹配数:", max_bipartite_matching(graph))  # 输出: 3
</syntaxhighlight>

==== 输入输出说明 ====
- 输入：邻接矩阵 <code>graph</code>，其中 <code>graph[u][v] = 1</code> 表示 <math>u \in U</math> 和 <math>v \in V</math> 之间有边。
- 输出：最大匹配数。对于示例，最大匹配数为 3。

=== Hopcroft-Karp 算法 ===
'''Hopcroft-Karp 算法'''是一种更高效的算法，时间复杂度为 <math>O(\sqrt{V}E)</math>，适用于大规模二分图。

== 实际应用案例 ==

=== 任务分配问题 ===
假设有 <math>n</math> 个工人和 <math>m</math> 个任务，每个工人可以完成某些任务。二分图匹配可用于找到最大数量的工人-任务分配。

=== 婚姻稳定问题 ===
在稳定婚姻问题中，二分图匹配可用于找到稳定的配对，确保没有两个人愿意离开当前的伴侣而配对。

== 可视化示例 ==

以下是一个二分图及其最大匹配的示例：

<mermaid>
graph LR
    U1 --> V1
    U1 --> V2
    U2 --> V2
    U2 --> V3
    U3 --> V1
    style U1 fill:#f9f
    style U2 fill:#f9f
    style U3 fill:#f9f
    style V1 fill:#9f9
    style V2 fill:#9f9
    style V3 fill:#9f9
</mermaid>

最大匹配为：
- <math>U1 \rightarrow V2</math>
- <math>U2 \rightarrow V3</math>
- <math>U3 \rightarrow V1</math>

== 总结 ==
二分图匹配是图论中的基础问题，匈牙利算法和 Hopcroft-Karp 算法是解决该问题的两种主要方法。它在任务分配、稳定婚姻问题等领域有广泛应用。通过本文的学习，读者应能理解二分图匹配的概念、算法实现及其实际意义。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:图论算法]]