-2
$\begingroup$

I provided my answers in the "answer your own question" bit.

I have applied the same logic for my answers to a&b and c&c which seem to be essentially the same questions. Am I right though?


a) Suppose f is a flow of value 50 from s to t in a flow network G. The capacity of the minimum s-t cut in G is equal to 50.

b) Suppose f is a flow of value 100 from s to t in a flow network G. The capacity of the minimum s-t cut in G is equal to 100.


c) Suppose f is a flow of value 20 from s to t in a flow network G and there is an s-t cut of capacity 20. Then there are no s --> t paths in the residual graph Gf.

d)Suppose f is a flow of value 100 from s to t in a flow network G and there is an s-t cut of capacity 100. Then there are no s --> t paths in the residual graph Gf.


e) Given a flow network where all the edge capacities are even integers, the Ford-Fulkerson algorithm will require at most C/2 iterations, where C is the total capacity leaving the source s.

f) Let G be a directed graph with n nodes and edge weights that might be negative, but no negative cycles. The shortest path from node s to node t has at most n-1 edges.

I think this is true. I know that there is no negative cycle, so the shortest path will not have any loop. But I'm not really sure how I know this...like how did we logic that out

g) P!=NP True. This is just a fact. But worth noting it has neither been proved nor disproved?

$\endgroup$
  • $\begingroup$ Your question is too broad, and still "check my answer". Your last question is about open problem, so off-topic here. (It also takes one answer for granted, but it was not proved, so the game is still on). $\endgroup$ – Evil Dec 14 '18 at 11:42
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it is a request for assignment grading. $\endgroup$ – David Richerby Dec 14 '18 at 14:40
0
$\begingroup$

Condensed A/B and C/D into two general t/f statments with explanations:

A/ B Suppose f is a flow of some value X from s to t in a flow network G. The capacity of the minimum s-t cut in G is equal to X.

This is FALSE. HOWEVER, if the flow were maximum, then the amount of max-flow is equal to size of min-cut making it TRUE

C/D Suppose f is a flow of some value X from s to t in a flow network G and there is an s-t cut of capacity X. Then there are no s --> t paths in the residual graph Gf.

TRUE. Once the max-flow is computed then there is not path from s to t in the residual graph.

e) Given a flow network where all the edge capacities are even integers, the Ford-Fulkerson algorithm will require at most C/2 iterations, where C is the total capacity leaving the source s.

TRUE because FF algorithm estimates every possible path from s to t and since every path from s to t will have minimum capacity of 2, FF will take half amount of iteration i.e. C/2 iteration to compute result.

f) Let G be a directed graph with n nodes and edge weights that might be negative, but no negative cycles. The shortest path from node s to node t has at most n-1 edges.

TRUE

g) P!=NP

TRUE(?)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.