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

グラフフロー, フローネットワーク, 用語・定義

フロー

フローとフローネットワーク

関数 \(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)\)

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

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

フローネットワーク \(G\)
フロー:\(G\) に対して定義され、容量制限とフロー保存則を満たす

特徴をまとめると、

  • 各辺のフローは容量を超えない
  • (ソースとシンクを除く)各頂点へ入るフローの値と、出ていくフローの値は同じ
  • ソース(入口) から出るフローの値と、シンク(出口)に入るフローの値は同じ

となります。

フローの値(流量)

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

フロー \(f\) の値 \(|f|\)

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

\(|f| = 10\) のフロー

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

最大フロー

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

最大フロー(\(|f|=15\))

残余ネットワークと増加可能経路

残余容量

フロー \(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)\) を、残余ネットワークと呼びます。

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

フロー \(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})\)

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

フロー \(f\)
残余ネットワーク(水色:2だけフローを増やせる増加可能経路)