For problems that require you to provide an algorithm, you must give the

following:

1. a precise description of the algorithm in English and, if helpful, pseudocode,

2. a proof of correctness,

3. an analysis of running time and space.

4. (For this problem, if the answer contains a graph, you should include a picture in your pdf or you can use the tikz package for TEX to draw the graph.) Consider the following graph G, (the numbers are the capacities of the edges) 4 (a) Find the maximum flow from s to t and a minimum s-t cut in G. What is the flow on every edge in the maximum flow s-t? (b) Draw the residual graph Gf (along with its edge capacities)- In this residual graph, mark the following vertices: i. the vertices reachable from s ii. the vertices from which t is reachable (c) An edge is called a bottleneck edge if increasing its capacity results in an increase in the maximum flow. List all the bottleneck edges in G. (d) Give a small example of a graph which has at most 4 vertices and no bottleneck edges (e) Provide an efficient algorithm to identify all bottleneck edges on a directed graph with integer edge capacities