给定一个流网络 G = (V,E)，其源为 s，汇为 t，边 e = (u,v)，描述一种算法来确定边 e 是否与某个最小割 (S,T) 相交。
我的第一个想法是计算最大流量 f，然后将 e 的容量减少一些 a > 0。然后我们检查残差图是否有从 s 到 t 的路径（这意味着我们可以进一步增加流量 f） .
现在，如果没有从 s 到 t 的路径，我们可以确定 e 不会越过任何最小割。
问题在于另一个方向。如果有一条从 s 到 t 的路径，那可能是因为我们在选择 a > 0 时不小心创建了一个新的最小割使 e 交叉。
那么如何选择足够小的 a > 0 呢？
这是一个很酷的问题。
“我的第一个想法是计算最大流量 f，然后将 e 的容量减少一些...”
你是说增加吗？因为如果你减少容量，流量就不会增长..
反正：
运行算法以找到最大流量并假设流量为 F。
检查e上流动的流量是否等于它的容量，如果不是，则返回false。
这是否意味着如果它相等，e必须穿过一些最小切割？
假设 e=(u,v)：由于边缘规则，进入 u 的流必须完全离开，
这意味着对于您将进行的每一次削减，都会有一些 e crooses it and e=(x,y)，
我们将有一些从 u->v....->x 或 y->....u->v 的路径。
如果我们将删除这条边（e），并且流量将减少，这意味着我们无论如何都不能返回到达 x 的流量（或者离开 y 的流量现在无法找到通往水槽的路）为那是以前。这意味着 e 在某个最小范围内。
如果流量没有改变，那只意味着我们找到了另一种方法来返回我们“丢失”的流量，这意味着 e 不属于任何最小切割，因为它不影响任何等于最大流量的最小切割容量。
您对问题的直觉很好，但请注意它不会起作用，因为 e 的增加/减少可能导致没有办法，因为有一个简单的例子，您改变 e 的容量并且仍然没有从 s 到 t 的路径残差网络，但 e 仍然属于某个最小割。