有向グラフ・ネットワーク・フロー

有向グラフ $D=(V,E)$ は、有限集合 $V$ と、相異なる頂点の順序対 $(u,v)$（$u$ から $v$ への有向辺）の集合 $E$ からなる。$(u,v)$ と $(v,u)$ が両方あってもよい。ネットワークとは、有向グラフ $D$、容量 $c:E\to\mathbb{R}_{\ge0}$、相異なる 2 頂点 $s$（入口）、$t$（出口）の組である。

関数 $f:E\to\mathbb{R}$ と頂点集合 $S\subseteq V$ に対し

と書く（$S$ から出る量、$S$ に入る量）。$f^\pm(v)=f^\pm(\{v\})$ とする。$f$ がフローであるとは、

• 容量制約: すべての $e\in E$ で $0\le f(e)\le c(e)$、
• 保存則: $s,t$ 以外のすべての頂点 $v$ で $f^+(v)=f^-(v)$

を満たすことをいう。$|f|=f^+(s)-f^-(s)$ をフローの流量という。流量が最大のフローを最大フローという。