定義

辺に正の重みが付いた有向グラフ $G = (V,A)$ を考える． 頂点数 $n\coloneqq |V|$ ，辺数 $m\coloneqq |A|$，辺 $e\in A$ の重みを $w_e$ と書く． この勉強会では辺重みの整数性を仮定する（すなわち $w_e\in \mathbb{Z}_{\gt 0}$ が成立）． このグラフの頂点 $s,t\in V$ に対して s-t フロー と s-t カットを以下で定義する．

s-t フロー

辺の流量ベクトル $\bm{f}=(f_{e_1},f_{e_2},\dots,f_{e_m})$ であって以下を満たすものを s-t フローと呼ぶ

• $0\leq f_e \leq w_e$
• 任意の頂点 $v\in V \setminus \{s,t\}$ に対して $\sum_{uv\in A}f_{uv} = \sum_{vw\in A}f_{vw}$ （ $v$ に入る水量と出る水量が等しい）

直感的には $s$ から $t$ に水を流す方法． ただし辺 $e$ は高々 $w_e$ しか水を流せない（辺の容量）．

$s$ を source（源泉） $t$ を sink （水の溜まる低地）と呼ぶ．

s-t フローの流量

フロー $\bm{f}$ の流量を $\sum_{sv\in A}f_{sv} - \sum_{vs\in A} f_{vs} = \sum_{vt\in A}f_{vt} - \sum_{tv\in A} f_{tv}$ で定義する．

実際には $s$ に入る辺や $t$ から出る辺は無いことが多く $\sum_{sv\in A}f_{sv} = \sum_{vt\in A}f_{vt}$ と考えて良い．

直感的には流れる水の量．

与えられたグラフに対して流量最大のフローを求める問題を最大流問題と呼ぶ．

青文字が流量11のフロー

E - 最大流

s-t カット

頂点集合の組み $(S,T)$ であって以下を満たすものを s-t カット と呼ぶ

• $S=V\setminus T$
• $s\in S, t\in T$