在具有下界的网络中寻找循环

Question

我无法理解如何在具有下限（不是需求）的网络中找到循环流。我找到了下一个包含问题描述和解决策略的文档：

1. https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf
2. http://homes.cs.washington.edu/~anderson/iucee/Slides_421_06/Lecture24_25_26.pdf
3. http://web.engr.illinois.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf

让我们考虑一个具有以下边的网络（l - 下限，c - 容量）：

1 -> 2 : l = 1 c = 3

2 -> 3 : l = 2 c = 4

3 -> 1 : l = 1 c = 2

据我了解，要解决这个问题，我们应该采取以下步骤：

1. 把这个问题转化为“有需求的流通问题”。这可以通过下一个公式 dv' = dv - (Lin - Lout) 来完成，其中 'dv' 是原始顶点需求（在我们的例子中它等于 0），'Lin' - 顶点输入边下界的总和，以及 ' Lout' - 顶点输出边下界的总和。
2. 将边容量更新为 c' = c - l
3. 将带有边的源顶点 S 添加到 dv < 0 且容量为“-dv”的每个顶点
4. 添加接收器顶点 T 和每个顶点的边，dv > 0，容量为“dv”
5. 使用任何算法（例如 Edmonds-Karp 算法）在新网络中找到最大流量。
6. 如果最大流的值等于与 T 连接的顶点的所有需求之和，则网络中存在循环。

执行这些步骤后，新网络将是：

S -> 2 : c = 1

2 -> 3 : c = 2

3 -> T : c = 1

1 -> 2 : c = 2

3 -> 1：c = 1

对顶点的要求：

d1 = 0

d2 = -1

d3 = 1

我们看到最大流量等于 1，等于到 T 的边之和也是 1。它覆盖了边 A->2->3->T。

问题是如何在具有原始边界的原始网络中获得循环流？

原始网络中存在流通流——我们只需要为所有边分配等于 2 的流。

Answer 1

有点晚了，但我在研究这个问题的解决方案时偶然发现了这个问题。

如果你用另一种方式来做，那就是：

1. 第 1 步和第 2 步如您的问题所示。
2. 将带有边的顶点 S 添加到 dv > 0 且容量为“dv”的每个顶点
3. 添加顶点 T，其中每个顶点的边 dv < 0，容量为“-dv”

此后，任何最大流算法找到的解决方案将是：

• S->3：c=1
• 3->1：c=1
• 1->2：c=1
• 2->T：c=1

您现在需要做的只是将下界值添加到前面步骤的结果中。在这种情况下：

• 1->2：c=1，l=1，c+l = 2
• 2->3：c=0，l=2，c+l=2
• 3->1：c=1，l=1，c+l = 2

您已经找到了您正在寻找的答案。我希望这对某人有帮助。