MAX-FLOW Flashcards
How a flow function is proved to be legal?
State Max-Flow problem as a linear programming problem
We can use Max-Flow problem to determine whether there are at least two totally distinct ways to get from source point to a target point. How?
Which edges of G are found in the residual graph of G?
- Only the edges that can admit more flow, forward and backward.*
- if c(u,v)-f(u,v)>0 then (u,v) appears.*
- if f(u,v)>0 then (v,u) appears.*
- Page 718 in the book.*
- The proof is based on the fact that when we look at a specific vertex u,V1 ={v |(u,v)} andV2 = {v |(v,u)} , because we disallow antiparallalism, V1 and V2 don’t share vertices.*
What is the residual capacity of p?
It is the maximum amount by which we can increase the flow on each edge in the augmenting path p.
What is it?
It is the flow on each edge on the path p in the augmenting path. Note: every edge which is not contained in p has a flow of 0.
f is a flowm the net flow f(S,T) across the cut (S,T) is defined to be:
What is the capacity of a cut (S,T)?
What is the definition of a minimum-cut?
A minimum-cut of a network is a cut whose capacity is minimum over all cuts of the network.
Prove 1->2
Prove 2 to 3
Prove 3 to 1
For an arbitrarily chosen augmenting paths, does FF always eventually terminates?
- No.*
- The FF method might fail to terminate only if edge capacities are irrational numbers.*
- If the capacities are rational numbers, we can apply an appropriate scaling transformation to make them all intergral.*
- Since with integral, |f| must be increased with at least 1, finding an augmenting path will occur at most |f| times, and since searching a path costs O(|V|+|E’|)=O(|E|) - using BFS, we have a run-time of O(|E|*|f|)*
- There’s a repeating question about having new limits; limit on the vertrics/multiple sources which produces exactly pi units of flow and such.*
- What is the solution for this cases?*
- The solution is simple to create a new edge which resembles the new limit/condition. This edge’s capacity is the limit and we force the current to move throw it, thus enforcing the condition.*
- If we wish for an exact condition - we can further check whether the maximal current equals the capacity given by the new condition. If so, this condition can be maintained.*
- Note:*
- Since capacities are non-negative, an augmenting path is definitely a simple path. why? because we push the stream “forwards” and not “backwards”.*
Reread the answer because you didn’t understand it at the first time.
Prove
What is its dual?
