问题标签 [network-flow]

Ford-Fulkerson 算法是否会及时找到具有n顶点和m边的单位容量流网络（所有边都有单位容量）的最大流O(mn)？

我有一个有向的彩色图（每个节点都有一种颜色），我想找出从节点 A 到节点 B 的路径是否存在，使得路径在 MOST 处通过每种颜色一次。

我认为这个问题可以用网络流来表述。以某种方式可以在相同颜色的节点上放置惩罚，如果节点重复，则使流为 0 或无穷大。

谢谢！

我已经实现了 Ford Fulkerson 算法，现在正在尝试研究它的变体。

假设给定的图及其解决方案是

假设在导出解之后，其中一条边的容量增加或减少。我们需要找到一种算法来使用当前解决方案而不是从一开始就获得新的最大流量。

我的建议是，对于这个例子，如果我们假设 1-3 边的容量从 12 减少到 8，那么我们需要从 1 到开始节点进行 BFS，并将每个边上的流量减少 4 并且做一个 BFS 从 3 到 5 并减少那里的流量。但我不确定这是否正确。即使它是正确的，我也不知道如何实现它？

谁可以帮我这个事？

我有一个带有两组顶点 A 和 B 的二部图。边没有权重。但是，其中一个集合（比如集合 B）中的顶点具有分配给它们的正权重（wb1，wb2 ...）我想在这个二分图中找到一个匹配，以便最大化从集合匹配的顶点的权重B.

经过广泛的在线搜索，这就是我想出的：将权重 wbi 分配给顶点 bi 上的所有边缘并运行匈牙利算法。有没有更有效的方法来看待这个问题，因为它不同于加权最大匹配（这里顶点具有权重而不是边）

如果我的语言不清楚，请随时编辑。谢谢你。

我希望这不是重复的，但我似乎找不到这个问题的具体答案。我对 Python 很陌生，所以这可能很明显，但我似乎找不到我的错误。

所以问题是：我正在使用 gurobi 来优化网络流模型。但是我在制定约束时遇到了一些麻烦，因为我必须迭代 2 个变量（我想这就是问题所在）。

首先是代码：

不工作的部分是：

错误是：'Var'类型不可迭代例如在Java中我可以通过p和i的两个循环来完成它（在Python中试过，没有用），但我不知道如何解决这个问题用 Python。

先感谢您

最小成本流问题的完整性定理指出，给定“整数数据”，总是存在对应于最小成本流的问题的整体解。积分数据的概念对我来说有点混乱，因为大多数论文、教程都说需求、供应和容量应该是积分的。现在，容量约束通常表示为

其中l_i是 edge 容量的下界i，u_i是上界。为了使完整性定理成立，l_i and u_i整数就足够了吗？怀疑来自这样一个事实，这并不一定意味着流本身总是整数，例如，对于l_i = 0, u_i = 1，边缘i可以有 0.5 的流。

我想将 Dinic 的算法与动态树一起应用。但我找到的来源很少。特别是关于动态树。如果有一个带有详细解释的好的源代码或一些使用动态树的简单源代码，那就太好了。

有没有人遇到过这样的事情？提前致谢

嘿，所以我有一个图，例如 3 条边进入一个节点，3 条边出来，但是如果一个特定的输入边有容量，我只需要激活输出边。例如，如果我们有：

A -> N

B -> N

C -> N

N -> N'

N' -> A'

N' -> B'

N' -> C'

如果 A 有流量，我只想流过 A'，如果 B 有流量等，我只想流过 B'。

基本上它是边缘 A、B、C 的容量限制器，我最初无法限制它们的容量。

假设这种情况发生多次，我如何将此约束添加到最大流量并解决给定图的最大流量图问题？

编辑：我最终也不能限制它们的容量，因为稍后会在图中使用 A'、B' 和 C'，所以我不能将 N 和 N' 移动到最后并在以后强制组合容量减少。

我有一个边加权无向图和 2 个节点（通常称为源和汇）。我需要找到一组可能权重最小的边，将这 2 个节点分成 2 个弱分量。

我知道Ford-Fulkerson 的最大流算法和他关于有向图上的最大流和最小割关系的定理。

我还知道 Ford-Fulkerson 的无向图最大流算法的修改，它用 2 个相反的有向边替换每个无向边，并同时更新流向它们的流。但是通过这种修改，max-flow-min-cut-theorem 似乎不再有效，因为在以下无向图中，将无法正确确定最小切割：

最大流最小割定理说，最小割是那些边，流动等于它们的容量，而通过修改后的福特-富克森就是所有的边，这显然不是正确的割。

我找到了一个Stoer–Wagner 算法，用于在无向图中找到全局最小割，但这不是我想要的，因为该算法不考虑任何源和汇，并且可以找到一个让节点位于的割相同的组件。

是否有任何算法可以有效地在具有源和汇的无向图中找到最小割，将这两个指定节点分开？我可以以某种方式修改前面提到的算法以使它们适用于我的情况吗？

当 Edmonds-Karp 算法说沿路径 p 增加流量 f 时，增加流量实际上意味着什么？这是否意味着沿着路径发送流量？