We are given a directed graph G = (V, E), with two special vertices s and t, and non-negative integral capacities c(e) on edges e E.

undefined

a. Assume that s has no incoming edges and t has no outgoing edges. Show an efficient algorithm that finds a maximum s-t flow f in G, such that f is integral and acyclic (a flow f is acyclic, if G contains no cycle C, such that every edge of C carries positive flow (note that C may contain just two edges); it is integral iff f(e) is an integer for all e E). Analyze the algorithm's running time; there is no need to prove its correctness. a. Assume that s has no incoming edges and t has no outgoing edges. Show an efficient algorithm that finds a maximum s-t flow f in G, such that f is integral and acyclic (a flow f is acyclic, if G contains no cycle C, such that every edge of C carries positive flow (note that C may contain just two edges); it is integral iff f(e) is an integer for all e E). Analyze the algorithm's running time; there is no need to prove its correctness