Let $G=(V,E,w)$ is a weighted graph where each edge $e$ has a non-negative weight $w_e$. We also have a distinguished source vertex $s$ and a sink vertex $t$. The maximum flow problem requires us to find a flow $f$ that routes as much flow as possible from source vertex $s$ to sink vertex $t$ while sending at most $w_𝑒$ units of flow over each edge $e$. In this thesis (page no 17), it is stated that maximum flow problem is equivalent to the following min-max problem

$\min_{B^Tf=\chi}\max_e \frac{\lvert f_e\rvert}{w_e}$

Here $B$ is the usual edge-vertex incidence matrix and $\chi=1_s-1_t$. Then $B^Tf=\chi$ is the flow conservation property. I fail to understand this. Can someone please explain this? Thanks


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.