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

我不明白如何在网络中找到下限(不是要求)的循环流。我找到了包含问题描述和解决策略的下一个文档:

https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf

http://homes.cs.washington.edu/~anderson/iucee/Slides_421_06/Lecture24_25_26.pdf

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

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

将此问题转换为“按需流通问题”。可以使用下一个公式dv'= dv-(Lin-Lout)完成，其中'dv'是原始顶点需求(在我们的示例中为零)，'Lin'-顶点输入边的下限之和，以及' Lout'-顶点输出边缘下限的总和。

将边缘容量更新为c'= c-l

将具有边的源顶点S添加到dv

添加宿顶点T，其每个顶点的边的dv> 0且容量为'dv'。

使用任何算法(例如Edmonds-Karp算法)在新网络中找到最大流量。

如果最大流量的值等于与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的流即可。

最佳答案

为时已晚，但是在研究此问题的解决方案时我偶然发现了这个问题。

如果您以另一种方式这样做，那就是:

步骤1和步骤2，与您的问题相同。

将具有边的顶点S添加到dv> 0且容量为'dv'的每个顶点中

将顶点T与每个顶点的边相加，且dv '-dv'

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

S-> 3:c = 1

3-> 1:c = 1

1-> 2:c = 1

2-> T:c = 1

您现在要做的只是将下限的值添加到先前步骤的结果中。在这种情况下:

1-> 2:c = 1，l = 1，c + 1 = 2

2-> 3:c = 0，l = 2，c + 1 = 2

3-> 1:c = 1，l = 1，c + l = 2

这样您就可以找到想要的答案。希望对您有所帮助。

关于algorithm - 在具有下界的网络中寻找循环，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40752549/