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

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. 将带有边的源顶点 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

你有你正在寻找的答案。我希望这对某人有所帮助。