无向图的最大匹配问题（Blossom 算法）
字数 2697 2025-12-08 23:05:04

无向图的最大匹配问题（Blossom 算法）

题目描述
给定一个无向图 \(G = (V, E)\)，我们要求它的最大匹配。匹配是指一组没有公共顶点的边的集合。最大匹配是指边数最多的匹配。在二分图中，最大匹配可以用匈牙利算法或Hopcroft-Karp算法高效求解。但在一般无向图中，由于图中可能存在奇环（例如长度为3、5、7……的环），传统的增广路搜索可能会失败。Blossom算法（也称为带花树算法）能够处理一般无向图的最大匹配问题，其核心思想是通过检测并“收缩”奇环（称为“花”，blossom）来将图简化，然后在简化后的图中寻找增广路。

解题过程循序渐进讲解

1. 基本概念回顾

  • 匹配：边集 \(M \subseteq E\)，且 \(M\) 中任意两条边没有公共顶点。
  • 匹配边/非匹配边：属于 \(M\) 的边称为匹配边，否则为非匹配边。
  • 匹配点/未匹配点：被 \(M\) 中边覆盖的顶点称为匹配点，否则是未匹配点。
  • 交替路：一条路径，其边交替属于匹配边和非匹配边。
  • 增广路：起点和终点都是未匹配点的交替路。增广路的长度一定是奇数，且非匹配边比匹配边多一条。如果我们对增广路取“对称差”（将匹配边变为非匹配边，非匹配边变为匹配边），就可以将匹配大小增加1。

2. 无向图与二分图的区别
在二分图中，当我们从某个未匹配点出发寻找增广路时，可以通过给顶点标记“左部”和“右部”来保证交替性，且不会出现环。但在无向图中，从某个未匹配点出发的BFS树可能出现奇环，这会导致传统的交替标记方法失效。例如，一个三角形（三个顶点两两相连），如果我们尝试用二分图的方式标记，会产生冲突。

3. Blossom算法的核心思想
Blossom算法由Jack Edmonds在1965年提出，它通过以下步骤处理奇环：

  • 在BFS搜索增广路的过程中，如果发现一个奇环（称为“花”），就将这个奇环“收缩”成一个新的超顶点（称为“花根”）。
  • 在收缩后的新图上继续搜索增广路。
  • 如果在收缩后的图中找到了增广路，可以将其“展开”回原图，得到原图中的一条增广路。

为什么可以收缩？
奇环有一个重要性质：从花中任意一个顶点进入花，都可以通过交替路走到花的任意其他顶点。因此，在增广路的搜索中，整个花可以视为一个单独的顶点（即花根），而不会漏掉可能的增广路。

4. 算法的详细步骤

步骤1：初始化

  • 从任意一个未匹配点开始，进行BFS，同时给顶点标记“偶数层”（even）或“奇数层”（odd），起点标记为偶数层。
  • 在BFS过程中，我们试图找到一条通往另一个未匹配点的交替路。

步骤2：BFS搜索与标记

  • 队列初始化为当前未匹配点（偶数层）。
  • 从队列中取出一个偶数层顶点 \(u\)，遍历它的邻接边 \((u, v)\)：
    • 如果 \(v\) 未被访问过：
      • 如果 \(v\) 是匹配点，则 \(v\) 的匹配边另一端记为 \(w\)。将 \(v\) 标记为奇数层，\(w\) 标记为偶数层，并将 \(w\) 加入队列。
      • 如果 \(v\) 是未匹配点，则找到了一条增广路，可以进行增广操作（步骤5）。
    • 如果 \(v\) 已经被访问过，且 \(v\) 是偶数层，且 \(u\) 和 \(v\) 在不同的BFS树中（即它们来自不同的未匹配点起点），则找到了一条连接两棵BFS树的交替路，可以合并成一条增广路。
    • 如果 \(v\) 已经被访问过，且 \(v\) 是偶数层，且 \(u\) 和 \(v\) 在同一棵BFS树中，则我们发现了奇环，需要进行“收缩”操作。

步骤3：收缩奇环（Blossom收缩）

  • 当发现一条边 \((u, v)\) 且 \(u\) 和 \(v\) 都是偶数层，并且它们在同一棵BFS树中时，从 \(u\) 和 \(v\) 分别向上追溯到它们的最近公共祖先（LCA），这个LCA一定也是偶数层，且从LCA到 \(u\) 和从LCA到 \(v\) 的两条路径加上边 \((u, v)\) 构成了一个奇环。
  • 我们将这个奇环中的所有顶点收缩成一个新的超顶点（花根），并将原图中与这些顶点相连的边都连接到这个超顶点上。
  • 在收缩后，我们需要重新调整BFS树的结构，将被收缩的环中所有顶点（除了花根）从BFS树中移除，并将它们的未访问邻居加入队列继续搜索。

步骤4：在收缩后的图上继续BFS

  • 重复步骤2和3，直到找到增广路或队列为空。

步骤5：增广与展开

  • 如果在收缩后的图中找到了一条增广路，我们需要将其还原到原图。如果增广路经过了某个超顶点（即被收缩的花），我们需要将超顶点展开成原来的奇环，并找到原图中对应的增广路。
  • 奇环的展开方法：由于奇环中必然存在一个顶点，使得从花根进入环后，可以沿着环的两个方向之一走到这个顶点，并且保持交替性。我们可以通过适当选择环上的匹配边，使得增广路可以顺利通过这个环。

步骤6：重复直到无法增广

  • 每次找到一条增广路，匹配数增加1。然后重新开始步骤1，寻找下一个未匹配点，直到图中没有增广路为止，此时匹配就是最大的。

5. 算法复杂度

  • 每次寻找增广路的时间是 \(O(|V|^2)\)，因为每次BFS可能需要收缩多个花，而收缩操作需要遍历边。
  • 总共有 \(O(|V|)\) 次增广（每次至少增加一条匹配边），因此总时间复杂度为 \(O(|V|^3)\)。
  • 空间复杂度为 \(O(|V| + |E|)\)，用于存储图、匹配状态、BFS队列和花的结构。

6. 实例演示（简略）
考虑一个三角形（三个顶点A、B、C，边AB、BC、CA），初始匹配为空。

  • 从未匹配点A开始BFS，标记A为偶数层。
  • 从A探索到B（偶数层→B未访问），B是未匹配点，立即找到增广路A-B。匹配变为{(A,B)}。
  • 但此时C仍是未匹配点，从未匹配点C开始BFS：
    • 标记C为偶数层。
    • 从C探索到A，A已访问且是奇数层（因为A是匹配点），继续。
    • 从C探索到B，B已访问且是偶数层（B是匹配点，但注意在BFS中，匹配点B会先被标记为奇数层，然后通过它的匹配点A标记为偶数层）。发现奇环C-A-B-C（A和B都是偶数层，且在同一棵树中）。
    • 收缩奇环{A,B,C}为一个超顶点X，继续搜索，但此时已无未匹配点，算法结束。
      最终最大匹配为{(A,B)}，大小为1。

总结
Blossom算法通过检测并收缩奇环，将一般无向图的最大匹配问题转化为类似于二分图的增广路搜索问题。其核心在于处理奇环时，将环收缩为单个顶点，并在找到增广路后正确展开。虽然实现细节较为复杂，但它保证了在多项式时间内求出最大匹配。

无向图的最大匹配问题（Blossom 算法） 题目描述 给定一个无向图 \(G = (V, E)\)，我们要求它的 最大匹配 。匹配是指一组没有公共顶点的边的集合。最大匹配是指边数最多的匹配。在二分图中，最大匹配可以用匈牙利算法或Hopcroft-Karp算法高效求解。但在 一般无向图 中，由于图中可能存在奇环（例如长度为3、5、7……的环），传统的增广路搜索可能会失败。Blossom算法（也称为带花树算法）能够处理一般无向图的最大匹配问题，其核心思想是通过检测并“收缩”奇环（称为“花”，blossom）来将图简化，然后在简化后的图中寻找增广路。 解题过程循序渐进讲解 1. 基本概念回顾 匹配 ：边集 \(M \subseteq E\)，且 \(M\) 中任意两条边没有公共顶点。 匹配边/非匹配边 ：属于 \(M\) 的边称为匹配边，否则为非匹配边。 匹配点/未匹配点 ：被 \(M\) 中边覆盖的顶点称为匹配点，否则是未匹配点。 交替路 ：一条路径，其边交替属于匹配边和非匹配边。 增广路 ：起点和终点都是未匹配点的交替路。增广路的长度一定是奇数，且非匹配边比匹配边多一条。如果我们对增广路取“对称差”（将匹配边变为非匹配边，非匹配边变为匹配边），就可以将匹配大小增加1。 2. 无向图与二分图的区别 在二分图中，当我们从某个未匹配点出发寻找增广路时，可以通过给顶点标记“左部”和“右部”来保证交替性，且不会出现环。但在无向图中，从某个未匹配点出发的BFS树可能出现 奇环 ，这会导致传统的交替标记方法失效。例如，一个三角形（三个顶点两两相连），如果我们尝试用二分图的方式标记，会产生冲突。 3. Blossom算法的核心思想 Blossom算法由Jack Edmonds在1965年提出，它通过以下步骤处理奇环： 在BFS搜索增广路的过程中，如果发现一个奇环（称为“花”），就将这个奇环“收缩”成一个新的超顶点（称为“花根”）。 在收缩后的新图上继续搜索增广路。 如果在收缩后的图中找到了增广路，可以将其“展开”回原图，得到原图中的一条增广路。 为什么可以收缩？ 奇环有一个重要性质：从花中任意一个顶点进入花，都可以通过交替路走到花的任意其他顶点。因此，在增广路的搜索中，整个花可以视为一个单独的顶点（即花根），而不会漏掉可能的增广路。 4. 算法的详细步骤 步骤1：初始化 从任意一个未匹配点开始，进行BFS，同时给顶点标记“偶数层”（even）或“奇数层”（odd），起点标记为偶数层。 在BFS过程中，我们试图找到一条通往另一个未匹配点的交替路。 步骤2：BFS搜索与标记 队列初始化为当前未匹配点（偶数层）。 从队列中取出一个偶数层顶点 \(u\)，遍历它的邻接边 \((u, v)\)： 如果 \(v\) 未被访问过： 如果 \(v\) 是匹配点，则 \(v\) 的匹配边另一端记为 \(w\)。将 \(v\) 标记为奇数层，\(w\) 标记为偶数层，并将 \(w\) 加入队列。 如果 \(v\) 是未匹配点，则找到了一条增广路，可以进行增广操作（步骤5）。 如果 \(v\) 已经被访问过，且 \(v\) 是偶数层，且 \(u\) 和 \(v\) 在不同的BFS树中（即它们来自不同的未匹配点起点），则找到了一条连接两棵BFS树的交替路，可以合并成一条增广路。 如果 \(v\) 已经被访问过，且 \(v\) 是偶数层，且 \(u\) 和 \(v\) 在同一棵BFS树中，则我们发现了奇环，需要进行“收缩”操作。 步骤3：收缩奇环（Blossom收缩） 当发现一条边 \((u, v)\) 且 \(u\) 和 \(v\) 都是偶数层，并且它们在同一棵BFS树中时，从 \(u\) 和 \(v\) 分别向上追溯到它们的最近公共祖先（LCA），这个LCA一定也是偶数层，且从LCA到 \(u\) 和从LCA到 \(v\) 的两条路径加上边 \((u, v)\) 构成了一个奇环。 我们将这个奇环中的所有顶点收缩成一个新的超顶点（花根），并将原图中与这些顶点相连的边都连接到这个超顶点上。 在收缩后，我们需要重新调整BFS树的结构，将被收缩的环中所有顶点（除了花根）从BFS树中移除，并将它们的未访问邻居加入队列继续搜索。 步骤4：在收缩后的图上继续BFS 重复步骤2和3，直到找到增广路或队列为空。 步骤5：增广与展开 如果在收缩后的图中找到了一条增广路，我们需要将其还原到原图。如果增广路经过了某个超顶点（即被收缩的花），我们需要将超顶点展开成原来的奇环，并找到原图中对应的增广路。 奇环的展开方法：由于奇环中必然存在一个顶点，使得从花根进入环后，可以沿着环的两个方向之一走到这个顶点，并且保持交替性。我们可以通过适当选择环上的匹配边，使得增广路可以顺利通过这个环。 步骤6：重复直到无法增广 每次找到一条增广路，匹配数增加1。然后重新开始步骤1，寻找下一个未匹配点，直到图中没有增广路为止，此时匹配就是最大的。 5. 算法复杂度 每次寻找增广路的时间是 \(O(|V|^2)\)，因为每次BFS可能需要收缩多个花，而收缩操作需要遍历边。 总共有 \(O(|V|)\) 次增广（每次至少增加一条匹配边），因此总时间复杂度为 \(O(|V|^3)\)。 空间复杂度为 \(O(|V| + |E|)\)，用于存储图、匹配状态、BFS队列和花的结构。 6. 实例演示（简略） 考虑一个三角形（三个顶点A、B、C，边AB、BC、CA），初始匹配为空。 从未匹配点A开始BFS，标记A为偶数层。 从A探索到B（偶数层→B未访问），B是未匹配点，立即找到增广路A-B。匹配变为{(A,B)}。 但此时C仍是未匹配点，从未匹配点C开始BFS： 标记C为偶数层。 从C探索到A，A已访问且是奇数层（因为A是匹配点），继续。 从C探索到B，B已访问且是偶数层（B是匹配点，但注意在BFS中，匹配点B会先被标记为奇数层，然后通过它的匹配点A标记为偶数层）。发现奇环C-A-B-C（A和B都是偶数层，且在同一棵树中）。 收缩奇环{A,B,C}为一个超顶点X，继续搜索，但此时已无未匹配点，算法结束。 最终最大匹配为{(A,B)}，大小为1。 总结 Blossom算法通过检测并收缩奇环，将一般无向图的最大匹配问题转化为类似于二分图的增广路搜索问题。其核心在于处理奇环时，将环收缩为单个顶点，并在找到增广路后正确展开。虽然实现细节较为复杂，但它保证了在多项式时间内求出最大匹配。