无向图中最小顶点割（Minimum Vertex Cut）的全局求解算法（基于Gusfield的简化Gomory-Hu树思想）
字数 2884 2025-12-22 02:58:42

无向图中最小顶点割（Minimum Vertex Cut）的全局求解算法（基于Gusfield的简化Gomory-Hu树思想）

题目描述

给定一个无向连通图 \(G = (V, E)\)，其顶点数为 \(n\)，边数为 \(m\)。图的顶点连通度（vertex connectivity）是指为了使图不再连通所需移除的最少顶点数（移除一个顶点时，会同时移除与其相连的所有边）。本算法目标是：计算图的全局最小顶点割的大小，即顶点连通度 \(\kappa(G)\)。
注意：顶点割不允许包含源点 \(s\) 或汇点 \(t\)，且要求割后图至少被分成两个非空部分。

算法思想

计算无向图全局最小顶点割的一种高效方法基于如下核心观察：对于任意两个顶点 \(u\) 和 \(v\)，它们之间的局部顶点割（即分离 \(u\) 和 \(v\) 的最小顶点割）的大小不会超过整个图的顶点连通度 \(\kappa(G)\)。因此，我们可以通过枚举所有顶点对 \((u, v)\)，计算分离它们的局部顶点割，并取最小值来得到全局最小顶点割。
直接枚举所有 \(O(n^2)\) 对顶点并计算每对的局部顶点割成本过高。Gusfield 在 Gomory-Hu 树思想的启发下，证明只需进行 \(n-1\) 次局部顶点割计算即可得到全局最小顶点割。算法步骤清晰，下面我们逐步讲解。

解题步骤

步骤1：理解局部顶点割的计算方法

分离两个顶点 \(u\) 和 \(v\) 的最小顶点割可以通过将每个顶点（除 \(u, v\) 外）拆分成“入点”和“出点”并构造一个有向流网络，然后求 s-t 最小割 来得到。
具体构造方式如下：

  1. 对原图 \(G\) 中每个顶点 \(x\)（除了 \(u\) 和 \(v\)），拆成两个顶点 \(x_{in}\) 和 \(x_{out}\)，并添加一条有向边 \((x_{in}, x_{out})\) 且容量为 1（表示割掉顶点 \(x\) 的成本为 1）。
  2. 对于原图 \(G\) 中的每条边 \((x, y)\)，添加两条有向边 \((x_{out}, y_{in})\) 和 \((y_{out}, x_{in})\)，容量设为无穷大（或一个足够大的数，如 \(n\)），表示边不能被割。
  3. 令 \(u\) 作为源点 \(s\)，\(v\) 作为汇点 \(t\)（它们不拆分，直接作为网络中的节点）。
    在这个网络中，任意一条从 \(s\) 到 \(t\) 的路径必须经过某个顶点 \(x\) 的 \(x_{in} \to x_{out}\) 边，割这条边就对应在原图中移除顶点 \(x\)。因此，该网络中的 s-t 最小割 的容量就等于分离 \(u\) 和 \(v\) 的最小顶点割的大小，并且割边指示了要移除的顶点集合。

步骤2：Gusfield 的简化算法流程

  1. 初始化一个顶点集合 \(S\)，最初包含任意一个顶点（例如顶点 1）。
  2. 重复以下过程，直到 \(S\) 包含所有顶点：
    • 从 \(S\) 中选择一个顶点 \(a\)，在 \(S\) 的补集中选择一个顶点 \(b\)。
    • 计算分离 \(a\) 和 \(b\) 的局部顶点割（利用步骤1的建图与最大流算法，如Dinic或Push-Relabel）。
    • 记录这次割的大小，并更新全局最小值候选。
    • 将 \(b\) 加入集合 \(S\)。
  3. 最终记录的全局最小值就是图的顶点连通度 \(\kappa(G)\)。

关键原理：该过程实际上隐含地构建了一棵 Gomory-Hu 树的骨架，每次计算得到一个割，并根据割将图分成两部分，保证后续计算能覆盖所有必要顶点对。总共只需要 \(n-1\) 次最大流计算，而非 \(\binom{n}{2}\) 次。

步骤3：算法正确性直观解释

考虑图的全局最小顶点割 \(C\)，它将图分成两个非空部分 \(A\) 和 \(B\)。算法过程中，必然存在某次迭代，其中 \(a \in A \cap S\)，\(b \in B \setminus S\)。此时计算的 \(a\) 与 \(b\) 之间的局部顶点割大小就是 \(|C|\)，因为 \(C\) 就是分离 \(A\) 和 \(B\) 的顶点割。因此，算法一定会在某次迭代中得到全局最小值。

步骤4：具体例子演示

考虑一个简单图：顶点集 \(\{1,2,3,4\}\)，边为 \((1,2), (2,3), (3,4), (4,1), (1,3)\)（即一个四边形加一条对角线）。

  1. 初始化 \(S = \{1\}\)。
  2. 选 \(a=1, b=2\)（因为 2 不在 \(S\)），计算分离 1 和 2 的最小顶点割：显然割掉顶点 {3} 或 {4} 均可分离它们，割大小为 1。记录 minCut = 1，将 2 加入 \(S\)。
  3. 选 \(a \in S\)（例如 1），\(b=3\)（不在 \(S\)），计算分离 1 和 3 的割：原图中 1 和 3 直接相连，但割掉顶点 {2} 和 {4} 可分离它们？实际计算最大流网络，得最小割为 2（需同时割掉 2 和 4）。更新？不，因为当前 minCut=1 更小。
  4. 选 \(a \in S\)（例如 1），\(b=4\)，计算得分离 1 和 4 的最小顶点割大小为 1（割掉顶点 2 或 3）。保持 minCut=1。
  5. 算法结束，全局最小顶点割大小为 1。

步骤5：时间复杂度分析

  • 每次局部顶点割计算需要建一个流网络，有 \(O(n)\) 个节点（每个顶点拆成两个），\(O(m)\) 条边。
  • 使用 Dinic 算法（在单位容量网络上）最坏复杂度为 \(O(\min(n^{2/3}, m^{1/2}) \cdot m)\)；但实际中顶点的拆边容量为 1，可视为单位容量网络，Dinic 复杂度为 \(O(\min(n^{2/3}, m^{1/2}) \cdot m)\)。
  • 总共进行 \(n-1\) 次最大流计算，总复杂度为 \(O(n \cdot \min(n^{2/3}, m^{1/2}) \cdot m)\)，对于稀疏图（\(m = O(n)\)），约为 \(O(n^{8/3})\)，在实际中通常可接受。

总结

该算法通过巧妙选择 \(n-1\) 对顶点进行局部顶点割计算，高效地得到了无向图的全局最小顶点割大小。核心在于将顶点割问题转化为有向网络中的最小割问题，并利用类似 Gomory-Hu 树的迭代过程减少计算次数。这个方法既保证了正确性，又显著优于暴力枚举所有顶点对。

无向图中最小顶点割（Minimum Vertex Cut）的全局求解算法（基于Gusfield的简化Gomory-Hu树思想） 题目描述 给定一个无向连通图 \( G = (V, E) \)，其顶点数为 \( n \)，边数为 \( m \)。图的 顶点连通度 （vertex connectivity）是指为了使图不再连通所需移除的最少顶点数（移除一个顶点时，会同时移除与其相连的所有边）。本算法目标是：计算图的全局最小顶点割的大小，即顶点连通度 \( \kappa(G) \)。 注意：顶点割不允许包含源点 \( s \) 或汇点 \( t \)，且要求割后图至少被分成两个非空部分。 算法思想 计算无向图全局最小顶点割的一种高效方法基于如下核心观察：对于任意两个顶点 \( u \) 和 \( v \)，它们之间的 局部顶点割 （即分离 \( u \) 和 \( v \) 的最小顶点割）的大小不会超过整个图的顶点连通度 \( \kappa(G) \)。因此，我们可以通过枚举所有顶点对 \( (u, v) \)，计算分离它们的局部顶点割，并取最小值来得到全局最小顶点割。 直接枚举所有 \( O(n^2) \) 对顶点并计算每对的局部顶点割成本过高。Gusfield 在 Gomory-Hu 树思想的启发下，证明只需进行 \( n-1 \) 次局部顶点割计算即可得到全局最小顶点割。算法步骤清晰，下面我们逐步讲解。 解题步骤 步骤1：理解局部顶点割的计算方法 分离两个顶点 \( u \) 和 \( v \) 的最小顶点割可以通过将每个顶点（除 \( u, v \) 外）拆分成“入点”和“出点”并构造一个有向流网络，然后求 s-t 最小割 来得到。 具体构造方式如下： 对原图 \( G \) 中每个顶点 \( x \)（除了 \( u \) 和 \( v \)），拆成两个顶点 \( x_ {in} \) 和 \( x_ {out} \)，并添加一条有向边 \( (x_ {in}, x_ {out}) \) 且容量为 1（表示割掉顶点 \( x \) 的成本为 1）。 对于原图 \( G \) 中的每条边 \( (x, y) \)，添加两条有向边 \( (x_ {out}, y_ {in}) \) 和 \( (y_ {out}, x_ {in}) \)，容量设为无穷大（或一个足够大的数，如 \( n \)），表示边不能被割。 令 \( u \) 作为源点 \( s \)，\( v \) 作为汇点 \( t \)（它们不拆分，直接作为网络中的节点）。 在这个网络中，任意一条从 \( s \) 到 \( t \) 的路径必须经过某个顶点 \( x \) 的 \( x_ {in} \to x_ {out} \) 边，割这条边就对应在原图中移除顶点 \( x \)。因此，该网络中的 s-t 最小割 的容量就等于分离 \( u \) 和 \( v \) 的最小顶点割的大小，并且割边指示了要移除的顶点集合。 步骤2：Gusfield 的简化算法流程 初始化一个顶点集合 \( S \)，最初包含任意一个顶点（例如顶点 1）。 重复以下过程，直到 \( S \) 包含所有顶点： 从 \( S \) 中选择一个顶点 \( a \)，在 \( S \) 的补集中选择一个顶点 \( b \)。 计算分离 \( a \) 和 \( b \) 的局部顶点割（利用步骤1的建图与最大流算法，如Dinic或Push-Relabel）。 记录这次割的大小，并更新全局最小值候选。 将 \( b \) 加入集合 \( S \)。 最终记录的全局最小值就是图的顶点连通度 \( \kappa(G) \)。 关键原理 ：该过程实际上隐含地构建了一棵 Gomory-Hu 树的骨架，每次计算得到一个割，并根据割将图分成两部分，保证后续计算能覆盖所有必要顶点对。总共只需要 \( n-1 \) 次最大流计算，而非 \( \binom{n}{2} \) 次。 步骤3：算法正确性直观解释 考虑图的全局最小顶点割 \( C \)，它将图分成两个非空部分 \( A \) 和 \( B \)。算法过程中，必然存在某次迭代，其中 \( a \in A \cap S \)，\( b \in B \setminus S \)。此时计算的 \( a \) 与 \( b \) 之间的局部顶点割大小就是 \( |C| \)，因为 \( C \) 就是分离 \( A \) 和 \( B \) 的顶点割。因此，算法一定会在某次迭代中得到全局最小值。 步骤4：具体例子演示 考虑一个简单图：顶点集 \( \{1,2,3,4\} \)，边为 \( (1,2), (2,3), (3,4), (4,1), (1,3) \)（即一个四边形加一条对角线）。 初始化 \( S = \{1\} \)。 选 \( a=1, b=2 \)（因为 2 不在 \( S \)），计算分离 1 和 2 的最小顶点割：显然割掉顶点 {3} 或 {4} 均可分离它们，割大小为 1。记录 minCut = 1，将 2 加入 \( S \)。 选 \( a \in S \)（例如 1），\( b=3 \)（不在 \( S \)），计算分离 1 和 3 的割：原图中 1 和 3 直接相连，但割掉顶点 {2} 和 {4} 可分离它们？实际计算最大流网络，得最小割为 2（需同时割掉 2 和 4）。更新？不，因为当前 minCut=1 更小。 选 \( a \in S \)（例如 1），\( b=4 \)，计算得分离 1 和 4 的最小顶点割大小为 1（割掉顶点 2 或 3）。保持 minCut=1。 算法结束，全局最小顶点割大小为 1。 步骤5：时间复杂度分析 每次局部顶点割计算需要建一个流网络，有 \( O(n) \) 个节点（每个顶点拆成两个），\( O(m) \) 条边。 使用 Dinic 算法（在单位容量网络上）最坏复杂度为 \( O(\min(n^{2/3}, m^{1/2}) \cdot m) \)；但实际中顶点的拆边容量为 1，可视为单位容量网络，Dinic 复杂度为 \( O(\min(n^{2/3}, m^{1/2}) \cdot m) \)。 总共进行 \( n-1 \) 次最大流计算，总复杂度为 \( O(n \cdot \min(n^{2/3}, m^{1/2}) \cdot m) \)，对于稀疏图（\( m = O(n) \)），约为 \( O(n^{8/3}) \)，在实际中通常可接受。 总结 该算法通过巧妙选择 \( n-1 \) 对顶点进行局部顶点割计算，高效地得到了无向图的全局最小顶点割大小。核心在于将顶点割问题转化为有向网络中的最小割问题，并利用类似 Gomory-Hu 树的迭代过程减少计算次数。这个方法既保证了正确性，又显著优于暴力枚举所有顶点对。