algorithm - 根据 s 和 t 顶点之间的最小切割将图分成两部分

Question

我正在实现最小切割图聚类，我需要能够拆分一个图分为两部分 S 和 T 根据 st min-cut 我在每个聚类步骤上构建一些 s 和 t 顶点。基本上，我想要一个函数，它接受一个图 G、一个节点 s 和一个节点 t 并返回两个不相交的节点集S 和 T。

据我所知，找到 st min-cut 的最简单方法是利用 min-cut ~ max-flow duality 并使用Push-relabel algorithm 进行最大流计算。但是 push-relabel 算法没有给我们任何关于什么是 S 和 T 集的信息。

那么，得到S和T最小割子集的正确方法是什么？有没有办法使用 Push-relabel 算法？有没有用 C++ 或 Python 实现的？

Answer 1

您可以使用 push-relabel 算法计算的信息来确定最小切割。如您所知，push-relabel 算法为每个顶点 v 分配一个值 h(v)。 h(v) 的可能值在区间 [0,N] 内，其中 N 是图的顶点数。很容易证明存在一些数 h' 使得 h(v) != h' 对于每个顶点 v(见练习 26.4 -3 Cormen 的书，第 2 版)。在找到这样的 h' 之后，每个 h(v) < h' 的顶点 v 都在切割的一侧，并且每个顶点 < em>u 和 h(u) > h' 在另一边。