In this problem, we are going to explore the equivalence of max-flow and min-cut in a directed graph. In the graph shown in Figure 1, let node s be the source node and node t be the target node. The number on each edge denote the flow rate (capacity) from one node to the other. For example, no more than 17 units could be flowed from node s to node a and no more than 6 units could be flowed from node d to node c. (a) The maximum flow is defined as the largest possible flow rate from source node to sink node. The maximum flow value is 20. Find the maximum flow by trial and error; draw a graph to show this flow. (b) Assume that we divide the nodes {s, a, b, c, d, t} into two sets S and T, s.t. SnT = 0 and SUT = {s, a, b, c, d, t}, and we require the source node s ES and the target node t E T. The min-cut is defined as the division of (S, T) which minimizes the flow from S and T for all the possible division (S, T). Find the min-cut by trial and error, write out S and T and report the cut value. (c) How do you know this flow and cut are optimal? S 17 10 a b 6 12 15 6 Figure 1: Directed Graph 25 2 t