问题标签 [max-flow]

我通过以下方式在 boost 中创建了一个图表：

然后我在它上面运行最大流量：

在此之后，我创建了该图的副本 g_copy.H：

主要：

将 s 和 t 更改为新的 s' 和 t'，然后再次运行最大流，这次是在复制的图 g_copy.H 上：

如果我查看原始图的剩余容量，g，它们在 new_flow = boost::edmonds_karp_max_flow(g_copy.H, s', t'); 以前有人有同样的问题吗？我在这里做错了什么导致原始图的剩余容量发生了这种意外变化吗？感谢任何帮助或反馈！

这就是我设法复制图表的方式：

我正在尝试使用有向图解决最小成本流问题的修改实例。具体来说，源和目标对是固定的，每条边都有单位成本但容量有限。我想最小化总和（流量）/边缘。我有两个与此相关的查询：

1. 如果每个流程从源到目的地都有一条路径，我应该如何进行？一种解决方案可能是使用最短路径算法（例如 Dijkstra），但只考虑可以完全适应流的路径。这可以通过迭代求解每个流并每次更新边缘容量来完成。我回顾了与最小成本和最大流量问题相关的文献，它们都假设任何商品都可以从任何来源流向任何目的地（考虑同类型商品的需求和供应）。我的问题是独一无二的，它包含固定的源和目标对。是否有针对这种特定情况的算法？
2. 如果我考虑拆分流，即每个流可以采用多条路径，那么解决方案是什么？

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

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 的流分配给所有边。

我需要解释究竟什么是节点不相交的路径？以及如何确定有向图中两个节点 Source(s) 和 Sink(t) 之间的节点不相交路径的最大数量。任何人都可以用图形解释。

给定一个无向图 G=V,E, 2 个顶点：x, y 和边 e，

我想检查是否有一条从 x 到 y 的路径包含给定的边 e。

我的想法：通过定义一个网络流来解决这个问题，其中 x 和 y 是源和汇，并检查 e 中的流是否大于 0，这意味着存在路径。但是有两个问题：

1. 我不知道如何指向边缘
2. 每个边缘的容量是多少？

所以我猜这不是正确的方法......如果有人能给出一个想法，那就太好了。

这个证明到处都被跳过了，据说是 Min-Cut-Max-Flow 定理的推论......它通常是这样的：

令 S1 和 S2 为流网络的最小割。那么 S1∪S1 和 S1∩S2 也是最小割。

谁能告诉我这是如何证明的？

最大流问题通常通过 edmond-karp 算法来解决，该算法构建残差图，并使用 BFS 寻找增广路径。

但通常最大流量问题是为加权图定义的。对于未加权的图，我们可以简单地将每条边的权重视为1，但我想知道是否有更简单的算法来解决未加权的版本。

我正在尝试使用具有无限权重边但每个节点都有容量的图来解决最大流量问题。我使用福特富尔克森算法解决了这个问题，并将每个节点分成一个输入节点和一个输出节点，容量是两者之间的加权边。当我在边缘硬编码时，我的算法效果很好（请参阅代码中的注释块），但当我尝试从文本文件构建边缘时总是返回零。对于我的生活，我无法弄清楚为什么，我已经检查以确保所有边缘都被正确构建，并且无法弄清楚出了什么问题。

用于读取图形的文本文件（第 1 行是边，第 2 行是节点容量） (1 2) (2 3) (2 5) (3 4) (4 5) (3 5) (2 1500) (3 1000) ( 4 800)

边缘类

我正在使用NetworkX来解决具有多个源和接收器的最大流量问题。我发现了一个在 NetworkX 中运行良好的函数，max_cost_flow但我遇到的问题是它要求净需求为零，换句话说，任何接收器都不应低于它的需要，否则会引发错误。

我可以使用什么（或如何修改此算法）来允许它计算最佳可能流量，而不一定满足所有条件？

根据 kraskevich 的建议：

我正在阅读有关最大流量定理的内容，在那里我看到了找到最小 st 切割的场景。但是无论我在哪里搜索，他们都是在知道最大流量（如这里）或通过迭代几乎所有（如这里）猜测削减后才这样做的。

是否有一种合乎逻辑的方法可以在不知道最大流量或猜测切割的情况下达到最小切割（使用路径）？

补充思想：在一个说 N 个顶点的图中，说一个是源's'，另一个是接收器't'。所以有 2^(N-2) 个可能的 st 分组。即使对于 N = 8，这也是巨大的。所以迭代是获得答案的唯一方法。有人告诉我，这是在考试中被问到的。在限时考试中要求这样一个迭代过程是否公平。如果没有检查所有（或没有给出最大流量值），如何确定他已经得出了正确的答案？例如。按照此处的说明找到最小切割。