在O(V+E)中寻找图的瓶颈边
首先，我想澄清一下我看到的情况：Finding 'bottleneck edges' in a graph 而且这并不是重复，只是不幸的巧合，那个人错误地将Minin-Cut称为“瓶颈”。 瓶颈边是流网络中的一条边，在增加时会增加网络的最大流量。 所以这不一定是最小割，就像o-1->o-1->o这样的图一样，我们没有瓶颈边，但我们确实有最小割。 (在该示例中，o是节点，边是
..
network-flow相关内容
究竟什么是增广路径?
在谈到计算网络流时，算法设计手册说: 传统的网络流算法基于增加路径的思想，并反复寻找从s到t的正容量路径并将其添加到流中.可以证明通过网络的流是最优的当且仅当它不包含增广路径. 我不明白什么是增强路径.我用谷歌搜索，发现: Wolfram 中的增强路径 维基中的流网络 但他们都参考了上面的引用. 谁能真正清楚地解释一下什么是增强路径? 解决方案 增广路径
..
是否有一种算法可以在无向图中找到分离源和汇的最小割
我有一个边加权无向图和 2 个节点(通常称为源和汇).我需要找到一组权重最小的边，将这 2 个节点分成 2 个弱分量. 我了解 Ford-Fulkerson 的最大流算法 和他的定理关于有向图上的最大流和最小割关系. 我还知道对无向图的 Ford-Fulkerson 最大流算法进行了修改，该算法将每个无向边替换为 2 个相反的有向边，并同时更新流向它们两个.但是有了这个修改，最大流最小
..
Ford-Fulkerson 方法在具有单位容量边的流动网络中的时间复杂度
Ford-Fulkerson 算法是否会在n 个顶点和m 个边的单位容量流网络(所有边都有单位容量)中找到最大流>O(mn) 时间? 解决方案 O(M*f) 是 Ford-Fulkerson 在整数容量图上的已知运行时间估计，其中 M 是边的数量，f 是最大流的值，因为很容易在 O(M) 中找到增广路径，并且每个这样的路径至少使流量增加 1. 如果你的图没有重复的边(也就是说，没有一
..
如何在多源流网络中找到最大流量？
如何将这种多源流网络转换为单源流网络并在其中找到最大流？ 解决方案 您创建一个虚拟源节点，称为 Source ，并从中绘制接近无限容量的有向边（例如，图的所有边的容量之和） 来源每个战车。结果图中的每个流都与原始多源图中的一一对应。
..
在最小切割中找到所有边缘
让（G，s，t，{c}）为流动网络，令F为所有边缘e的集合，对于这些边缘e至少存在一个最小割点（A，B），使得e来自A给出一个可以找到F中所有边的多项式时间算法。 注意：到目前为止，我知道我需要运行Ford-Fulkerson，以便每个边都有一个流。而且我知道对于F中的所有边，流f（e）= c（e）。但是，图G中并非所有遵守该约束的边都将处于最小切割状态。我被困在这里。 解决方案 假
..
最低成本流-R中的网络优化
我正在尝试在中实施"最低成本网络流量"运输问题解决方案R. 我知道可以使用lpSolve之类的方法从头开始实现.但是，我看到有一个方便的igraph实施方式，用于"最大流量".这种预先存在的解决方案会方便得多，但是我找不到最低成本的等效功能. 是否存在用于计算最低成本网络流解决方案的igraph函数，或者是否可以将igraph::max_flow函数应用于最低成本问题? igra
..
所有配对最大流量
给定一个有向加权图，如何找到所有顶点对之间的最大流量（或 Minimum Edge Cut ）。 简单的方法很简单调用像Dinic's这样的Max Flow流程算法，其复杂性为每对 O（（V ^ 2）* E）。 > 因此，对于所有的对，它是 O（（V ^ 4）* E）。 是否有可能将复杂度降至 O（（V ^ 3）* E）或 O（V ^ 3）通过一些优化？ 解决方案 Gomory-
..
增强路径究竟是什么？
当谈到计算网络流量时，算法设计手册说： 传统的网络流算法基于扩充路径的思想，并反复找到从s到t的正面容量的路径，并将其添加到流程中。可以看出，当且仅当不包含扩充路径时，通过网络的流量是最佳的。 我不明白什么是增补路径。我已经google了，发现： Wolfram的增强路径 Wiki中的流网络 但是它们都引用上面的报价。 任何人都可以真正清楚解释什么是扩充路径？
..
分配作业使用最大流量的人，很难版
我的自我学习的最大流量，有这个问题： 原来的问题是 假设我们有作业列表 {J1，J1，...，JM} 和已申请了他们的人的名单 {P1，P2，P3，...，PN} 每个人有不同的利益，其中有些已经申请了多个作业（每个人都有工作，他们可以做一个列表） 没有人被允许做3个以上的就业机会。 所以，这个问题可以通过寻找在下面的图中的一个最大流量解决 我理解这个解决方案，但 问题的较
..
计算最小的 - 切在向加权图使用maxflow算法
我一直使用福特Fulkerson算法计算出的最大流量，现在我要实现项目的选择问题，我需要计算最大。没有。可行的设计项目需要找到不包含一个min.cut。可行的项目，最大的利润。 应该用什么算法来找到分钟。切*知道max.flow在图形之后。我*如何使用最大流量来确定切割含有即没有。节点有助于最大flow.I的需要选择最优节点集，使得收入maximisied。在我的申请的每个节点都与一个相关联的收入
..
图 - 究竟是增广路径？
当谈到计算网络流量，href="http://www.algorist.com/">算法设计手册说 传统的网络流算法是基于增广路径，然后反复地寻找从的积极容量到t的路径，并将其添加到流的想法。它可以证明，通过网络流是最佳的，当且仅当它不包含增广路 我不明白什么是增广路径。我用Google搜索，结果发现： 中钨增广路 流网络在维基 等。 但他们都提到上面的报价。 任何人都可以请真正
..
修改最大流算法
我试图解决有关最大流问题的问题。我有一个源和两个水槽。我需要找到在这个网络中的最大流量。这部分是通用最大流。但是，这两个指标都得到了最大流问题的这一特殊版本的流量相同。 是否有任何人谁可以帮助我该怎么做才能做到这一点？ 解决方案 让取值是你的源点和 T1 和 T2 的两个水槽。 您可以使用下面的算法： 通过连接使用常规最大流和两个洗手池，例如 T1 和 T2 到通过与无限容量的边缘超
..