A network is a simple directed graph such that each edge e has two intger lower and upper capacities 0≤cl(e)≤cu(e). A circular flow on this graph is a function such that:
1) For each edge e, cl(e)≤f(e)≤cu(e).
2) For each vertex v: \sum_{e\in v^\plus{}}f(e)\equal{}\sum_{e\in v^\minus{}}f(e)
a) Prove that this graph has a circular flow, if and only if for each partition X,Y of vertices of the network we have:
\sum_{\begin{array}{c}{e\equal{}xy}\\{x\in X,y\in Y}\end{array}} c_l(e)\leq \sum_{\begin{array}{c}{e\equal{}yx}\\{y\in Y,x\in X}\end{array}} c_l(e)
b) Suppose that f is a circular flow in this network. Prove that there exists a circular flow g in this network such that g(e)\equal{}\lfloor f(e)\rfloor or g(e)\equal{}\lceil f(e)\rceil for each edge e. functionfloor functionceiling functioncombinatorics proposedcombinatorics