User:Hjhfk

$\mathrm{\Sigma }$ File:Aa4567890.png

The maximum flow problem can be described as the following linear program.

$\begin{array}{ll}\text{maximize}& {\sum }_{v:(s,v)\in E}{f}_{sv}\\ \begin{array}{l}\text{subject to}\\ \\ \\ \\ \end{array}& \begin{array}{llll}{f}_{uv}& \le c_{uv}& & \mathrm{\forall }(u,v)\in E\\ {\sum }_{u:(u,v)\in E}{f}_{uv}-{\sum }_{w:(v,w)\in E}{f}_{vw}& =0& & \mathrm{\forall }v\in V\setminus \{s,t\}\\ f_{uv}& \ge 0& & \mathrm{\forall }(u,v)\in E\end{array}\end{array}$