algorithm - 网络流量中s-t流量、流量值和最大流量的区别

Question

我试图通过阅读 Klienberg 和 Tardos 的书来理解网络流。我对理解以下术语以及每当我们执行扩充时这些术语的值如何变化有疑问。这是我到现在为止所理解的。如有不妥请指正

1. s-t flow - 这是一个随机路径 P，可以在任何图 G 中找到，以承载来自 s 的流 到 t
2. 流量值(value) - 这表示源产生的流量
3. 最大流量 - 这是我遇到问题的地方。我无法理解流量值和最大流量之间的区别。最大流量是否表示特定图 G 中可以承载流量的所有 s-t 路径的总和，还是表示这些 s-t 路径中的最大值？

如有任何帮助，我们将不胜感激。谢谢

Answer 1

Flow 是沿所有边缘流出 s(或进入 t，必须相同)的流量总和。流从 0 开始，在一个流算法的各个阶段，随着我们找到越来越多的流路径并将它们添加到整体流中，它会逐渐增加。在某些时候，我们找不到更多的流动路径；那么，我们就得到了maximum flow(流量的最大可能值)。所以最大流量也是流出s(或进入t)的所有边的流量之和，但仅在不再可能发送的点更多流量。

附言我没有 Kleinberg/Tardos，但你确定你对 s-t flow 的定义是正确的吗？如果是这样，我知道这听起来很困惑，因为“流程”通常指的是整体流程。 Cormen/Leiserson/Rivest/Stein 使用我认为更常见的术语增强路径。