A flow f is acyclic if there are no directed cycles in the subgraph of edges with positive flow. (a) Prove that every flow f has at least one corresponding acyclic flow that has the same value. (In other words, for every graph, at least one maximum flow is acyclic.) (b) A path flow is a flow that gives positive values to a simple, directed path from source to sink. Prove that every acyclic flow is a finite combination of path flows. (c) Some flows for a directed graph are not a combination of path flows. Give an example of one.

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.