True or false give justifiaction 1)in the graph and f is the maximum flow in the

1) True 2) True 3) False. May not be possible in some cases 4) True.

ID: 3535651 • Letter: T

Question

True or false give justifiaction

1)in the graph and f is the maximum flow in the graph and capacities are real.

2) If all edge capacities in a graph are integer multiples of 5 then the maximum flow

value is a multiple of 5.

3) For any graph with edge capacities and vertices s and t, there always exists an edge

such that increasing the capacity on that edge will increase the maximum flow from s

to t in G. (Assume that there is at least one path in the graph from s to t.)

4) Let G be a flow diagram (a directed graph with edge capacities) and let k be a

positive number. Then there is a flow through G of size k if and only if the edges out

of the start node have capacities adding to at least k and the edges into the finish node

have capacities adding to at least k.

1) True

2) True

3) False. May not be possible in some cases

4) True.

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.