[Math] maximum flow ford-fulkerson analysis

algorithmsgraph theorynetwork-flow

I am reading about maximum flows in Introduction to algorithms by Cormen etc.

Ford-Fulkerson algorithm is given below.

FORD-FULKERSON(G, s, t)

1  for each edge (u, v) in E[G]

2       do â[u, v]  0

3          â[v, u]  0

4  while there exists a path p from s to t in the residual network Gâ

5      do câ(p)  min {câ(u, v) : (u, v) is in p}

6         for each edge (u, v) in p

7             do â[u, v]  â[u, v]+câ(p)

8                â[v, u]  - â[u, v]

While analyzing above algorithm author is mentioned as below.

The work done within the while loop can be made efficient if we
efficiently manage the data structure used to implement the network G
= (V, E). Let us assume that we keep a data structure corresponding to a directed graph G' = (V, E'), where E' = {(u, v) : (u, v) belong to
E or (v, u) belongs to E}. Edges in the network G are also edges in
G', and it is therefore a simple matter to maintain capacities and
flows in this data structure. Given a flow â on G, the edges in the
residual network Gâ consist of all edges (u, v) of G' such that c(u,
v) – â[u, v] not equal to 0. The time to find a path in a residual
network is therefore O(E') = O(E) if we use either depth-first search
or breadth-first search. Each iteration of the while loop thus takes
O(E) time, making the total running time of FORD-FULKERSON O(E | â*
|).

My questions on above text.

  1. Can any one please explain above paragraph easy to understand? I think both G and G' is same structually what differnce it makes?
  2. What does author mean by "dges in the network G are also edges in G', and it is therefore a simple matter to maintain capacities and flows in this data structure." ?
  3. How author came with The time to find a path in a residual network is therefore O(E') = O(E) if we use DFS or BFS?

Thanks for your time and help.

Best Answer

There's not a heck of a lot of context here, but let's see if I can try to help:

  1. Regarding the set E' - if (a,b) is in E, then both (a,b) and (b,a) will be in E', which is why G is not the same as G'.

  2. It means it in the sense that there are representative edges in G' for every edge in G, I assume.

  3. I think this is just a structural property based on the fact that the edges of G' are a superset of the edges of G. Without more context I'm really not sure what's going on here.

Related Question