フローネットワークの基礎と用語の定義

Contents

フロー

関数 $f : V×V \rightarrow \mathbb{R}$で表現されるフローは、以下の特徴を持つ重み付き有向グラフ（フローネットワーク） $G=(V,E)$ 上で定義されます。

フローネットワーク $G=(V,E)$ が満たす条件

・始点 $s$ と終点 $t$ が存在し、始点をソース・終点をシンクなどと呼ぶ
・容量 $c(u,v)$ は非負
・逆向きの辺は含まない：$(u,v)\in E$ ならば $(v,u)\notin E$
・自己ループは無い

また、フロー $f$ は以下を満たします。

フロー $f$ が満たす条件

容量制限：全ての $u,v \in V$ について、$0 \leq f(u,v) \leq c(u,v)$
フロー保存則：全ての $u\in V \backslash \{s,t\}$ について、$\sum_{v \in V}f(u,v) = \sum_{v\in V}f(v,u)$

１つ目の容量制限は、フローが容量を超えないように流れる必要があることを表します。

２つ目のフロー保存則は、始点と終点以外では、入り込む量と出ていく量が等しいことを表しています。

特徴をまとめると、

となります。

フロー $f$ の値 $|f|$ を、始点から出るフローの合計と、始点に入り込むフローの合計の差として表すことにします。

フロー $f$ の値 $|f|$

$$ |f| = \sum_{v \in V}f(s,v) ~ – \sum_{v \in V}f(v,s) $$

※ 始点に入り込むフローを考えることは多く無いので、出るフローのみを考えれば良い場合が多いです。

先程のフローの条件（容量制限・フロー保存則）を満たすものの中で、フローの値 $|f|$ が最大となるものを、最大フロー などと言います。

フロー $f$ に対して定義される以下の値を、残余容量と言います。

残余容量 $c_f$

$$ c_f(u,v) := \left\{ \begin{array}{ll}
c(u,v) ~ – f(u,v) & ((u,v)\in E) \\
f(u,v) & ((v,u)\in E) \\
0 & (otherwise)
\end{array} \right. $$

$(u,v)\in E$ の場合を考えてみます。フローが定義されると、「あとどれくらいフローを流すことができるか」という値も $c_f(u,v) = c(u,v) ~ – f(u,v)$ で定めることができます。

さらにこれを拡張して考えると、$(v,u)\in E$ の場合、「流したフローはどれくらいで、逆向きに押し返せる最大値はいくつか」という値も $c_f(u,v) = f(u,v)$ で定めることができます。

残余容量自体を、容量として構築したネットワーク $G_f = (V, E_f)$ を、残余ネットワークと呼びます。

「あとどれくらいフローを流すことができるか」や「どのくらい逆流できるか」が分かりやすくなります。

残余ネットワーク内で、ソース $s$ からシンク $t$ へのパスのうち、パス上の任意の辺 $(u,v)$ について

$$ 0 < c_f(u,v)$$

が成り立つようなパスを、増加可能経路（増加道）などと言います。

もう少し厳密にすると、増加可能経路 $(v_1, v_2, v_3, …, v_k)$ は以下を満たします。

増加可能経路 $(v_1, v_2, v_3, …, v_k)$ が満たす条件

・　$v_1 = s$
・　$v_k = t$
・　$0 < c_f(v_i,v_{i+1})$

増加可能経路があれば、追加でフローを流すことができると分かります。