xxx 最小割的 Stoer-Wagner 算法

字数 2061 2025-11-25 17:49:38

xxx 最小割的 Stoer-Wagner 算法

题目描述
给定一个无向带权图 \(G = (V, E, w)\)，其中每条边 \(e \in E\) 有一个非负权重 \(w(e)\)，目标是找到图的一个全局最小割（global minimum cut）。全局最小割是指将顶点集 \(V\) 划分为两个非空子集 \(S\) 和 \(V \setminus S\)，使得连接 \(S\) 和 \(V \setminus S\) 的所有边的权重之和最小。Stoer-Wagner 算法通过一系列收缩操作和最大邻接序搜索，高效求解该问题。

解题过程

1. 基本概念与思路

最小割：对无向图，最小割是使割边权重和最小的划分。若图连通，最小割保证划分后两个子集均非空。
算法核心思想：
- 利用最大邻接序（Maximum Adjacency Order, MA Order） 确定两个顶点 \(s\) 和 \(t\)，使得它们之间的最小割等价于 \(s-t\) 最小割。
- 通过收缩操作 合并顶点，逐步减少图规模，最终得到全局最小割。

2. 关键步骤详解

步骤 1：最大邻接序（MA Order）的生成

从任意顶点开始（如 \(v_1\)），逐步选择与当前已选顶点集合 \(A\) 邻接边权重和最大的顶点加入 \(A\)。
形式化描述：
1. 初始化 \(A = \emptyset\)。
2. 随机选择起始顶点 \(u\)，令 \(A = \{u\}\)。
3. 重复以下过程直到 \(A = V\)：
  - 选择满足 \(\max_{x \notin A} \sum_{y \in A} w(x, y)\) 的顶点 \(x\)（即与 \(A\) 连接边权总和最大的顶点）。
  - 将 \(x\) 加入 \(A\)。
最后加入 \(A\) 的两个顶点记为 \(s\) 和 \(t\)（\(s\) 为倒数第二个，\(t\) 为最后一个）。

步骤 2：收缩操作（Edge Contraction）

将顶点 \(s\) 和 \(t\) 合并为一个新顶点 \(st\)，并更新边权：
- 对于与 \(s\) 或 \(t\) 相连的边，若连接同一顶点 \(u\)，则新边权为 \(w(s, u) + w(t, u)\)。
收缩后，原图中连接 \(s\) 和 \(t\) 的边被移除，其他边保留。

步骤 3：递归求解与终止条件

对当前图 \(G\) 执行 MA Order，得到 \(s\) 和 \(t\)，并记录此时 \(t\) 与集合 \(A \setminus \{t\}\) 的边权和（即 \(t\) 的“割值”）。
收缩 \(s\) 和 \(t\)，得到新图 \(G'\)。
递归地在 \(G'\) 上求解最小割，同时比较当前割值与递归得到的最小割值，取较小者。
当图只剩 2 个顶点时，直接返回它们之间的边权作为候选最小割。

步骤 4：全局最小割的确定

算法过程中所有候选割的最小值即为全局最小割。
通过回溯收缩过程，可还原割对应的顶点划分。

3. 实例演示
考虑一个简单图：顶点集 \(\{a, b, c\}\)，边权 \(w(a,b)=2, w(b,c)=3, w(a,c)=1\)。

初始 MA Order：
- 从 \(a\) 开始，\(A = \{a\}\)。
- 选择与 \(A\) 邻接权最大的顶点：\(b\)（权 2）加入 \(A = \{a, b\}\)。
- 最后加入 \(c\)（与 \(A\) 的邻接权为 \(w(b,c)+w(a,c)=3+1=4\)），此时 \(s=b, t=c\)。
- 记录割值 \(= w(b,c) + w(a,c) = 3+1=4\)。
收缩 \(b\) 和 \(c\)：
- 新顶点 \(bc\)，边权更新：\(w(a, bc) = w(a,b) + w(a,c) = 2+1=3\)。
递归：新图仅剩顶点 \(a\) 和 \(bc\)，边权为 3，返回 3 作为候选割。
比较：候选割为 \(\min(4, 3) = 3\)，全局最小割值为 3（对应划分 \(\{a\}\) 和 \(\{b, c\}\)）。

4. 算法复杂度与特点

时间复杂度：使用斐波那契堆实现 MA Order 的优先级队列，每轮 \(O(|E| + |V| \log |V|)\)，共 \(|V|-1\) 轮，总复杂度 \(O(|V||E| + |V|^2 \log |V|)\)。
优势：确定性算法，保证找到精确解，适用于稠密图。

通过以上步骤，Stoer-Wagner 算法逐步收缩图并利用最大邻接序高效定位最小割，最终得到全局最优解。

xxx 最小割的 Stoer-Wagner 算法题目描述给定一个无向带权图 \( G = (V, E, w) \)，其中每条边 \( e \in E \) 有一个非负权重 \( w(e) \)，目标是找到图的一个全局最小割（global minimum cut）。全局最小割是指将顶点集 \( V \) 划分为两个非空子集 \( S \) 和 \( V \setminus S \)，使得连接 \( S \) 和 \( V \setminus S \) 的所有边的权重之和最小。Stoer-Wagner 算法通过一系列收缩操作和最大邻接序搜索，高效求解该问题。解题过程 1. 基本概念与思路最小割：对无向图，最小割是使割边权重和最小的划分。若图连通，最小割保证划分后两个子集均非空。算法核心思想：利用最大邻接序（Maximum Adjacency Order, MA Order）确定两个顶点 \( s \) 和 \( t \)，使得它们之间的最小割等价于 \( s-t \) 最小割。通过收缩操作合并顶点，逐步减少图规模，最终得到全局最小割。 2. 关键步骤详解步骤 1：最大邻接序（MA Order）的生成从任意顶点开始（如 \( v_ 1 \)），逐步选择与当前已选顶点集合 \( A \) 邻接边权重和最大的顶点加入 \( A \)。形式化描述：初始化 \( A = \emptyset \)。随机选择起始顶点 \( u \)，令 \( A = \{u\} \)。重复以下过程直到 \( A = V \)：选择满足 \( \max_ {x \notin A} \sum_ {y \in A} w(x, y) \) 的顶点 \( x \)（即与 \( A \) 连接边权总和最大的顶点）。将 \( x \) 加入 \( A \)。最后加入 \( A \) 的两个顶点记为 \( s \) 和 \( t \)（\( s \) 为倒数第二个，\( t \) 为最后一个）。步骤 2：收缩操作（Edge Contraction）将顶点 \( s \) 和 \( t \) 合并为一个新顶点 \( st \)，并更新边权：对于与 \( s \) 或 \( t \) 相连的边，若连接同一顶点 \( u \)，则新边权为 \( w(s, u) + w(t, u) \)。收缩后，原图中连接 \( s \) 和 \( t \) 的边被移除，其他边保留。步骤 3：递归求解与终止条件对当前图 \( G \) 执行 MA Order，得到 \( s \) 和 \( t \)，并记录此时 \( t \) 与集合 \( A \setminus \{t\} \) 的边权和（即 \( t \) 的“割值”）。收缩 \( s \) 和 \( t \)，得到新图 \( G' \)。递归地在 \( G' \) 上求解最小割，同时比较当前割值与递归得到的最小割值，取较小者。当图只剩 2 个顶点时，直接返回它们之间的边权作为候选最小割。步骤 4：全局最小割的确定算法过程中所有候选割的最小值即为全局最小割。通过回溯收缩过程，可还原割对应的顶点划分。 3. 实例演示考虑一个简单图：顶点集 \( \{a, b, c\} \)，边权 \( w(a,b)=2, w(b,c)=3, w(a,c)=1 \)。初始 MA Order ：从 \( a \) 开始，\( A = \{a\} \)。选择与 \( A \) 邻接权最大的顶点：\( b \)（权 2）加入 \( A = \{a, b\} \)。最后加入 \( c \)（与 \( A \) 的邻接权为 \( w(b,c)+w(a,c)=3+1=4 \)），此时 \( s=b, t=c \)。记录割值 \( = w(b,c) + w(a,c) = 3+1=4 \)。收缩 \( b \) 和 \( c \) ：新顶点 \( bc \)，边权更新：\( w(a, bc) = w(a,b) + w(a,c) = 2+1=3 \)。递归：新图仅剩顶点 \( a \) 和 \( bc \)，边权为 3，返回 3 作为候选割。比较：候选割为 \( \min(4, 3) = 3 \)，全局最小割值为 3（对应划分 \( \{a\} \) 和 \( \{b, c\} \)）。 4. 算法复杂度与特点时间复杂度：使用斐波那契堆实现 MA Order 的优先级队列，每轮 \( O(|E| + |V| \log |V|) \)，共 \( |V|-1 \) 轮，总复杂度 \( O(|V||E| + |V|^2 \log |V|) \)。优势：确定性算法，保证找到精确解，适用于稠密图。通过以上步骤，Stoer-Wagner 算法逐步收缩图并利用最大邻接序高效定位最小割，最终得到全局最优解。