网络流：添加一个新的边缘 [英] Network Flow: Adding a new edge

问题描述

在最近的一次在compition我被要求设计一个算法之一是，为当V顶点和E边的网络，当加入一条边（它的容量应为1）结果在增加的最大流量。这是我们要设计这样一个algoritm找到这样的边缘。

In the recent time in one of the compition I have been asked to design an algorithm that, for a network having V vertices and E edges, if by adding an edge (it's capacity should be 1) results in increase the maximum flow. that is we have to design such an algoritm to find such edges.

算法应该再快 O（| E | * H（| V || E |）），其中 H（| V || E |）的时间在计算最大流量采取

Algorithm should be faster then O(|E|* h(|V||E|)) where h(|V||E|) is time taken in computing maximum flow.

在此先感谢。让我知道，如果现在还不清楚。

Thanks in advance. Let me know if it is unclear.

推荐答案

（什么菲利普说，修正版。）计算的最大流量。提取一个无容量限制，包括导演用积极的剩余容量圆弧曲线。增加一个特定的弧增加的最大流量，当且仅当有到尾部和从头部到接收器，即从源极路径，引入电弧产生一个增广路

(Corrected version of what Philip said.) Compute a maximum flow. Extract an uncapacitated, directed graph consisting of the arcs with positive residual capacity. Adding a particular arc increases the maximum flow if and only if there are paths from the source to the tail and from the head to the sink, i.e., the introduction of the arc creates an augmenting path.

在您的例子 {S-＆GT; A，A-＆GT; B，A-＆GT; C，A-＆GT; D，B-＆GT;吨，C＆GT; T，D - ＆GT;吨} ，最大流量 S-3＆GT; A，A-1＆GT; B，A-1＆GT; C，A-1＆GT; D，B-1＆GT ; T，C-1＆GT; T，D-1＆GT;吨，剩余图有每一个落后的弧形 {A-＆GT; S，B＆GT; A，C - ＆gt;一种，D＆GT; A，叔＆GT; B，叔＆GT; C，T-D 1和D} 。顶点可达的距离取值是 {S} 和 T 是【T】，所以唯一的单弧，可以增加最大流量 S-＆GT;吨。

In your example {s->a, a->b, a->c, a->d, b->t, c->t, d->t}, the maximum flow is s-3>a, a-1>b, a-1>c, a-1>d, b-1>t, c-1>t, d-1>t, and the residual graph has every backward arc {a->s, b->a, c->a, d->a, t->b, t->c, t->d}. The vertices reachable from s are {s} and the vertices reachable from t are {t}, so the only single arc that could increase the max flow is s->t.

这篇关于网络流：添加一个新的边缘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！