Question 2. (20 marks) Let (G, s,1,c) be a flow network. We say that an edge e of G is a bottleneck edge if by increasing the capacity of e and only of e, we increase the maximum flow of the flow network. More precisely, e is a bottleneck edge of (G, s, t,c), if there is a capacity function d for the edges of G such that de) > cle) and de') = cle') for every edge e' of G other than e, and the value of a maximum flow of (G, s, t, d) is strictly) greater than the value of a maximum flow of (G, s, t,c). Consider the following flow network. 2 a 4 3 1 1 4 2 a. C. Show a maximum flow and a minimum cut of this flow network. Do not show how you obtained your answer, but explain why your answer must be correct using a theorem we proved in class. b. Show the residual graph of this flow network with respect to the maximum flow you found in part (a). Give the set of bottleneck edges of this flow network. d. Show the simplest flow network you can think of that has no bottleneck edges. e. Give an efficient algorithm that takes as input a flow network (G, s,t,c), where all the edge capacities are integers, and produces as output the set of bottleneck edges of (G,5,1,c). Explain why your algorithm is correct, and analyse its running time. (Hint: Find a maximum flow f of (G, s, t,c), and use the corresponding residual graph Gf.)