Max-Flow

Question 1

What is runtime of checking if flow f is max-flow

Answer 1

O(n+m)

Constructing residual graph is linear, and DFS to find new Path(s,t) is linear. No path means max flow, if not we repeat.

Question 2

Definition of Max-flow Min-cut Theorem

Answer 2

For any flow network, the size of the max flow is equal to the minimum capacity of an st-cut

Question 3

Define capacity in max-flow

Answer 3

Sum of all edges that crosses the cut from vertex set L to R

Question 4

Definition of “size” of a flow

Answer 4

Total amount of flow that can move from source to sink in a network.

Question 5

Define “bottleneck edge”

Answer 5

Any edge that crosses vertex set reachable by s, and those reachable by t.

Question 6

Why is bottleneck edge not a cut?

Answer 6

Cuts (used in MST) has to divide a graph into 2 vertex sets.

Bottleneck edges doesn’t have to (can be 2 subsets of a graph)

Question 7

Difference between bottleneck and critical edges

Answer 7

All bottleneck edges are critical edges
There exists critical edges that are not bottleneck edges.

Question 8

Let {G=(V,E), s, t in V, c(e) for e in E} be a network. For a given valid flow f, you are told that the edge e=(uv) satisfies f(e)=c(e) (this is, the edge e is saturated).

Please select all statements that are always true.

1) The reversed edge (vu) is in the residual network .

2) The size of the flow f is at least c(e).

3) All paths from the source s to the sink t must traverse the edge e.

4) There exists a path from s to t with capacity equal to c(e).

Answer 8

1) True

2) True

3) False. There can be other valid augment paths

4) False.

Question 9

Let {G=(V,E), s, t in V, c(e) for e in E} be a network and let f be a valid flow of maximum size. Consider a new network which is identical to the given one except that the capacities of all edges increase by one. This is, the new capacities are c_new(e) = c(e) + 1

Which of the following is true

1) The flow f is a valid flow of maximum size in the new network.

2) The size of the max flow in the new network has size at least size(f)+1.

3) The size of the max flow increase only if there is a path of saturated edges from s to t.

4) The size of the max flow in the new network is exactly equal to size(f)+1.

Answer 9

2

1) False. Doesn’t have to be true.

2) True. It’d at least be more than size(f)

3) False. Don’t need all edges to be saturated, just one.

4) False. All edges increase by +1, so max flow could be cumulative…