graph - 在图中找到所有切割的算法

Question

我正在寻找一种有效的算法，它可以帮助我列出图表中的所有切口。该图是一个流网络（有向图），具有固定的源和汇。我想找出所有可能的切割集，一侧为源，另一侧为下沉。

请注意，优先级是找到所有割集，而不是最小割。

例如，考虑具有以下边列表的图： s-->a-->t s-->b-->t

上图的割集是：{sa,sb}, {at,bt}, {sa,sb,at}, {sa,sb,bt}, {sa,sb,at,bt}

Answer 1

它不能有效，因为您有指数级的削减量。你有源是 S，T 中的汇，其中 ST 是切割。现在想一想：对于每个顶点，它可以在 S 中，也可以在 T 中。将所有顶点视为一个长二进制数，其中 1 表示顶点 i 在 S 中，0 表示它在 T 中。

你有多少选择？如果你有 n 个顶点，你可以有多少个不同的二进制数？答案是 2^n，但我们可以忽略水槽和水槽，但它不是母亲，我们仍然有 O(2^n) 用于不同的切割。