algorithm - 计算有向图中不同 st 割的数量

Question

我试图在有向未加权图中找到不同 st 削减的数量。在一篇文章Enumeration in Graphs p 中。45 我找到了列举这些削减的好方法（第 7.3 节）。如果我只对此类削减的数量感兴趣并且我实际上不需要枚举它，是否可以使用更快或更简单的算法？

我正在使用的 st cut 的定义如下。我们有一个有向图，其中两个顶点标记为S和T。Cut 是图的最小边集，通过删除这些边，将不再存在从顶点S到顶点T的路径。

Answer 1

CSteory.StackExchange 就是这个地方！我的问题在那里得到了否定的回答。