在具有下限的网络中找到循环

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' 是原始顶点需求（在我们的例子中它等于零），'Lin' - 顶点输入边下界之和，以及 ' Lout' - 顶点输出边下界之和。
2. 将边容量更新为 c' = c - l
3. 使用 dv 将带有边的源顶点 S 添加到每个顶点 < 0 with capacities '-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. 使用 dv 添加顶点 T 以及每个顶点的边 < 0 with capacities '-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

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

Answer 2

感谢@Adis 和@RegyN 的帮助。补充一点。 如果经过此处描述的步骤后，最终出现多个具有 +ve 流或 -ve 流的节点，则该网络中不可能存在循环。