フローネットワーク
有限な有向グラフ G ( V , E ) {\displaystyle \ G(V,E)} の各枝 ( u , v ) ∈ E {\displaystyle \ (u,v)\in E} に非負実数の容量 c ( u , v ) {\displaystyle \ c(u,v)} が設定されているとする。 ( u , v ) ∉ E {\displaystyle \ (u,v)\not \in E} の場合、 c ( u , v ) = 0 {\displaystyle \ c(u,v)=0} と見なす。ここで、2つの頂点、始点 s {\displaystyle \ s} と終点 t {\displaystyle \ t} を区別する。フローネットワークは実数関数 f : V × V → R {\displaystyle \ f:V\times V\rightarrow \mathbb {R} } で表され、全ノード u {\displaystyle \ u} と v {\displaystyle \ v} について、次が成り立つ。
ここで、 f ( u , v ) {\displaystyle \ f(u,v)} は u {\displaystyle \ u} から v {\displaystyle \ v} へのフローの総和を意味する。
本来のネットワークには u {\displaystyle \ u} から v {\displaystyle \ v} への枝がない場合でも、残余ネットワークでは u {\displaystyle \ u} から v {\displaystyle \ v} への枝がある場合もある。反対向きのフローは相殺されるため、 v {\displaystyle \ v} から u {\displaystyle \ u} へのフローが減少するということは、 u {\displaystyle \ u} から v {\displaystyle \ v} へのフローが増加することを意味する。増加道(augmenting path)とは、残余ネットワーク内の経路 ( u 1 , u 2 , ... , u k ) {\displaystyle \ (u_{1},u_{2},\dots ,u_{k})} であって、 u 1 = s {\displaystyle \ u_{1}=s} かつ u k = t {\displaystyle \ u_{k}=t} であり、 c f ( u i , u i + 1 ) > 0 {\displaystyle \ c_{f}(u_{i},u_{i+1})>0} であるような経路を意味する。最大フローのネットワークとは、残余ネットワークに増加道が存在しない場合を指す。