MAX-FLOW

Question 1

How a flow function is proved to be legal?

Answer 1

Question 2

State Max-Flow problem as a linear programming problem

Answer 2

Question 3

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?

Answer 3

Question 4

Which edges of G are found in the residual graph of G?

Answer 4

• 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.*

Question 5

Answer 5

• 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.*

Question 6

What is the residual capacity of p?

Answer 6

It is the maximum amount by which we can increase the flow on each edge in the augmenting path p.

Question 7

What is it?

Answer 7

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.

Question 8

f is a flowm the net flow f(S,T) across the cut (S,T) is defined to be:

Answer 8

Question 9

What is the capacity of a cut (S,T)?

Answer 9

Question 10

What is the definition of a minimum-cut?

Answer 10

A minimum-cut of a network is a cut whose capacity is minimum over all cuts of the network.

Question 11

Question 12

Answer 12

Question 13

Prove 1->2

Answer 13

Question 14

Prove 2 to 3

Answer 14

Question 15

Prove 3 to 1

Answer 15

Question 16

For an arbitrarily chosen augmenting paths, does FF always eventually terminates?

Answer 16

• 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|)*

Question 17

Answer 17

Question 18

• 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?*

Answer 18

• 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.*

Question 19

• Note:*
• Since capacities are non-negative, an augmenting path is definitely a simple path. why? because we push the stream “forwards” and not “backwards”.*

Question 20

Answer 20

Question 21

Reread the answer because you didn’t understand it at the first time.

Answer 21

Question 22

Answer 22

Question 23

Answer 23

Question 24

Answer 24

Question 25

*Prove*

Answer 25

Question 26

*What is its dual?*

Answer 26

Question 27

Answer 27