请问求一个图的全局最小割,有什么比较快的算法?

想问问有没有比Stoer-Wagner更快的算法
关注者
85
被浏览
5,085
收录于 编辑推荐 ·

算是个比较好搜的题目,凭经验搜一下就好了……

随便写点翻译好了……(只会常用的,捂脸


一个无向图 G = (V, E) 的割 (S, T) 满足 S \cup T = V, S \neq \emptyset, T \neq \emptyset ,这个割的代价是 w(S, T) = \sum_{u \in S, v \in T, u v \in E}{w(uv)} 。而 s - t 割则是满足 s \in S, t \in T 的全局割 (S, T) 。对于这样的图,割一共有 2^{|V| - 1} - 1 种,最小割是其中代价最小的某一个割。为了将割与 s - t 割区分开来,有时也称割为全局割。

一、我会暴力!

如果这个无向图不连通,那么全局最小割是很简单的,否则由最大流最小割定理可知,求解 s - t 最小割的对偶问题是求解 s 为源点、 t 为汇点的最大流问题,存在许多多项式时间的算法可以解决。注意到 s - t 最小割本身就是一个全局割,那么全局最小割一定会是某一种 s - t 最小割,求解全局最小割最暴力的确定性算法就是随便固定一个点 s ,枚举 \mathcal{O}\left(|V|\right) 种可能的 t ,分别求解 s - t 最小割。

二、我会随机!

Karger‘s algorithm是这样一个怪力乱神的随机算法:每次随机时,它会不断地从剩下的图中选出一条边,将这条边的两个端点缩在一起,直到整个图剩下两个端点,那么原图中分别被缩到这两个端点的那些点分别构成了 S 集和 T 集,对应的割也可以直接从图中求得。

每次随机的时间复杂度是 \mathcal{O}(|E|) 的,随机 \mathcal{O}\left(|V|^2 \log |V|\right) 次之后还没有找到全局最小割的概率小于 \frac{1}{|V|}

他们顺便扩展了一下这个算法,每次随机两次将点集的大小缩到原来的 \frac{1}{\sqrt{2}} ,分别递归求解相同问题,取最优值作为结果。他们表示这样可以在 \mathcal{O}\left(|V|^2\log^3 |V|\right) 的时间里以出错可能小于 \frac{1}{|V|} 的概率找到全部最小割。

<del>不过,直接随机选 (s, t) 点对求最大流不就好了吗?</del>

三、我会算法!

Stoer—Wagner algorithm是这样一个奥妙重重的确定算法:每次尝试得到当前图中某两个特殊点之间的 s - t 最小割,将它们缩成一个点,直到整个图缩成一个点,全局最小割即这个过程中计算过的 s - t 最小割中的最小值。(???这复杂度不是暴力吗?

与直接做 \mathcal{O}\left(|V|\right)s - t 最小割不同的是,该算法中使用的 st 是在求解过程中确定的,而不是直接给定的。

每次在当前的无向图 G' = (V', E') 中不断维护一个点集 A' ,初始点集 A' 包含一个任选的点 u \in V' ,当 A' \neq V' 时选取 v \in V', v \not \in A'\sum_{u \in A', u v \in E'}{w(u v)} 最大的点 v 加入点集 A' ,直到 A' = V' 时结束,此时令倒数第二次加入 A' 的点为 s ,最后一次加入 A' 的点为 t ,则 s - t 最小割为割 (A' - \{t\}, \{t\}) 。正确性的话,证明其他 s - t 割都不比它小就好了。

缩点一供要缩 |V| - 1 次,每次找 (s, t) 可以做到时间复杂度 \mathcal{O}\left(|E| + |V|^2\right) 或者 \mathcal{O}\left(\left(|E| + |V|\right) \log |V|\right)

四、图是平面图!

由平面图的对偶定理可知,原图的每一个割都对应着新图的每一个环,所以求解原图中的 s - t 最小割可以通过一些简单的对偶变成求解对偶图中的最短路问题。

而对于求解全局最小割,我们也可以使用分治的方法在对偶图中求解最小环。每次在对偶图中任选一个点 a 为源点,构建对偶图的最短路树,再在对偶图中找到一个区域 F (对应原图中的点 f )以及与它邻接的两个点 bc ,令 a, b, c 之间的这个环是 C (即 ab 最短路径、 ac 最短路径、使 F 被包含在 C 内部的那条在 Fbc 之间的路径),将原图根据 C 的内部与外部划分成两个部分(不含 C ),给这两部分分别加一个新点代表 C ,即可递归求解不跨越 C 的最小环,否则若要经过 C ,则可以找到 ab 路径上的第一条边所邻接的不在 C 内部的那个区域 F' (对应原图中的点 f' ),可证原图的全局最小割一定不会将 ff' 归在同一点集,那么只需要求解 f - f' 最小割就好了。

注意到平面图有 \mathcal{O}\left(|V|\right) = \mathcal{O}(|E|) ,随手写一下的时间复杂度是 \mathcal{O}\left(|V| \log^2 |V|\right) 的,再努努力优化一下应该可以做到 \mathcal{O}\left(|V| \log \log |V|\right) ,具体请参考ftiasch 的回答 - 平面图最小环。(顺手 at 卡不掉错误算法的@赵轩昂

五、我不管全局最小割了!我要多次询问 s - t 最小割!

这可能就有点超出能力范围了?

<del>我还是老老实实做 \mathcal{O}\left(|V|^2\right)s - t 最小割吧……</del>

不要慌,我觉得还行!

这里要介绍一个求解 |V| - 1s - t 最小割的方法Gomory—Hu tree,做法很简单,证明个人认为需要想一会。

对于一个连通无向图 G = (V, E) ,我们尝试构建一个新的树 G' = (V', E') ,其中 V' 中的元素是由 V 中一些点组成的点集(即元素是集合),初始 G' = (\{V\}, \emptyset) ,我们将不断地把 G' 中的点分裂,直到最终 V' 中的每一个元素都是 V 中某一个点组成的点集并在两者之间能形成双射,此时求解 s - t 割即计算 G' 中点 \{s\} 到点 \{t\} 路径上的最小边权值。

分裂是指每次选择一个点集 A \in V' ,满足 A 中至少有两个 V 中的点,并从中选出两个点 s \in A, t \in A ,求解 s - t 最小割 (S, T) ,将 A 划分成 A \cap S, A \cap T 两个点,在它们之间连一条边权值为 w(S, T) 的边,之前与 A 相连的边也根据另一个端点属于 ST 来确定连向 A \cap SA \cap T 即可。

此外,Gomory—Hu tree 也经常作为近似求解 k 连通块最小割的算法例子。


随手写的很仓促,不知道有什么要补充的,待我赶完 deadline 再来修一修 T_T