问题标签 [network-flow]

我们都知道，网络流的问题可以归结为线性规划。但是，当我们解决网络流量问题时，我们需要流量始终是整数。所以我认为网络流量应该简化为整数线性规划。由于ILP是NP完全的，网络流量问题也应该是NP完全问题。但这与我们所学到的相矛盾，因为网络流的运行时间是 O(Cm)！我哪里错了？是因为网络流问题的运行时间是像背包问题（Wn）这样的伪多项式时间吗？我现在很困惑！

不知何故，我创建了这个图表，它似乎违反了流量值上限为最小切割容量的属性之一。
这是图表：

算法找到的最大流量为 7。（在 sact 上发送 3，在 sbt 上发送 3，在 sat 上发送 1）
而图中的最小切割是 {s,b} ，{a,c,t} 容量为 5。
我'我不确定我在哪里出错了。有人可以纠正这个吗？

积分定理告诉我们，如果流网络中的所有容量都是整数，那么存在一个最大流，其中每个值都是整数

但最显着的部分是存在，不是每一个最​​大流量！这意味着该语句并未声称每个最大流量都是整数值

我无法弄清楚为什么如果所有容量都是整数，但存在最大流量不是整数值！

还是我只是对试图告诉我的这个定理有错误的想法？

我试图解决一个关于最大流量问题的问题。我有一个源和两个接收器。我需要在这个网络中找到一个最大流量。这部分是一般的最大流量。但是，在这个特殊版本的最大流量问题中，两个目标都必须获得相同的流量。

有没有人可以帮助我该怎么做？

令 (G,s,t,{c}) 为流网络，令 F 为所有边 e 的集合，其中至少存在一个最小割 (A,B)，使得 e 从 A 到 B。给出一个多项式时间算法，找出 F 中的所有边。

注意：到目前为止，我知道我需要运行 Ford-Fulkerson，以便每个边缘都有一个流程。此外，我知道对于 F 中的所有边，流 f(e) = c(e)。然而，图 G 中并非所有尊重该约束的边都将处于最小切割中。我被困在这里。

我希望在具有有向和无向边的图上实现（或使用库，如果已经存在）Max Flow 算法，并将其可视化。我倾向于 JavaScript。我知道 d3.js 和 arbor.js 允许交互式图形可视化，但是有推荐的方法来可视化从节点到节点的实际流吗？这是为了演示理论计算机科学中的一些概念。

理想的图将能够显示边容量、边成本（与容量不同）和节点名称，边可以是单向（有向）或双向（双向，指向两个节点的箭头，或者只是没有箭头这根本不是两个独立的有向边）。

任何有关图形可视化工具的建议 - 您可以看到从边缘到边缘的流程 - 将不胜感激。

注意：如果有人知道允许这种可视化的好框架/库，我不反对使用 Python 或其他语言。

谢谢。

我正在研究算法分析。我目前正在阅读Network Flow算法。我正在考虑应用Network Flow有关寻找bipartite matchings最低成本的算法。

• 让G对应的网络流G'
• 让M我们perfect matching进入G
• 让G<sub>M</sub>与residual graph此匹配相关联

来自 Jon Kleinberg 和 Eva Tardos 的算法设计7.13 第 406 页，

Theorem 7.62状态：

(7.62) 令 M 为完美匹配。_{如果 G M}中存在负成本有向循环 C ，则 M 不是最小成本

这个定理是有道理的，但是，我对 abipartite flow network's residual graph的 aperfect matching如何实际上包含一个循环感到困惑。我可以看到一个循环的唯一方法是是否涉及sink或source。

然而，在 aperfect matching中将source不包含离开它的边缘，并且在sink将不包含进入它的边缘。此外，内部节点中发生的循环似乎与 a 的定义相矛盾Bipartite graph。

有人可以在残差图中提供这样一个循环的例子吗？

最大流量和最大流量有什么区别。我在研究福特富尔克森算法时正在阅读这些术语，它们非常令人困惑。我在互联网上尝试过，但无法得到合理的答案。我相信最大流量很清楚，因为它意味着可以在网络中从源传输到接收器的最大流量，但最大流量到底是什么。

如果可能，请用外行的方式回答。

谢谢。

我正在尝试解决以下问题，但我的算法太慢了。那是因为我正在使用Edmonds - Karp 算法来找到最大流量，当应用于二分图时，它也能提供最大匹配。它的运行时间是n^5。我想知道任何更快的算法来解决这个问题（特别是二分图）。我目前正在研究的一种算法是Relabel to Front，即 n^3。

我目前在大学研究流网络，我的教授向我们提出了这个定理：“给定一个流网络，其中有一个流 B，因此对于每个顶点，除了源和汇：| B(e) 的 ∑(e:u→v) - B(e')的∑(e':v→u) | ≤ε。

注意：这个等式适用于每个 v（不是网络中源或汇的顶点）。e:u→v 意味着我想要在割集中从 u 的集合到 v 的集合的每条边的 B(e) 的总和。然后，e':v→u 意味着我想要从 v 的集合到 u 的集合的每条边的 B(e) 的总和。

存在一个新流 F，对于图中的每条边，|F(e)-B(e)|<ε*N（其中 N 是图中的顶点数）。”</p>

他声称存在证据，但我无法深究。我在考虑 Epsilon 的下限是图的最小切割这一事实，但我所拥有的所有其他想法都是无用的。我会很感激任何帮助。我在网上搜索了证据，但找不到任何东西。

提前致谢，或者