max-flow - 最大流量和最小切割的对偶性：当存在无限容量时

Question

我想知道 max-flow 和 min-cut 之间著名的二元性是否真的可以容忍无限的价值容量。这是一个似乎不是的简单示例：

源 s、汇 t、其他五个节点 a、b、c、d、e

s -> a: 容量 3

s -> b: 3

a -> c: \infty

a -> d: \infty

b -> d: \infty

b -> e: \infty

c -> t: 1

d -> t: 1

e -> t: 4

最大流量为 5。但是，没有容量为 5 的切割。这是因为无限容量迫使所有 a、b、c、d、e 属于同一集合/切割的一半（否则会有割集中的一个 \infty 权重）。

Answer 1

哦，我忘了，在有向图的时候，一条边（u，v）要计入cut weight，u和v不仅应该属于cut的不同半边，而且u应该在同一个半边作为源 s，而 v 与接收器 t 在同一半。

所以现在有一个容量为 5 的平凡割： S = {s, a, c, d} T = {b, e, t}

Answer 2

确实如此，但前提是至少有一个容量有限的切割。否则，如您的示例所示，它不会提供有关最大流量的信息。