フローの合成と分解

フローの定義は頂点における保存条件が満たされるグラフの辺を入力とする関数であるのが普通ですが、他の定式化もあります。この定式化の方がより自然で有用なこともあります。

任意のグラフ \(G\) とソース頂点 \(s\) とシンク頂点 \(t\) が与えられたとして、\(G\) の適当な \((s,t)\)-フロー \(f, g\) と実数 \(\alpha, \beta\) を取り、次の関数 \(h: E \rightarrow \mathbb{R}\) を考えます: \[ h(u \rightarrow v) := \alpha \cdot f(u \rightarrow v) + \beta \cdot g(u \rightarrow v) \] ここで \(u \rightarrow v\) は任意の辺です。この定義は単純に \(h = \alpha f + \beta g\) とも書けます。定義を追っていくと、\(h\) もまた \((s,t)\)-フローでありその値は \(|h| = \alpha |f| + \beta |g|\) であることが分かります。これをより一般的に言うと、\((s,t)\)-フローの線形結合は \((s,t)\)-フローだということです。

よって任意の \((s,t)\)-フローは特殊な構造を持つフローの重み付き和として表現できます。\(s\) から \(t\) への任意の有向路 \(P\) について、対応する路フロー (path flow) を次のように定義します: \[ P(u \rightarrow v) = \begin{cases} 1 & \text{if } u \rightarrow v \in P \\ -1 & \text{if } v \rightarrow u \in P \\ 0 & \text{それ以外} \end{cases} \] 定義を追っていくと \(P: E \rightarrow \mathbb{R}\) は値が \(1\) の \((s, t)\) フローであることが簡単に示せます。ここでは路に流す一単位のフローとその路の両方を意図的に同じ記号 \(P\) で表しています。

同様に、任意の閉路 \(C\) に対応する閉路フロー (cycle flow) を次のように定義します: \[ C(u \rightarrow v) = \begin{cases} 1 & \text{if } u \rightarrow v \in C \\ -1 & \text{if } v \rightarrow u \in C \\ 0 & \text{それ以外} \end{cases} \] ここでも \(C: E \rightarrow \mathbb{R}\) が値の \(0\) の \((s, t)\) フローであることは簡単に示せます。

前述の議論から任意の路フローと閉路フローの線形結合もまたフローとなることが証明でき、この線形和をフロー分解 (flow decomposition) と呼びます。さらに、任意の非負フローには次の構造を持つフロー分解が存在します:

フロー分解定理 (Flow Decomposition Theorem) 全ての非負 \((s,t)\)-フローは有向 \((s,t)\)-路と有向閉路の正の線形和として書ける。そのとき有向辺 \(u \rightarrow v\) が分解の路または閉路に現れるのは \(f(u \rightarrow v) > 0\) のときに限られ、分解に含まれる路と閉路の数は \(f(e) > 0\) を満たす辺 \(e\) の数以下である。

証明 \(f\) に含まれるゼロでないフローを持つ辺の数に関する帰納法で示す。直観的に言うと、Ford-Fulkerson のアルゴリズムを逆回しにしたのがこの証明である。

循環を重み付き閉路に分解する
図 10.9. 循環を重み付き閉路に分解する

\(f\) において少なくとも一つの辺が正のフローを持っているならば、その辺を通る \((s,t)\)-路あるいは負閉路が存在する。よってその路または閉路を \(f\) から引けるだけ引くことで少なくとも一つの辺を \(f\) から消すことができる。こうするとゼロでないフローを持つ辺の数が減るので、あとは再帰の妖精が残りの分解をしてくれる。

この議論をきちんと行うために、 \(f\) が循環 (circulation) である特殊ケースを考える。フローが循環であるとは、値が \(0\) で \(s,t\) を含む全ての頂点において保存条件が成り立つことを言う。任意のフローネットワークとそれに含まれる循環 \(f\) を固定し、\(f(u \rightarrow v) > 0\) を満たす辺 \(u \rightarrow v\) の数を \(\#f\) とする。\(f\) が最大でも \(\max \lbrace 0, \# f - 1 \rbrace\) 個の閉路の正の線形結合に分解できることを、これから \(\# f\) に関する帰納法で示す。考えるべきケースは三つある:

  • \(\# f = 0\) の場合、\(f\) はゼロ個の閉路の線形結合である。

  • \(f (u \rightarrow v) > 0\) である辺 \(u \rightarrow v\) 全体が有向閉路を作る場合、\(f\) は一つの閉路の線形結合として表せる。

  • そうでない場合、\(f(u \rightarrow v) > 0\) である辺 \(u \rightarrow v\) について、任意の歩道 \(u = v_{0} \rightarrow\) \(v = v_{1} \rightarrow\) \(v_{2} \rightarrow \cdots \) であって全ての添え字 \(i\) について \(f(v_{i-1} \rightarrow v_{i} ) > 0\) であるものを考える。フローの保存条件から全ての頂点に出るフローと入るフローがあるので、この歩道は任意に長くできる。そうした場合二回以上訪れる頂点が存在するので、そのような頂点で一番添え字が若いものを \(v_{j} = v_{k}\) \((j < k)\) とする。このとき \(v_{j} \rightarrow v_{j-1} \rightarrow \cdots \rightarrow v_{k}\) は単純閉路 \(C\) となる。

    \(\displaystyle F := \min_{e \in C} f(e)\) とし、新しい関数 \(f^{\prime}\) を \(f^{\prime} := f - F \cdot C\)、省略せずに書くと \[ f^{\prime}(u \rightarrow v) := \begin{cases} f(u \rightarrow v) - F & \text{if } u \rightarrow v \in C \\ f(u \rightarrow v) & \text{それ以外} \end{cases} \] と定義する。定義を追っていくと \(f^{\prime}\) は値が \(0\) で実現可能な \(G\) の循環であることが分かる。\(F\) の定義よりある \(e \in C\) において \(f(e) = F\) となるので、その \(e\) に対して \(f^{\prime}(e) = 0\) であり、したがって \(\# f^{\prime} \leq \# f - 1\) である。\(f^{\prime}\) は \(f\) より少ない辺しか持たないことから、帰納法の仮定より \(f^{\prime}\) には \(\# f^{\prime} - 1 \leq \# f - 2\) 個以下の閉路を使った分解が存在する。よってこの分解に \(C\) に沿って \(F\) だけフローを流したフローを追加すれば、\(\# f - 1\) 個の路または閉路を使った \(f\) の分解が手に入る。このことを簡潔に書けば \(f = f^{\prime} + F \cdot C\) である。

以上より \(f\) が最大でも \(\max \lbrace 0, \# f - 1 \rbrace\) 個の閉路の正の線形結合に分解できることが示せた。

\(f\) を任意のフローネットワークに対する \(|f| > 0\) を満たす任意の \((s,t)\)-フローとする。ネットワークに \(t \rightarrow s\) という辺を追加し、新しい循環 \(f^{\prime}\) を \(f^{\prime} (t \rightarrow s) = |f|\) およびそれ以外の辺に対しては \(f^{\prime} (u \rightarrow v) = f(u \rightarrow v)\) として定義する。ここで \(\# f^{\prime} = \# f + 1 \geq 2\) である。前述の議論より \(f^{\prime}\) は最大でも \(\#f^{\prime} - 1\) 個の有向閉路の正の線形結合に分解できる。この分解から辺 \(t \rightarrow s\) を取り除いたときに得られるのはフロー \(f\) に対する分解であり、最大でも \(\# f^{\prime} - 1 \leq \# f\) 個の \((s,t)\)-路および閉路しか持たない。具体的には、\(f^{\prime}\) における \(s \rightarrow t\) を含む閉路は \(f\) における \((s,t)\)-路となり、\(f^{\prime}\) における \(s \rightarrow t\) 閉路を含まない閉路は \(f\) においても閉路のままとなる。 \(\Box\)

フロー分解定理の証明から、次の特殊な場合に対する強い結果が得られます:

さらに、任意のフローから閉路を削除すると同じ値を持つ非巡回フローが手に入ることも分かります。つまり全てのフローネットワークには最大非巡回 \((s,t)\)-フローが存在します。

この証明は \((s,t)\)-フローを路と閉路に分解するアルゴリズムとしても読むことができます。つまり \((s,t)\)-路または有向閉路を現在のフローから見つけてそれをできる限り取り除くという処理をフローが空になるまで繰り返すアルゴリズムであり、 Ford-Fulkerson のアルゴリズムに似ています。次のようにすれば路フローまたは閉路フローを \(O(V)\) 時間で見つけられます:

両方の場合においてアルゴリズムがスタックしないことは保存条件から分かります。各反復は \(O(V)\) 時間で行うことができ、フローを引くという処理で少なくとも一つの辺がフローから消えるので、フロー分解アルゴリズム全体の実行時間は \(\pmb{O(VE)}\) です。

フロー分解定理を使うと、路または閉路を一つずつ作る処理を反復する任意の最大フローアルゴリズムの実行時間の下界が分かります。全てのフローは最大でも \(E\) 個の路と閉路に分解でき、それぞれの路と閉路は最大でも \(V\) 個の辺を持つことから、フロー分解全体の複雑性は \(O(VE)\) です。さらに任意のフロー分解が \(\Theta(VE)\) の複雑性を持つフローは簡単に構築できるので、各反復ごとに一つの路または閉路を実際に構築する最大フローアルゴリズム ――具体的には、Ford と Fulkerson の増加路アルゴリズムの全ての実装―― は最悪ケースにおける実行時間が \(\Theta(VE)\) となります。