二分图的最大权匹配（Kuhn-Munkres算法）
字数 1721 2025-10-31 08:19:25

二分图的最大权匹配（Kuhn-Munkres算法）

题目描述
给定一个完全二分图 \(G = (X \cup Y, E)\)，其中 \(|X| = |Y| = n\)，每条边 \((x_i, y_j)\) 有一个权重 \(w_{ij} \geq 0\)。要求找到一种完美匹配（即每个顶点恰好被匹配一次），使得匹配边的权重之和最大。

解题过程
Kuhn-Munkres算法（又称匈牙利算法）通过构造顶点标号（Labeling）和等价子图，将最大权匹配问题转化为最大匹配问题。以下是详细步骤：

  1. 初始化顶点标号

    • 对左侧顶点集 \(X\)，定义标号 \(l(x_i) = \max_{j} w_{ij}\)（即顶点 \(x_i\) 关联的最大边权）。
    • 对右侧顶点集 \(Y\)，定义标号 \(l(y_j) = 0\)。
    • 标号需满足可行性条件：对任意边 \((x_i, y_j)\)，有 \(l(x_i) + l(y_j) \geq w_{ij}\)。

  2. 构造等价子图

    • 定义等价子图 \(G_l\)：仅保留满足 \(l(x_i) + l(y_j) = w_{ij}\) 的边。
    • 在 \(G_l\) 中寻找完美匹配（若找到，则此匹配即为原图的最大权匹配，由可行性条件保证）。

  3. 迭代改进标号

    • 若当前等价子图 \(G_l\) 中不存在完美匹配，执行以下步骤：
      a. 在 \(G_l\) 中寻找一个最大匹配 \(M\)。
      b. 选择未匹配的左侧顶点 \(u \in X\) 作为起点，通过交错路径（交替经过匹配边和非匹配边）标记可达顶点：
      • 令 \(S \subseteq X\) 为从 \(u\) 出发可达的左侧顶点集合，\(T \subseteq Y\) 为可达的右侧顶点集合。
        c. 计算标号调整量：

\[ \delta = \min_{x_i \in S, y_j \notin T} \{ l(x_i) + l(y_j) - w_{ij} \} \]

    （即不满足可行性条件的最小差值）。  
 d. 更新标号：  
    - 对 $ x_i \in S $，令 $ l(x_i) = l(x_i) - \delta $。  
    - 对 $ y_j \in T $，令 $ l(y_j) = l(y_j) + \delta $。  
    - 其他顶点标号不变。  
 e. 更新等价子图 $ G_l $：根据新标号重新保留满足 $ l(x_i) + l(y_j) = w_{ij} $ 的边。  
 f. 重复步骤3直到找到完美匹配。
  1. 算法终止
    • 当等价子图中找到完美匹配时，算法结束。此时匹配的权重和等于所有顶点标号之和，且为最大值。

示例说明
假设二分图权重矩阵为：

\[\begin{bmatrix} 3 & 5 \\ 2 & 1 \\ \end{bmatrix} \]

  • 初始化标号：\(l(x_1)=5, l(x_2)=2, l(y_1)=0, l(y_2)=0\)。
  • 等价子图包含边 \((x_1, y_2)\)（因 \(5+0=5\)）和 \((x_2, y_1)\)（因 \(2+0=2\)），但无法形成完美匹配。
  • 调整标号：取 \(S=\{x_1\}, T=\{y_2\}\)，计算 \(\delta = 2\)，更新后标号为 \(l(x_1)=3, l(x_2)=2, l(y_1)=0, l(y_2)=2\)。
  • 新等价子图包含边 \((x_1, y_1)\)（权重3）和 \((x_2, y_1)\)（权重2），可形成完美匹配 \(\{(x_1,y_1), (x_2,y_2)\}\)，权重和为 \(3+1=4\)（注意 \((x_2,y_2)\) 的权重1通过标号间接满足条件）。

关键点

  • 标号调整始终保持可行性条件，确保最终匹配的最优性。
  • 时间复杂度为 \(O(n^3)\)，适用于稠密二分图。
二分图的最大权匹配（Kuhn-Munkres算法） 题目描述 给定一个完全二分图 \( G = (X \cup Y, E) \)，其中 \( |X| = |Y| = n \)，每条边 \( (x_ i, y_ j) \) 有一个权重 \( w_ {ij} \geq 0 \)。要求找到一种完美匹配（即每个顶点恰好被匹配一次），使得匹配边的权重之和最大。 解题过程 Kuhn-Munkres算法（又称匈牙利算法）通过构造顶点标号（Labeling）和等价子图，将最大权匹配问题转化为最大匹配问题。以下是详细步骤： 初始化顶点标号 对左侧顶点集 \( X \)，定义标号 \( l(x_ i) = \max_ {j} w_ {ij} \)（即顶点 \( x_ i \) 关联的最大边权）。 对右侧顶点集 \( Y \)，定义标号 \( l(y_ j) = 0 \)。 标号需满足可行性条件：对任意边 \( (x_ i, y_ j) \)，有 \( l(x_ i) + l(y_ j) \geq w_ {ij} \)。 构造等价子图 定义等价子图 \( G_ l \)：仅保留满足 \( l(x_ i) + l(y_ j) = w_ {ij} \) 的边。 在 \( G_ l \) 中寻找完美匹配（若找到，则此匹配即为原图的最大权匹配，由可行性条件保证）。 迭代改进标号 若当前等价子图 \( G_ l \) 中不存在完美匹配，执行以下步骤： a. 在 \( G_ l \) 中寻找一个最大匹配 \( M \)。 b. 选择未匹配的左侧顶点 \( u \in X \) 作为起点，通过交错路径（交替经过匹配边和非匹配边）标记可达顶点： 令 \( S \subseteq X \) 为从 \( u \) 出发可达的左侧顶点集合，\( T \subseteq Y \) 为可达的右侧顶点集合。 c. 计算标号调整量： \[ \delta = \min_ {x_ i \in S, y_ j \notin T} \{ l(x_ i) + l(y_ j) - w_ {ij} \} \] （即不满足可行性条件的最小差值）。 d. 更新标号： 对 \( x_ i \in S \)，令 \( l(x_ i) = l(x_ i) - \delta \)。 对 \( y_ j \in T \)，令 \( l(y_ j) = l(y_ j) + \delta \)。 其他顶点标号不变。 e. 更新等价子图 \( G_ l \)：根据新标号重新保留满足 \( l(x_ i) + l(y_ j) = w_ {ij} \) 的边。 f. 重复步骤3直到找到完美匹配。 算法终止 当等价子图中找到完美匹配时，算法结束。此时匹配的权重和等于所有顶点标号之和，且为最大值。 示例说明 假设二分图权重矩阵为： \[ \begin{bmatrix} 3 & 5 \\ 2 & 1 \\ \end{bmatrix} \] 初始化标号：\( l(x_ 1)=5, l(x_ 2)=2, l(y_ 1)=0, l(y_ 2)=0 \)。 等价子图包含边 \( (x_ 1, y_ 2) \)（因 \( 5+0=5 \)）和 \( (x_ 2, y_ 1) \)（因 \( 2+0=2 \)），但无法形成完美匹配。 调整标号：取 \( S=\{x_ 1\}, T=\{y_ 2\} \)，计算 \( \delta = 2 \)，更新后标号为 \( l(x_ 1)=3, l(x_ 2)=2, l(y_ 1)=0, l(y_ 2)=2 \)。 新等价子图包含边 \( (x_ 1, y_ 1) \)（权重3）和 \( (x_ 2, y_ 1) \)（权重2），可形成完美匹配 \( \{(x_ 1,y_ 1), (x_ 2,y_ 2)\} \)，权重和为 \( 3+1=4 \)（注意 \( (x_ 2,y_ 2) \) 的权重1通过标号间接满足条件）。 关键点 标号调整始终保持可行性条件，确保最终匹配的最优性。 时间复杂度为 \( O(n^3) \)，适用于稠密二分图。