1. [25 points} A ow network with demands is a directed capacitated graph with potentially multiple sources and sinks, which may have incoming and outgoing edges respectively. In particular, each node n E V has an integer demand d(n}; if d[n] > 0, v is a sink, while if d(v) R+ that satises (a) capacity constraints: for each e E E, 0 E fie) S C(e}. (b) demand mnstmints: For each n E V, fini] fout (a) = dfv). We are now concerned with a decision problem rather than a maximization one: is there a circulation f with demands that meets both capacity and demand conditions? i. Derive a necessary condition for a feasible circulation with demands to exist. ii. Reduce the problem of nding a feasible circulation with demands to Max Flow. 2. [25 points) In many applications, on top of the node demands introduced in the previous problem, the ow must also make use of certain edges. To capture such constraints, consider the following variant of the previous problem. You are given a flow network G = {V, E) with demands where every edge e has an integer capacity ca, and an integer lower lion-ad 2,, 2 0. A circulation f must now satisfy .19., <_i e for every as well the demand constraints. determine whether a feasible circulation exists. points similarly to aw network with demands we can dene flow supplies where each node it v now has an integer supply so that if> i}, u is a source and if 3,, R+ that is, a ow satisfying edge capacity constraints and node supplies that minimizes the total cost of the flow. (a) Show that max ow can be formulated as a min-cost ow problem. (1)) Formulate a linear program for the min-cost ow