2. (10 marks) Suppose you're looking at a flow network G with source s and sink t, and you want to express the intuition that some nodes are clearly on the "source side" of the main bottlenecks; some nodes are clearly on the "sink side" of the main bottlenecks; and some nodes are in the middle. However, G can have many minimum cuts, so we have to be careful in how we make this idea precise. . We say a node v is upstream if, for all minimum s, t-cuts (A, B), we have v E A-that is, v lies on the source side of every minimum cut. . We say a node v is downstream if, for all minimum s, t-cuts (A, B), we have v E B-that is, v lies on the sink side of every minimum cut. . We say a node is central if it is neither upstream nor downstream; i.e., there is at least one minimum s, t-cut (A, B) for which v E A, and at least one minimum cut (A, B*) for which U E B*. Give an algorithm that takes a flow network G and classifies each of its nodes as either upstream, downstream, or central. The running time of your algorithm should be within a constant factor of the time required to compute a single maximum flow. You should carefully explain why your algorithm works 2. (10 marks) Suppose you're looking at a flow network G with source s and sink t, and you want to express the intuition that some nodes are clearly on the "source side" of the main bottlenecks; some nodes are clearly on the "sink side" of the main bottlenecks; and some nodes are in the middle. However, G can have many minimum cuts, so we have to be careful in how we make this idea precise. . We say a node v is upstream if, for all minimum s, t-cuts (A, B), we have v E A-that is, v lies on the source side of every minimum cut. . We say a node v is downstream if, for all minimum s, t-cuts (A, B), we have v E B-that is, v lies on the sink side of every minimum cut. . We say a node is central if it is neither upstream nor downstream; i.e., there is at least one minimum s, t-cut (A, B) for which v E A, and at least one minimum cut (A, B*) for which U E B*. Give an algorithm that takes a flow network G and classifies each of its nodes as either upstream, downstream, or central. The running time of your algorithm should be within a constant factor of the time required to compute a single maximum flow. You should carefully explain why your algorithm works