2022-126

Consider the statements below about network flows, where s is the source and t the sink:

I) The maximal flow in the following network is 10:

II) Given the following graph with flow/capacity for each link:

 

The residual graph associated to the above solution is the following:  

III) The push-relabeled based algorithms are the ones which involves computing a residual network and looking for augmenting paths.

 

IV) The sum of the incoming flow of a vertex u has to be equal to the sum of the outgoing flow of u, except in the source and sink nodes 

Mark the alternative that list exactly the true statements:

a) only I and IV 

b) only I, II, and IV

c) only II and III

d) only III and IV

e) None of the above 

Original idea by: Levy Chaves