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 ATEX to draw the graph.) Consider the following graph G, (the numbers are the capacities of the edges): 2 (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. 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 ATEX to draw the graph.) Consider the following graph G, (the numbers are the capacities of the edges): 2 (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