algorithm - 根据 s 和 t 顶点之间的 min-cut 将图分成两部分

Question

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

据我所知，找到 st min-cut 的最简单方法是利用 min-cut ~ max-flow duality 并使用Push-relabel 算法进行 max-flow 计算。但是 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'使得每个顶点v的 h(v) != h'（参见 Cormen 的书第 2 版的练习 26.4-3）。找到这样的 h'后，每个h(v) < h'的顶点v都在切口的一侧，而每个h(u) > h'的顶点u都在另一侧。