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

您已经找到了想要的答案。我希望这对某人有所帮助。