无向图的最小点割集（Minimum Vertex Cut）问题

字数 2938 2025-12-13 20:29:51

无向图的最小点割集（Minimum Vertex Cut）问题

题目描述

给定一个无向连通图 $G = (V, E)$ 和两个不相邻的顶点 $s$ 与 $t$，求一个最小的顶点集合 $C \subseteq V \setminus \{s, t\}$，使得在 $G$ 中删去 $C$ 的所有顶点（以及与这些顶点相连的边）后，$s$ 和 $t$ 不再连通。这样的集合 $C$ 称为一个 $ s $-$ t $最小点割集（Minimum$ s $-$ t $ Vertex Cut）。

注意：

顶点割集不允许包含 $s$ 或 $t$ 本身。
如果 $s$ 和 $t$ 直接相邻，该问题在传统定义下可能无解（或需特殊处理）。
目标是求最小割集的大小（即顶点数量），并可能要求输出具体集合。

解题思路

此问题可通过最大流最小割定理的扩展来解决。核心思想是：

将无向图转化为有向图，并将每个顶点拆分为“入点”和“出点”，中间用一条有向边连接，容量为 1（表示删除该顶点的代价）。
原图中的每条无向边转化为两条方向相反的有向边，容量设为无穷大（表示边不可被“删除”，只能通过删点切断路径）。
在新的有向网络中，求从 $s$ 的出点到 $t$ 的入点的最大流，其值即为最小点割集的大小。
通过最大流后的残量网络，可找出具体的最小点割集。

逐步讲解

第 1 步：顶点拆分与建图

对于原无向图 $G$ 中的每个顶点 $v$，将其拆分为两个顶点：

$v_{in}$：表示进入 $v$ 的“入口”。
$v_{out}$：表示从 $v$ 出发的“出口”。

在 $v_{in}$ 和 $v_{out}$ 之间添加一条有向边 $(v_{in} \to v_{out})$，容量为 1。这条边表示“如果该顶点被选中进入割集，则需切断这条内部边”。

对于原图中的每条无向边 $(u, v) \in E$，转化为两条有向边：

$u_{out} \to v_{in}$，容量为 $+\infty$。
$v_{out} \to u_{in}$，容量为 $+\infty$。

这样，任何从 $s$ 到 $t$ 的路径都必须经过某些顶点的内部边（容量 1）。切断这些内部边（即让它们满流）就对应删除原图中的顶点。

注意：

为保护 $s$ 和 $t$ 不被删除，将 $s_{in} \to s_{out}$ 和 $t_{in} \to t_{out}$ 的容量设为 $+\infty$。
新建的源点为 $s_{out}$，汇点为 $t_{in}$。

第 2 步：转化为最大流问题

在新建的有向网络中，求从 $s_{out}$ 到 $t_{in}$ 的最大流。
根据最大流最小割定理，最大流的值等于最小割的容量。
在这个网络中，最小割一定由若干条“顶点内部边”（容量 1）组成，因为其他边的容量为无穷大，不会被选入割集。
因此，最大流的值就是最小点割集的大小。

第 3 步：求最大流

可以使用任意高效的最大流算法，如 Dinic 算法 或 Push-Relabel 算法。
由于边容量较小（主要是 1 或 ∞），Dinic 算法在此类单位容量图上通常非常高效。

算法步骤（以 Dinic 为例）：

在新建的图上初始化流量为 0。
重复以下步骤直到无法增广：
- 用 BFS 从源点 $s_{out}$ 构建层次图（只经过未满流的边）。
- 用 DFS 在层次图上寻找阻塞流并增加流量。
最终得到的最大流值即为答案。

第 4 步：找出具体的最小点割集

最大流结束后，得到残量网络。
从源点 $s_{out}$ 出发，在残量网络上 BFS 标记所有可达的顶点。
对于每个原图顶点 $v \notin \{s, t\}$，如果 $v_{in}$ 可达而 $v_{out}$ 不可达，则说明边 $(v_{in} \to v_{out})$ 被满流切断，即顶点 $v$ 属于最小点割集。

举例说明

假设无向图如下（s=1, t=4）：

1 — 2 — 4
 \  /
  3

步骤 1：拆点建图

顶点拆为：1_in, 1_out, 2_in, 2_out, 3_in, 3_out, 4_in, 4_out。
内部边：1_in→1_out（∞），2_in→2_out（1），3_in→3_out（1），4_in→4_out（∞）。
原边转化：
(1,2) → 1_out→2_in（∞）和 2_out→1_in（∞）
(1,3) → 1_out→3_in（∞）和 3_out→1_in（∞）
(2,3) → 2_out→3_in（∞）和 3_out→2_in（∞）
(2,4) → 2_out→4_in（∞）和 4_out→2_in（∞）

步骤 2：计算最大流
从 1_out 到 4_in 的最大流为 2（两条路径：1→2→4 和 1→3→2→4 共享顶点 2）。
实际上最小点割集是 {2}，大小为 1？等等，我们需要检查。

实际上，在这个例子中，删除顶点 2 后，1 和 4 之间仍然有路径 1–3–4 吗？没有边 (3,4)，所以删除顶点 2 后 1 和 4 不连通。因此最小点割集大小为 1，集合 {2}。

但在建图后，从 1_out 到 4_in 的路径有：
1_out → 2_in → 2_out → 4_in（需经过内部边 2_in→2_out，容量 1）
1_out → 3_in → 3_out → 2_in → 2_out → 4_in（需经过 3_in→3_out 和 2_in→2_out，容量均为 1）
因此最大流为 1（只能饱和一条内部边），对应最小点割集 {2} 或 {3} 之一。

时间复杂度

顶点数变为 $2|V|$，边数变为 $|V| + 2|E|$。
使用 Dinic 算法，复杂度为 $O((|V|+|E|) \cdot \sqrt{|V|})$ 在单位容量网络上（因为内部边容量为 1）。
整体可在多项式时间内求解。

扩展

全局最小点割（无指定 s, t）：可通过固定 s，枚举 t 并取最小割，时间复杂度 $O(|V|^3)$ 级别，有更优的 Stoer-Wagner 风格算法用于点割吗？通常 Stoer-Wagner 用于边割，点割需用类似方法但更复杂。
带权点割：将内部边的容量设为删除该顶点的代价即可。

总结：最小点割集问题通过顶点拆分为入点和出点，并设置内部边容量为 1，转化为经典的最大流问题，从而高效求解。

无向图的最小点割集（Minimum Vertex Cut）问题题目描述给定一个无向连通图 $ G = (V, E) $ 和两个不相邻的顶点 $ s $ 与 $ t $，求一个最小的顶点集合 $ C \subseteq V \setminus \{s, t\} $，使得在 $ G $ 中删去 $ C $ 的所有顶点（以及与这些顶点相连的边）后，$ s $ 和 $ t $ 不再连通。这样的集合 $ C $ 称为一个 $ s $-$ t $ 最小点割集（Minimum $ s $-$ t $ Vertex Cut）。注意：顶点割集不允许包含 $ s $ 或 $ t $ 本身。如果 $ s $ 和 $ t $ 直接相邻，该问题在传统定义下可能无解（或需特殊处理）。目标是求最小割集的大小（即顶点数量），并可能要求输出具体集合。解题思路此问题可通过最大流最小割定理的扩展来解决。核心思想是：将无向图转化为有向图，并将每个顶点拆分为“入点”和“出点”，中间用一条有向边连接，容量为 1（表示删除该顶点的代价）。原图中的每条无向边转化为两条方向相反的有向边，容量设为无穷大（表示边不可被“删除”，只能通过删点切断路径）。在新的有向网络中，求从 $ s $ 的出点到 $ t $ 的入点的最大流，其值即为最小点割集的大小。通过最大流后的残量网络，可找出具体的最小点割集。逐步讲解第 1 步：顶点拆分与建图对于原无向图 $ G $ 中的每个顶点 $ v $，将其拆分为两个顶点： $ v_ {in} $：表示进入 $ v $ 的“入口”。 $ v_ {out} $：表示从 $ v $ 出发的“出口”。在 $ v_ {in} $ 和 $ v_ {out} $ 之间添加一条有向边 $ (v_ {in} \to v_ {out}) $，容量为 1。这条边表示“如果该顶点被选中进入割集，则需切断这条内部边”。对于原图中的每条无向边 $ (u, v) \in E $，转化为两条有向边： $ u_ {out} \to v_ {in} $，容量为 $ +\infty $。 $ v_ {out} \to u_ {in} $，容量为 $ +\infty $。这样，任何从 $ s $ 到 $ t $ 的路径都必须经过某些顶点的内部边（容量 1）。切断这些内部边（即让它们满流）就对应删除原图中的顶点。注意：为保护 $ s $ 和 $ t $ 不被删除，将 $ s_ {in} \to s_ {out} $ 和 $ t_ {in} \to t_ {out} $ 的容量设为 $ +\infty $。新建的源点为 $ s_ {out} $，汇点为 $ t_ {in} $。第 2 步：转化为最大流问题在新建的有向网络中，求从 $ s_ {out} $ 到 $ t_ {in} $ 的最大流。根据最大流最小割定理，最大流的值等于最小割的容量。在这个网络中，最小割一定由若干条“顶点内部边”（容量 1）组成，因为其他边的容量为无穷大，不会被选入割集。因此，最大流的值就是最小点割集的大小。第 3 步：求最大流可以使用任意高效的最大流算法，如 Dinic 算法或 Push-Relabel 算法。由于边容量较小（主要是 1 或 ∞），Dinic 算法在此类单位容量图上通常非常高效。算法步骤（以 Dinic 为例）：在新建的图上初始化流量为 0。重复以下步骤直到无法增广：用 BFS 从源点 $ s_ {out} $ 构建层次图（只经过未满流的边）。用 DFS 在层次图上寻找阻塞流并增加流量。最终得到的最大流值即为答案。第 4 步：找出具体的最小点割集最大流结束后，得到残量网络。从源点 $ s_ {out} $ 出发，在残量网络上 BFS 标记所有可达的顶点。对于每个原图顶点 $ v \notin \{s, t\} $，如果 $ v_ {in} $ 可达而 $ v_ {out} $ 不可达，则说明边 $ (v_ {in} \to v_ {out}) $ 被满流切断，即顶点 $ v $ 属于最小点割集。举例说明假设无向图如下（s=1, t=4）：步骤 1：拆点建图顶点拆为：1_ in, 1_ out, 2_ in, 2_ out, 3_ in, 3_ out, 4_ in, 4_ out。内部边：1_ in→1_ out（∞），2_ in→2_ out（1），3_ in→3_ out（1），4_ in→4_ out（∞）。原边转化： (1,2) → 1_ out→2_ in（∞）和 2_ out→1_ in（∞） (1,3) → 1_ out→3_ in（∞）和 3_ out→1_ in（∞） (2,3) → 2_ out→3_ in（∞）和 3_ out→2_ in（∞） (2,4) → 2_ out→4_ in（∞）和 4_ out→2_ in（∞）步骤 2：计算最大流从 1_ out 到 4_ in 的最大流为 2（两条路径：1→2→4 和 1→3→2→4 共享顶点 2）。实际上最小点割集是 {2}，大小为 1？等等，我们需要检查。实际上，在这个例子中，删除顶点 2 后，1 和 4 之间仍然有路径 1–3–4 吗？没有边 (3,4)，所以删除顶点 2 后 1 和 4 不连通。因此最小点割集大小为 1，集合 {2}。但在建图后，从 1_ out 到 4_ in 的路径有： 1_ out → 2_ in → 2_ out → 4_ in（需经过内部边 2_ in→2_ out，容量 1） 1_ out → 3_ in → 3_ out → 2_ in → 2_ out → 4_ in（需经过 3_ in→3_ out 和 2_ in→2_ out，容量均为 1）因此最大流为 1（只能饱和一条内部边），对应最小点割集 {2} 或 {3} 之一。时间复杂度顶点数变为 $ 2|V| $，边数变为 $ |V| + 2|E| $。使用 Dinic 算法，复杂度为 $ O((|V|+|E|) \cdot \sqrt{|V|}) $ 在单位容量网络上（因为内部边容量为 1）。整体可在多项式时间内求解。扩展全局最小点割（无指定 s, t）：可通过固定 s，枚举 t 并取最小割，时间复杂度 $ O(|V|^3) $ 级别，有更优的 Stoer-Wagner 风格算法用于点割吗？通常 Stoer-Wagner 用于边割，点割需用类似方法但更复杂。带权点割：将内部边的容量设为删除该顶点的代价即可。总结：最小点割集问题通过顶点拆分为入点和出点，并设置内部边容量为 1，转化为经典的最大流问题，从而高效求解。