Fundamental Theorem of Flow ·Flow network:D(V,E),s,t∈V,andc:E→R≥0 。Max-flow=min-cut ·With integral capacity c:E→Z≥o,the maximum flow is achieved by an integer flow f:E→Z≥o An elementary proof by augmenting path. An advanced proof by LP duality and integrality.• Flow network: , , and • Max-flow = min-cut • With integral capacity , the maximum flow is achieved by an integer flow . D(V, E) s, t ∈ V c : E → ℝ≥0 c : E → ℤ≥0 f : E → ℤ≥0 Fundamental Theorem of Flow • An elementary proof by augmenting path. • An advanced proof by LP duality and integrality