寻找无向图中的最小点割集（Minimum Vertex Cut）问题
字数 3754 2025-12-16 03:13:10

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

题目描述
给定一个无向连通图 \(G=(V, E)\)，以及两个不相邻的顶点 \(s\) 和 \(t\)（即 \((s, t) \notin E\)）。定义一个 点割集（Vertex Cut） 为一个顶点集合 \(C \subseteq V \setminus \{ s, t \}\)，使得从图中移除 \(C\) 中的所有顶点（同时移除与这些顶点相连的边）后，\(s\) 和 \(t\) 不再连通。最小点割集 是指包含顶点数量最少的点割集。本问题要求找出一个最小点割集（注意：可能存在多个解，找到任意一个即可），并计算其大小。

关键限制与说明

  1. 由于 \(s\) 和 \(t\) 不相邻，我们无需担心直接边的影响。
  2. 如果图本身不连通，则点割集为空集。但题目通常假设图连通。
  3. 该问题可以推广到求任意两个顶点之间的最小点割集（若相邻，需特殊处理）。
  4. 本问题与 最小割 不同：最小割通常指边割集，而这里是点割集。

解题思路
最小点割集问题可以通过转化为 最大流问题 来求解，具体方法是构造一个 点容量网络，将每个顶点拆分为入点和出点，并设置点容量为 1（除了源点和汇点）。这样，原图中的点割集就对应新网络中的边割集，从而可以用最大流算法求解。

转化步骤

  1. 顶点拆分：将每个顶点 \(u\) 拆分为两个顶点 \(u_{in}\) 和 \(u_{out}\)，并添加一条有向边 \((u_{in}, u_{out})\)，容量为 1（表示“穿过”该顶点的代价）。
  2. 边转换：对于原图中的每条无向边 \((u, v)\)，添加两条有向边 \((u_{out}, v_{in})\) 和 \((v_{out}, u_{in})\)，容量设为无穷大（或一个足够大的数，如 \(|V| + 1\)），表示边本身不可被割。
  3. 源与汇：令 \(s_{out}\) 为源点，\(t_{in}\) 为汇点。注意，为了确保 \(s\) 和 \(t\) 不可被割，将 \((s_{in}, s_{out})\) 和 \((t_{in}, t_{out})\) 的容量设为无穷大。
  4. 求最小割：在新构造的有向容量网络中，求从 \(s_{out}\) 到 \(t_{in}\) 的最小割（即最小边割集）。根据最大流最小割定理，最小割的容量等于最大流的值，且最小割中的边对应原图中的点割集顶点。

为什么这样转化有效？

  • 原图中若要断开 \(s\) 和 \(t\) 的连通性，必须移除某些顶点。
  • 在新网络中，每个顶点被拆分为入点和出点，并通过一条容量为 1 的边连接。若要阻断所有从 \(s_{out}\) 到 \(t_{in}\) 的路径，必须割断某些 \((u_{in}, u_{out})\) 边（因为其他边容量无穷大，割它们不优）。
  • 割断 \((u_{in}, u_{out})\) 边对应于移除原图中的顶点 \(u\)，且代价为 1。
  • 因此，新网络的最小边割集容量即为原图最小点割集的大小，割集中的 \((u_{in}, u_{out})\) 边对应于点割集中的顶点 \(u\)。

详细求解步骤

步骤 1：构造点容量网络
假设原图有 \(n\) 个顶点，编号为 \(1, 2, \dots, n\)，其中 \(s\) 和 \(t\) 已知。

  • 创建新图的顶点集合：对每个原顶点 \(u\)，创建两个新顶点 \(u_{in}\) 和 \(u_{out}\)。通常可以用索引表示，例如 \(u_{in} = u\)，\(u_{out} = u + n\)。
  • 添加内部边：对每个 \(u\)，添加边 \((u_{in}, u_{out})\)，容量为：
    • 如果 \(u = s\) 或 \(u = t\)，容量为 \(\infty\)（表示不可割）。
    • 否则，容量为 1。
  • 添加外部边：对原图中每条边 \((u, v)\)，添加两条有向边 \((u_{out}, v_{in})\) 和 \((v_{out}, u_{in})\)，容量为 \(\infty\)。
  • 设置源点为 \(s_{out}\)，汇点为 \(t_{in}\)。

步骤 2：在新网络上运行最大流算法
使用任意高效的最大流算法（如 Dinic、Edmonds-Karp、Push-Relabel 等）计算从 \(s_{out}\) 到 \(t_{in}\) 的最大流。最大流的值 \(F\) 即为最小点割集的大小。
注意：由于容量为 1 的边很多，算法应能处理顶点数最多为 \(2n\) 的网络。

步骤 3：从最小割中还原点割集
在求得最大流后，通过 残量网络中的可达性 找出最小割：

  • 在残量网络中，从源点 \(s_{out}\) 进行 DFS/BFS，标记所有从源点可达的顶点。
  • 最小割是这样一个边集合：从被标记的顶点指向未被标记的顶点的边，且该边在原网络中容量大于 0。
  • 在这些割边中，找出所有满足以下条件的边 \((u_{in}, u_{out})\)：
    • 在原网络中容量为 1（即不是 \(s\) 或 \(t\) 的内部边）。
    • 在残量网络中，\(u_{in}\) 被标记，而 \(u_{out}\) 未被标记（即该边被割断）。
  • 这些边对应的原顶点 \(u\) 构成一个最小点割集。

步骤 4：输出结果
输出点割集的大小 \(F\) 以及具体顶点集合。

举例说明
假设原图有 4 个顶点：\(V = \{1, 2, 3, 4\}\)，边为 \((1,2), (1,3), (2,3), (2,4), (3,4)\)，\(s = 1\)，\(t = 4\)。

  1. 构造点容量网络：顶点拆分为 \(1_{in},1_{out}, \dots, 4_{in},4_{out}\)。
    • 内部边容量：\((1_{in},1_{out})\) 和 \((4_{in},4_{out})\) 为 \(\infty\)，其余为 1。
    • 外部边：例如对边 (1,2)，添加 \((1_{out},2_{in})\) 和 \((2_{out},1_{in})\)，容量 \(\infty\)。
  2. 计算从 \(1_{out}\) 到 \(4_{in}\) 的最大流。一种最小割是割断 \((2_{in},2_{out})\) 和 \((3_{in},3_{out})\)，因此最大流值为 2。
  3. 还原点割集：顶点 2 和 3。
  4. 最小点割集大小为 2，集合为 \(\{2, 3\}\)。

复杂度分析

  • 顶点数：新网络有 \(2n\) 个顶点，边数最多为 \(n + 2m\)（内部边 \(n\) 条，外部边 \(2m\) 条）。
  • 若使用 Dinic 算法，复杂度为 \(O( \text{min}(V^{2/3}, E^{1/2}) \cdot E )\) 在单位容量网络中表现更好，但这里容量为 1 或 ∞，可视为单位网络吗？注意 ∞ 边实际用大数表示，通常用 \(n+1\)，因此不是纯粹单位容量。一般地，用 Dinic 复杂度为 \(O(V^2 E)\) 在 worst-case 较高，但实践中足够快。若用 Push-Relabel 可达 \(O(V^3)\)。对于无向图点割，常用 \(O(n \cdot \text{maxflow})\)，其中 maxflow 是每次求解的复杂度。
  • 本问题是 全局最小点割 的特例（仅针对一对顶点），更一般的全局最小点割（所有点对中最小值）有专门算法（如 Stoer-Wagner 对边割的扩展），但这里我们仅针对固定 \(s,t\) 对。

注意事项

  1. 若 \(s\) 和 \(t\) 相邻，上述转化可能不直接适用，因为移除顶点不能割断直接边。此时最小点割集可能为空（若允许移除相邻顶点则需调整）。但通常题目保证不相邻。
  2. 若要找 全局最小点割（即所有点对中最小的点割集），可以对所有不相邻点对运行上述算法，取最小值，但复杂度较高。有更高效的基于 Gomory-Hu 树扩展的算法，但较为复杂。
  3. 实际实现时，∞ 可以用一个大于 \(n\) 的数（如 \(n+1\)）代替，因为最小点割大小不超过 \(n-2\)。

总结
通过顶点拆分将点割集问题转化为边割集问题，再利用最大流最小割定理求解，是一种经典的图论技巧。掌握这一转化方法，不仅能解决最小点割集问题，还能推广到点容量不为 1 的广义情况（如顶点有权重时，只需将内部边容量设为权重即可）。

寻找无向图中的最小点割集（Minimum Vertex Cut）问题 题目描述 给定一个无向连通图 \( G=(V, E) \)，以及两个不相邻的顶点 \( s \) 和 \( t \)（即 \( (s, t) \notin E \)）。定义一个 点割集（Vertex Cut） 为一个顶点集合 \( C \subseteq V \setminus \{ s, t \} \)，使得从图中移除 \( C \) 中的所有顶点（同时移除与这些顶点相连的边）后，\( s \) 和 \( t \) 不再连通。 最小点割集 是指包含顶点数量最少的点割集。本问题要求找出一个最小点割集（注意：可能存在多个解，找到任意一个即可），并计算其大小。 关键限制与说明 由于 \( s \) 和 \( t \) 不相邻，我们无需担心直接边的影响。 如果图本身不连通，则点割集为空集。但题目通常假设图连通。 该问题可以推广到求任意两个顶点之间的最小点割集（若相邻，需特殊处理）。 本问题与 最小割 不同：最小割通常指边割集，而这里是点割集。 解题思路 最小点割集问题可以通过转化为 最大流问题 来求解，具体方法是构造一个 点容量网络 ，将每个顶点拆分为入点和出点，并设置点容量为 1（除了源点和汇点）。这样，原图中的点割集就对应新网络中的边割集，从而可以用最大流算法求解。 转化步骤 顶点拆分 ：将每个顶点 \( u \) 拆分为两个顶点 \( u_ {in} \) 和 \( u_ {out} \)，并添加一条有向边 \( (u_ {in}, u_ {out}) \)，容量为 1（表示“穿过”该顶点的代价）。 边转换 ：对于原图中的每条无向边 \( (u, v) \)，添加两条有向边 \( (u_ {out}, v_ {in}) \) 和 \( (v_ {out}, u_ {in}) \)，容量设为无穷大（或一个足够大的数，如 \( |V| + 1 \)），表示边本身不可被割。 源与汇 ：令 \( s_ {out} \) 为源点，\( t_ {in} \) 为汇点。注意，为了确保 \( s \) 和 \( t \) 不可被割，将 \( (s_ {in}, s_ {out}) \) 和 \( (t_ {in}, t_ {out}) \) 的容量设为无穷大。 求最小割 ：在新构造的有向容量网络中，求从 \( s_ {out} \) 到 \( t_ {in} \) 的最小割（即最小边割集）。根据最大流最小割定理，最小割的容量等于最大流的值，且最小割中的边对应原图中的点割集顶点。 为什么这样转化有效？ 原图中若要断开 \( s \) 和 \( t \) 的连通性，必须移除某些顶点。 在新网络中，每个顶点被拆分为入点和出点，并通过一条容量为 1 的边连接。若要阻断所有从 \( s_ {out} \) 到 \( t_ {in} \) 的路径，必须割断某些 \( (u_ {in}, u_ {out}) \) 边（因为其他边容量无穷大，割它们不优）。 割断 \( (u_ {in}, u_ {out}) \) 边对应于移除原图中的顶点 \( u \)，且代价为 1。 因此，新网络的最小边割集容量即为原图最小点割集的大小，割集中的 \( (u_ {in}, u_ {out}) \) 边对应于点割集中的顶点 \( u \)。 详细求解步骤 步骤 1：构造点容量网络 假设原图有 \( n \) 个顶点，编号为 \( 1, 2, \dots, n \)，其中 \( s \) 和 \( t \) 已知。 创建新图的顶点集合：对每个原顶点 \( u \)，创建两个新顶点 \( u_ {in} \) 和 \( u_ {out} \)。通常可以用索引表示，例如 \( u_ {in} = u \)，\( u_ {out} = u + n \)。 添加内部边：对每个 \( u \)，添加边 \( (u_ {in}, u_ {out}) \)，容量为： 如果 \( u = s \) 或 \( u = t \)，容量为 \( \infty \)（表示不可割）。 否则，容量为 1。 添加外部边：对原图中每条边 \( (u, v) \)，添加两条有向边 \( (u_ {out}, v_ {in}) \) 和 \( (v_ {out}, u_ {in}) \)，容量为 \( \infty \)。 设置源点为 \( s_ {out} \)，汇点为 \( t_ {in} \)。 步骤 2：在新网络上运行最大流算法 使用任意高效的最大流算法（如 Dinic、Edmonds-Karp、Push-Relabel 等）计算从 \( s_ {out} \) 到 \( t_ {in} \) 的最大流。最大流的值 \( F \) 即为最小点割集的大小。 注意：由于容量为 1 的边很多，算法应能处理顶点数最多为 \( 2n \) 的网络。 步骤 3：从最小割中还原点割集 在求得最大流后，通过 残量网络中的可达性 找出最小割： 在残量网络中，从源点 \( s_ {out} \) 进行 DFS/BFS，标记所有从源点可达的顶点。 最小割是这样一个边集合：从被标记的顶点指向未被标记的顶点的边，且该边在原网络中容量大于 0。 在这些割边中，找出所有满足以下条件的边 \( (u_ {in}, u_ {out}) \)： 在原网络中容量为 1（即不是 \( s \) 或 \( t \) 的内部边）。 在残量网络中，\( u_ {in} \) 被标记，而 \( u_ {out} \) 未被标记（即该边被割断）。 这些边对应的原顶点 \( u \) 构成一个最小点割集。 步骤 4：输出结果 输出点割集的大小 \( F \) 以及具体顶点集合。 举例说明 假设原图有 4 个顶点：\( V = \{1, 2, 3, 4\} \)，边为 \( (1,2), (1,3), (2,3), (2,4), (3,4) \)，\( s = 1 \)，\( t = 4 \)。 构造点容量网络：顶点拆分为 \( 1_ {in},1_ {out}, \dots, 4_ {in},4_ {out} \)。 内部边容量：\( (1_ {in},1_ {out}) \) 和 \( (4_ {in},4_ {out}) \) 为 \( \infty \)，其余为 1。 外部边：例如对边 (1,2)，添加 \( (1_ {out},2_ {in}) \) 和 \( (2_ {out},1_ {in}) \)，容量 \( \infty \)。 计算从 \( 1_ {out} \) 到 \( 4_ {in} \) 的最大流。一种最小割是割断 \( (2_ {in},2_ {out}) \) 和 \( (3_ {in},3_ {out}) \)，因此最大流值为 2。 还原点割集：顶点 2 和 3。 最小点割集大小为 2，集合为 \( \{2, 3\} \)。 复杂度分析 顶点数：新网络有 \( 2n \) 个顶点，边数最多为 \( n + 2m \)（内部边 \( n \) 条，外部边 \( 2m \) 条）。 若使用 Dinic 算法，复杂度为 \( O( \text{min}(V^{2/3}, E^{1/2}) \cdot E ) \) 在单位容量网络中表现更好，但这里容量为 1 或 ∞，可视为单位网络吗？注意 ∞ 边实际用大数表示，通常用 \( n+1 \)，因此不是纯粹单位容量。一般地，用 Dinic 复杂度为 \( O(V^2 E) \) 在 worst-case 较高，但实践中足够快。若用 Push-Relabel 可达 \( O(V^3) \)。对于无向图点割，常用 \( O(n \cdot \text{maxflow}) \)，其中 maxflow 是每次求解的复杂度。 本问题是 全局最小点割 的特例（仅针对一对顶点），更一般的全局最小点割（所有点对中最小值）有专门算法（如 Stoer-Wagner 对边割的扩展），但这里我们仅针对固定 \( s,t \) 对。 注意事项 若 \( s \) 和 \( t \) 相邻，上述转化可能不直接适用，因为移除顶点不能割断直接边。此时最小点割集可能为空（若允许移除相邻顶点则需调整）。但通常题目保证不相邻。 若要找 全局最小点割 （即所有点对中最小的点割集），可以对所有不相邻点对运行上述算法，取最小值，但复杂度较高。有更高效的基于 Gomory-Hu 树扩展的算法，但较为复杂。 实际实现时，∞ 可以用一个大于 \( n \) 的数（如 \( n+1 \)）代替，因为最小点割大小不超过 \( n-2 \)。 总结 通过顶点拆分将点割集问题转化为边割集问题，再利用最大流最小割定理求解，是一种经典的图论技巧。掌握这一转化方法，不仅能解决最小点割集问题，还能推广到点容量不为 1 的广义情况（如顶点有权重时，只需将内部边容量设为权重即可）。