二分图匹配

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

二分图与匹配的定义[编辑 | 编辑源代码]

二分图[编辑 | 编辑源代码]

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

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

匹配[编辑 | 编辑源代码]

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

二分图匹配的算法[编辑 | 编辑源代码]

匈牙利算法[编辑 | 编辑源代码]

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

算法步骤[编辑 | 编辑源代码]

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

代码示例[编辑 | 编辑源代码]

以下是用 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

输入输出说明[编辑 | 编辑源代码]

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

Hopcroft-Karp 算法[编辑 | 编辑源代码]

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

实际应用案例[编辑 | 编辑源代码]

任务分配问题[编辑 | 编辑源代码]

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

婚姻稳定问题[编辑 | 编辑源代码]

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

可视化示例[编辑 | 编辑源代码]

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

最大匹配为： - $U 1 \to V 2$ - $U 2 \to V 3$ - $U 3 \to V 1$

总结[编辑 | 编辑源代码]

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