KACTL 算法笔记

063-图论-一般图匹配

6 min read

  1. YAML 元数据 已设置 tags: [KACTL, 图论, 核心概念]。

  2. 核心概述 在含奇环的一般无向图上通过“交替路增广 + 花缩（Blossom）”求最大匹配，典型复杂度 O(N^3)。

  3. 原文引述

Description: Maximum matching in a general (not necessarily bipartite) undirected graph using Edmonds’ blossom algorithm with blossom contraction and augmenting paths. Time: O(N^3)

  1. 展开阐述

  • 定义与背景

    • 一般图匹配：在无向图 G=(V,E) 中选取互不共享端点的边集 M，目标是最大化 |M|。当图包含奇环时，二分图方法失效，需要 Edmonds Blossom 算法。
    • 增广路定理：若不存在从未匹配点到未匹配点的交替路（起止均为“自由点”），则当前匹配为最大；否则沿该路翻转匹配状态使匹配规模 +1。

  • 接口/数据结构（据实现习惯）

    • 典型接口：
      • GeneralMatching(n)：初始化 n 个点；
      • addEdge(u, v)：添加无向边；
      • solve()：返回最大匹配大小，并填充 mate[i]（与 i 匹配的点，或 -1）。
    • 关键数组与含义（常见命名）：
      • mate：当前匹配对；
      • base：每个点所在“花”的基点（奇环的最小公共祖先）；
      • parent：交替树中点的前驱，用于回溯增广路；
      • label/parity：BFS 分层的偶/奇标记与类型；
      • 队列：按层推进交替森林。

  • 核心流程/要点（交替森林 + 花缩）

    1. 从所有自由点作为根启动 BFS，构造交替森林，层奇偶交替扩展边：
      • 遇到未标记点通过“非匹配边”前进；再通过其“匹配边”继续，维持交替性质。
    2. 同层连边触发奇环（花）：
      • 若在 BFS 中遇到两点位于同一奇偶层，形成奇数长度环；
      • 找到两点在交替树中的最低公共祖先作为“基”，将整环收缩为超点（花缩）。
    3. 在收缩图上继续 BFS：
      • 花缩保证“交替可达性”被保留；一旦在收缩图中发现到另一自由点的交替路，即得到可增广路径。
    4. 增广与展开：
      • 沿 parent 回溯翻转匹配边；
      • 对花缩的超点按记录的结构“解缩”，在原图中对应翻转，匹配规模 +1。
    5. 终止条件：当无法再找到新的增广路时，依据增广路定理，当前匹配即为最大匹配。

  • 复杂度与边界条件

    • 时间：O(N^3)（常见实现），适用于中等规模稠密图；空间：O(N+M)。
    • 图模型：无向图；自环不参与匹配；重边等价处理。
    • 初始化与一致性：base、parent、label 需在每次从自由点启动的搜索中正确复位。
    • 稳定性：花缩/解缩逻辑需保持“交替性质”与“基点一致性”，避免在回溯时破坏奇偶层次。

  • 变体/扩展与关系

    • 带权最大匹配：参见 079-图论-带权匹配（一般图带权版本）。
    • 二分图匹配对比：二分图无奇环花缩，采用 DFS/HK 更高效（见 056-图论-DFS匹配、067-图论-HopcroftKarp）。
    • 最小点覆盖/最大独立集：在二分图有经典对偶关系；一般图中不再直接适用。
    • 与最大流：可通过构造流网络解决二分匹配；一般图匹配直接转流较不自然且复杂度不占优。

  • 正确性要点与不变式

    • 交替性质不变式：交替树沿“非匹配边”扩展到奇层、再沿“匹配边”扩展到偶层；
    • 花缩保持可增广性：奇环被收缩后，原图中的任何可增广路径在收缩图中仍对应一条可达路径；
    • 增广路定理：算法在“无可增广路”时停止即为全局最优。

  • 与相邻技术的对比与取舍建议

    • 若图已知为二分图，应优先采用 HK，复杂度更好；
    • 仅当存在奇环或未知二分性时，使用一般图匹配（Blossom）更稳妥。
  1. 关联节点

Graph View

Backlinks