algorithm - 最短路径长度与最小切割能力的关系

Question

在每个弧容量为 1 且从 s 到 t 的最短长度为 k 的图 G 中，最小容量 st 切割为 O(n^2/k^2)，其中 n 是顶点数。n 选择 2 给出 O(n^2) 弧数，我不确定如何进一步推理以证明该陈述的合理性。如果我认为每条 st 路径都是 k 长，那给了我 O(n^2/k) 可能的交叉点。也许我的想法不太对。任何类型的输入将不胜感激

标签： algorithmgraph-algorithmford-fulkerson