MathDB

A network is a simple directed graph such that each edge

e

has two intger lower and upper capacities

0\leq c_l(e)\leq c_u(e)

. A circular flow on this graph is a function such that: 1) For each edge

e

c_l(e)\leq f(e)\leq c_u(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

Problem Statement