天道酬勤,学无止境

network-flow

找到最小切割中的所有边(Find all edges in min-cut)

问题 让 (G,s,t,{c}) 是一个流网络,让 F 是所有边 e 的集合,其中存在至少一个最小割 (A,B) 使得 e 从 A 到 B。给出一个多项式时间算法,找出 F 中的所有边。 注意:到目前为止,我知道我需要运行 Ford-Fulkerson,这样每个边都有一个流。 此外,我知道对于 F 中的所有边,流 f(e) = c(e)。 然而,并非图 G 中所有遵守该约束的边都在最小切割中。 我被困在这里。 回答1 假设您已经计算了图G上的最大流量,并且您知道通过图中每条边的流量。 从源顶点s ,对原始图执行广度优先搜索或深度优先搜索,只遍历那些流量小于边容量的边。 将这次遍历中可到达的顶点集表示为S ,将不可到达的顶点表示为T 。 为了获得最小割C ,我们只需找到原始图G中的所有边,这些边从S中的某个顶点开始,并在T中的某个顶点结束。 Topcoder 中的本教程提供了上述算法的解释/证明。 查看以以下文本开头的部分: 流网络中的切割只是将顶点分成两组,我们称它们为 A 和 B,这样源顶点在 A 中,汇点在 B 中。 我将尝试在 Topcoder 教程中提供相应部分的解释(也只是为了让我复习一下)。 现在,假设我们已经计算了图G上的最大流,并且我们已经使用上面概述的过程计算了边C的集合。 从这里,我们可以得出几个事实。 事实 1:源顶点s必须在集合S ,汇顶点t必须在集合T 。

2021-09-30 05:38:38    分类:技术分享    algorithm   network-flow   minimum-cut

Find all edges in min-cut

Let (G,s,t,{c}) be a flow network, and let F be the set of all edges e for which there exists at least one minimum cut (A,B) such that e goes from A to B. Give a polynomial time algorithm that finds all edges in F. NOTE: So far I know I need to run Ford-Fulkerson so each edges has a flow. Furthermore I know for all edges in F, the flow f(e) = c(e). However not all edges in a graph G which respects that constraint will be in a min-cut. I am stuck here.

2021-09-30 05:10:07    分类:问答    algorithm   network-flow   minimum-cut

使用最大流量,更难的版本为人们分配工作(Assigning jobs to people using Maximum Flow, harder version)

问题 我正在自学最大流量,有这个问题: 原来的问题是 假设我们有一个工作列表 {J1, J1,..., Jm} 以及申请他们的人的名单 {P1, P2, P3,...,Pn} 每个人都有不同的兴趣,其中一些人申请了多个工作(每个人都有一份他们可以做的工作清单) 任何人不得从事超过 3 项工作。 所以,这个问题可以通过在下图中找到最大流量来解决 我理解这个解决方案,但是 问题的更难版本 如果添加这些条件会怎样? 简单版的前3个条件(工作和人员列表,每个人都有一个兴趣或能力列表)仍然相同公司只聘用 Vi 人从事工作 Ji 公司希望雇用尽可能多的人一个人可以从事的工作数量没有限制。 我应该在图中做出什么不同,以便我的解决方案也能满足这些条件?或者如果我需要不同的方法,请告诉我。 在任何人说什么之前,这不是作业。 这只是自学,但我正在研究最大流量,问题出在那个区域,所以解决方案应该使用最大流量。 回答1 对于多人从事一项工作: 从Ji到t的边的容量等于该作业的人数。 例如,如果作业 #1 可以有三个人,这意味着从J1到t的边缘容量为三。 对于招聘尽可能多的人的要求: 我认为这是不可能的单个流程图。 下面是它如何做一个算法: 运行一次流算法。 对于每个人: 尝试将输入容量降低到低于当前流量的一倍。 再次运行流算法。 虽然这不会减少总流量,但从 (2.1.) 开始重复。 将容量增加一倍

2021-07-12 16:23:12    分类:技术分享    algorithm   graph   graph-algorithm   network-flow   ford-fulkerson

Assigning jobs to people using Maximum Flow, harder version

I am self studying max flow and there was this problem: the original problem is Suppose we have a list of jobs {J1, J1,..., Jm} and a list of people that have applied for them {P1, P2, P3,...,Pn} each person have different interests and some of them have applied for multiple jobs (each person has a list of jobs they can do) nobody is allowed to do more than 3 jobs. so, this problem can be solved by finding a maximum flow in the graph below I understand this solution, but the harder version of the problem what if these conditions are added? the first 3 conditions of the easy version (lists of

2021-06-29 05:24:03    分类:问答    algorithm   graph   graph-algorithm   network-flow   ford-fulkerson

全对最大流量(All pair Maximum Flow)

问题 给定一个有向加权图,如何找到所有顶点对之间的最大流(或最小边切割)。 天真的方法是简单地为每对调用像Dinic一样的最大流算法,其复杂度为O((V^2)*E) 。 因此,对于所有对,它都是O((V^4)*E) 。 是否可以通过一些优化将复杂度降低到O((V^3)*E)或O(V^3) ? 回答1 Gomory-Hu Tree不适用于有向图,撇开该观点,Gomory-Hu Tree将通过应用最小切割来形成Graph最大流量。 时间复杂度为: O(|V|-1 * T(minimum-cut)) = O(|V|-1 * O(2|V|-2)) ~ O(|V|^2) *使用最佳的最小切割算法(Max-Flow Min-Cut Reduction) 本示例说明如何从给定图构造Gomory-Hu树 回答2 Gomory-Hu树不适用于有向加权图。 是否存在比在有向图上运行n ^ 2最大流更快地解决所有对最大流的算法,这是一个悬而未决的问题。

2021-05-18 00:11:46    分类:技术分享    graph   max-flow   network-flow

All pair Maximum Flow

Given a directed weighted graph, how to find the Maximum Flow ( or Minimum Edge Cut ) between all pairs of vertices. The naive approach is simply to call a Max Flow algorithm like Dinic's, whose complexity is O((V^2)*E), for each pair. Hence for all pairs it is O((V^4)*E). Is it possible to reduce the complexity to O((V^3)*E) or to O(V^3) by some optimizations?

2021-05-01 16:23:50    分类:问答    graph   max-flow   network-flow