1
$\begingroup$

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

$\endgroup$

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.