最大流量問題

最適化理論では、最大フロー問題では、フロー ネットワークを通じて最大流量を実現する 実行可能なフローを見つけます。

最大フロー問題は、循環問題などのより複雑なネットワーク フロー問題の特殊なケースとして考えることができます。最大フロー最小カット定理で述べられているように、st フロー (つまり、ソースs からシンクtへのフロー)の最大値は、ネットワーク内のst カット(つまり、s を t から切断するカット)の最小容量に等しくなります。

最大フロー問題は、ソビエト鉄道の交通流の簡略モデルとして、 1954年にTEハリスとFSロスによって初めて定式化されました。 ^{[1] [2] [3]}

1955年、レスター・R・フォード・ジュニアとデルバート・R・ファルカーソンは、最初のアルゴリズムであるフォード・ファルカーソンアルゴリズムを作成しました。^{[4] [5]} 1955年の論文^{[4]で、フォードとファルカーソンはハリスとロスの問題は次のように定式化されると書いています（ [1]} 5ページを参照）。

複数の中間都市を経由して 2 つの都市を結ぶ鉄道網を考えます。この鉄道網の各リンクには、その容量を表す番号が割り当てられています。定常状態を前提として、ある都市から別の都市への最大の流れを見つけます。

フォードとフルカーソンは1962年に出版した著書「ネットワークにおけるフロー」[5]の中で次の^ように書いている。

この問題は、1955年春にTEハリス氏から著者らに提起された。ハリス氏は、FSロス退役将軍と共同で鉄道交通流の簡略モデルを作成し、この特定の問題がそのモデルによって示唆される中心的な問題であると指摘した[11]。

ここで[11]は、ハリスとロスによる1955年の秘密報告書「鉄道の純容量を評価する方法の基礎」^[3]を指している（^[1]の5ページを参照）。

長年にわたり、最大フロー問題に対する様々な改良された解法が発見されてきました。特に、エドモンズとカープ、およびディニッツがそれぞれ独立に発見した最短増加経路アルゴリズム、ディニッツのブロッキングフローアルゴリズム、ゴールドバーグとタージャンのプッシュ再ラベルアルゴリズム、ゴールドバーグとラオのバイナリブロッキングフローアルゴリズムが有名です。シャーマン^[6]とケルナー、リー、オレッキア、シドフォード^{[7] [8]}のアルゴリズムは、ほぼ最適な最大フローを見つけますが、無向グラフでのみ機能します。

2013年にJames B. Orlinはアルゴリズムを説明した論文を発表しました。^[9]${\displaystyle O(|V||E|)}$

2022年にLi Chen、Rasmus Kyng、Yang P. Liu、Richard Peng、Maximilian Probst Gutenberg、Sushant Sachdevaは、最大フロー問題が特殊ケースとなる最小コストフロー問題に対して、ほぼ線形時間で動作するアルゴリズムを発表しました。 ^{[10] [11]負の重みを持つ}単一ソース最短経路（SSSP）問題の場合、最小コストフロー問題の別の特殊ケースとして、ほぼ線形時間のアルゴリズムも報告されています。^{[12] [13]両方のアルゴリズムは、2022年の}コンピュータサイエンスの基礎に関するシンポジウムで最優秀論文とみなされました。^{[14] [15]}${\displaystyle O(|E|^{1+o(1)})}$

まず、いくつかの表記法を確立します。

• がそれぞれ のソースとシンクを持つネットワークであるとします。${\displaystyle N=(V,E)}$${\displaystyle s,t\in V}$${\displaystyle N}$
• が の端上の関数である場合、 上のその値は またはで表される。${\displaystyle g}$${\displaystyle N}$${\displaystyle (u,v)\in E}$${\displaystyle g_{uv}}$${\displaystyle g(u,v).}$

定義。エッジの容量とは、エッジを通過できるフローの最大量です。正式にはマップです。${\displaystyle c:E\to \mathbb {R} ^{+}.}$

定義。フローとは、次の条件を満たす マップです。${\displaystyle f:E\to \mathbb {R} }$

• 容量制約。エッジのフローはその容量を超えることはできません。言い換えれば、すべての${\displaystyle f_{uv}\leq c_{uv}}$${\displaystyle (u,v)\in E.}$
• フローの保存。ソースとシンクを除いて、ノードに入るフローの合計は、そのノードから出るフローの合計と等しくなければなりません。または:

${\displaystyle \forall v\in V\setminus \{s,t\}:\quad \sum _{u:(u,v)\in E,f_{uv}>0}f_{uv}=\sum _{u:(v,u)\in E,f_{vu}>0}f_{vu}.}$

注：流れは対称的である：すべての${\displaystyle f_{uv}=-f_{vu}}$${\displaystyle (u,v)\in E.}$

定義。フローの値は、ソースからシンクに流れる流量です。正式には、フローは次のように表されます。 ${\displaystyle f:E\to \mathbb {R} ^{+}}$

${\displaystyle |f|=\sum _{v:\ (s,v)\in E}f_{sv}=\sum _{u:\ (u,t)\in E}f_{ut}.}$

定義。最大フロー問題は、ソースからシンクにできるだけ多くのフローをルーティングすること、つまり、最大値を持つフローを見つけることです。 ${\displaystyle f_{\textrm {max}}}$

最大フローが複数存在する場合があり、任意の実数値（または任意の有理数値）のフロー（整数だけでなく）が許可される場合は、最大フローは正確に 1 つ存在するか、または無限に存在します。これは、基本最大フローの線形結合が無限に存在するためです。言い換えると、 1 つの最大フローでエッジにフローの単位を送信し、別の最大フローでエッジにフローの単位を送信すると、それぞれに対してユニットを送信し、残りのエッジにそれに応じてフローをルーティングして、別の最大フローを取得できます。フロー値が任意の実数または有理数である場合、各ペアに対してそのような値が無限に存在します。 ${\displaystyle x}$${\displaystyle u}$${\displaystyle y>x}$${\displaystyle u}$${\displaystyle \Delta \in [0,y-x]}$${\displaystyle x+\Delta }$${\displaystyle u}$${\displaystyle \Delta }$${\displaystyle x,y}$

次の表は、最大フロー問題を解決するためのアルゴリズムを示しています。ここで、およびはネットワークの頂点とエッジの数を示します。値は、すべての容量を整数値に再スケーリングした後の最大エッジ容量を指します (ネットワークに無理数の容量が含まれている場合は、無限大になる可能性があります)。 ${\displaystyle V}$${\displaystyle E}$${\displaystyle U}$${\displaystyle U}$

その他のアルゴリズムについては、Goldberg & Tarjan (1988) を参照してください。

積分フロー定理は、

フロー ネットワーク内の各エッジに整数容量がある場合、整数最大フローが存在します。

主張されているのは、フロー値が整数であるということ（これは最大フロー最小カット定理から直接導かれる）だけではなく、すべてのエッジ上のフローが整数であるということです。これは、エッジを横切るフローが、そのエッジに対応するアイテムが、求められているセットに含まれるかどうかをエンコードする可能性がある多くの組み合わせアプリケーション（以下を参照）にとって重要です。

1 つのソースと 1 つのシンクだけではなく、ソースの集合とシンクの集合を持つネットワークが与えられた場合、 を横切る最大フローを求めることになります。 の各頂点に接続する統合ソースと、 の各頂点によって接続され、各辺に無限の容量を持つ統合シンク(スーパーソースとスーパーシンクとも呼ばれる) を追加することで、マルチソースマルチシンク問題を最大フロー問題に変換できます (図 4.1.1 を参照)。 ${\displaystyle N=(V,E)}$${\displaystyle S=\{s_{1},\ldots ,s_{n}\}}$${\displaystyle T=\{t_{1},\ldots ,t_{m}\}}$${\displaystyle N}$${\displaystyle S}$${\displaystyle T}$

二部グラフ が与えられたとき、における最大濃度マッチング、つまり可能な限り最大の辺数を含むマッチングを見つけます。この問題は、ネットワーク を構築することで最大フロー問題に変換できます。ここで、 ${\displaystyle G=(X\cup Y,E)}$${\displaystyle G}$${\displaystyle N=(X\cup Y\cup \{s,t\},E')}$

1. ${\displaystyle E'}$からへ向かうのエッジが含まれます。${\displaystyle G}$${\displaystyle X}$${\displaystyle Y}$
2. ${\displaystyle (s,x)\in E'}$それぞれおよびそれぞれについて。${\displaystyle x\in X}$${\displaystyle (y,t)\in E'}$${\displaystyle y\in Y}$
3. ${\displaystyle c(e)=1}$それぞれについて（図4.3.1参照）。${\displaystyle e\in E'}$

すると、 における最大フロー値はにおける最大マッチングのサイズに等しくなり、 におけるフローを持つエッジを整数最大フローとして取得することで、最大カーディナリティ マッチングを見つけることができます。 ${\displaystyle N}$${\displaystyle G}$${\displaystyle 1}$

有向非巡回グラフ が与えられたとき、の各頂点をカバーするための頂点非結合パスの最小数を求めます。から二部グラフを構築できます。ここで ${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle G'=(V_{\textrm {out}}\cup V_{\textrm {in}},E')}$${\displaystyle G}$

1. ${\displaystyle V_{\textrm {out}}=\{v_{\textrm {out}}\mid v\in V\land v{\text{ has outgoing edge(s)}}\}}$
2. ${\displaystyle V_{\textrm {in}}=\{v_{\textrm {in}}\mid v\in V\land v{\text{ has incoming edge(s)}}\}}$
3. ${\displaystyle E'=\{(u_{\textrm {out}},v_{\textrm {in}})\in V_{out}\times V_{in}\mid (u,v)\in E\}}$。

次に、 がサイズのマッチングを持つことが、 が辺とパスを含む頂点分離パスカバーを持つことと同値であることが示されます。ここで、 は内の頂点の数です。したがって、代わりに 内の最大基数マッチングを見つけることで、問題を解決できます。 ${\displaystyle G'}$${\displaystyle M}$${\displaystyle m}$${\displaystyle G}$${\displaystyle C}$${\displaystyle m}$${\displaystyle n-m}$${\displaystyle n}$${\displaystyle G}$${\displaystyle G'}$

のマッチングを見つけ、そこからカバーを構築したと仮定します。直感的には、 で 2 つの頂点がマッチングする場合、辺はに含まれます。明らかに、 の辺の数はです。が頂点素である ことを確認するには、次のことを考慮します。${\displaystyle M}$${\displaystyle G'}$${\displaystyle C}$${\displaystyle u_{\mathrm {out} },v_{\mathrm {in} }}$${\displaystyle M}$${\displaystyle (u,v)}$${\displaystyle C}$${\displaystyle C}$${\displaystyle m}$${\displaystyle C}$

1. 内の各頂点は内で一致しない可能性があり、その場合から に至る辺は存在しません。また、から に至る辺は 1 つだけ存在します。いずれの場合でも、内のどの頂点からも 1 つ以上の辺は離れません。${\displaystyle v_{\textrm {out}}}$${\displaystyle G'}$${\displaystyle M}$${\displaystyle v}$${\displaystyle C}$${\displaystyle v}$${\displaystyle C}$${\displaystyle v}$${\displaystyle C}$
2. 同様に、の各頂点について– が一致する場合、に入る単一の辺が存在します。そうでない場合、に入る辺はありません。${\displaystyle v_{\textrm {in}}}$${\displaystyle G'}$${\displaystyle v}$${\displaystyle C}$${\displaystyle v}$${\displaystyle C}$

したがって、 には 2 つの入ってくるエッジまたは 2 つの出ていくエッジを持つ頂点はなく、 のすべてのパスは頂点が互いに素であることを意味します。 ${\displaystyle C}$${\displaystyle C}$

カバーのサイズが であることを示すために、空のカバーから始めて段階的に構築していきます。カバーに頂点を追加するには、既存のパスに追加するか、その頂点から始まる長さ 0 の新しいパスを作成します。前者は、 であり、カバー内のあるパスが で始まる場合、または であり、あるパスが で終わる場合のいずれにも当てはまります。後者は常に当てはまります。前者の場合、カバー内のエッジの総数は 1 増えますが、パスの数は変わりません。後者の場合、パスの数が増えますが、エッジの数は変わりません。これで、すべての頂点をカバーした後、カバー内のパスの数とエッジの数の合計が であることが明らかです。したがって、カバー内のエッジの数が である場合、パスの数は です。 ${\displaystyle C}$${\displaystyle n-m}$${\displaystyle u}$${\displaystyle (u,v)\in E}$${\displaystyle v}$${\displaystyle (v,u)\in E}$${\displaystyle v}$${\displaystyle n}$${\displaystyle n}$${\displaystyle m}$${\displaystyle n-m}$

ネットワークを考えてみましょう。各ノードにエッジ容量に加えて容量があると仮定します。つまり、フローが容量制約とフローの保存だけでなく、頂点容量制約も満たす ようなマッピングです。${\displaystyle N=(V,E)}$${\displaystyle c:V\to \mathbb {R} ^{+},}$${\displaystyle f}$

${\displaystyle \sum _{i\in V}f_{iv}\leq c(v)\qquad \forall v\in V\backslash \{s,t\}.}$

言い換えると、頂点を通過するフロー量は、その容量を超えることはできません。 を横切る最大フローを求めるには、 を拡張して、問題を元の意味の最大フロー問題に変換します。まず、それぞれをおよびに置き換えます。ここで、は に向かう辺で接続され、はから出る辺に接続されています。次に、とを接続する辺に容量を割り当てます(図 4.4.1 を参照)。この拡張されたネットワークでは、頂点容量制約が削除されるため、問題を元の最大フロー問題として扱うことができます。 ${\displaystyle N}$${\displaystyle N}$${\displaystyle v\in V}$${\displaystyle v_{\text{in}}}$${\displaystyle v_{\text{out}}}$${\displaystyle v_{\text{in}}}$${\displaystyle v}$${\displaystyle v_{\text{out}}}$${\displaystyle v}$${\displaystyle c(v)}$${\displaystyle v_{\text{in}}}$${\displaystyle v_{\text{out}}}$

有向グラフと 2 つの頂点が与えられた場合、からへの経路の最大数を求めます。この問題にはいくつかのバリエーションがあります。 ${\displaystyle G=(V,E)}$${\displaystyle s}$${\displaystyle t}$${\displaystyle s}$${\displaystyle t}$

1. パスは辺が互いに素でなければなりません。この問題は、と をそれぞれ のソースとシンクとしてからネットワークを構築し、各辺に の容量を割り当てることで、最大フロー問題に変換できます。このネットワークでは、辺が互いに素なパス がある場合に限り、最大フローが になります。${\displaystyle N=(V,E)}$${\displaystyle G}$${\displaystyle s}$${\displaystyle t}$${\displaystyle N}$${\displaystyle 1}$${\displaystyle k}$${\displaystyle k}$

2. パスは独立、つまり頂点が互いに素でなければなりません (と を除く)。から頂点容量を持つネットワークを構築できます。ここで、すべての頂点とすべての辺の容量は です。この場合、最大フローの値は から への独立したパスの最大数に等しくなります。 ${\displaystyle s}$${\displaystyle t}$${\displaystyle N=(V,E)}$${\displaystyle G}$${\displaystyle 1}$${\displaystyle s}$${\displaystyle t}$

3. 経路は辺が互いに素かつ頂点が互いに素であることに加えて、長さの制約も持つ。つまり、長さがちょうど、または最大で である経路のみを数える。この問題のほとんどのバリエーションは、 の値が小さい場合を除いて NP完全である。^[27]${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

有向グラフの閉包とは、 C から出る辺がない頂点の集合のことです。閉包問題とは、頂点重み付き有向グラフの最大重み閉包または最小重み閉包を見つける作業です。最大フロー問題への還元を使用して、多項式時間で解決できます。

野球の敗退問題では、リーグでnチームが競い合っています。リーグシーズンの特定の段階で、 w _iは勝利数、r _iはチームiの残り試合数、r _{ij はチーム}jとの残り試合数です。そもそもシーズンを終える見込みがない場合、チームは敗退します。野球の敗退問題のタスクは、シーズン中の各時点でどのチームが敗退するかを決定することです。Schwartz ^{[28] は、この問題を最大ネットワークフローに簡略化する手法を提案しました。この手法では、チーム}kが敗退するかどうかを決定するネットワークが作成されます。

G = ( V , E ) をネットワークとし、s 、 t ∈ Vをそれぞれソースとシンクとします。ゲーム ノード_ijを追加します。これは、これら 2 つのチーム間のプレイ回数を表します。また、各チームのチーム ノードを追加し、i < jの各ゲーム ノード{ i、j }をVに接続し、容量r _ijのエッジでsから各ノードを接続します。これは、これら 2 つのチーム間のプレイ回数を表します。また、各チームのチーム ノードを追加し、各ゲーム ノード{ i、j } を2 つのチーム ノードiとjに接続して、どちらかが勝つようにします。これらのエッジのフロー値を制限する必要はありません。最後に、チーム ノードiからシンク ノードtへのエッジが作成され、容量w _k + r _k – w _iが、チームi がw _k + r _{k を}超えて勝つことを防ぐために設定されます。Sをリーグに参加しているすべてのチームのセットとし、

${\displaystyle r(S-\{k\})=\sum _{i,j\in \{S-\{k\}\} \atop i<j}r_{ij}}$。

この方法では、サイズr ( S − { k }) のフロー値がネットワークG内に存在する場合にのみ、チームk は排除されないと主張されています。前述の記事では、このフロー値がsからtへの最大フロー値であることが証明されています。

航空業界では、フライト クルーのスケジュールが大きな問題となっています。航空会社のスケジュール問題は、拡張された最大ネットワーク フローの応用として考えることができます。この問題の入力は、各フライトの出発地と到着地と時間に関する情報を含むフライト セットFです。航空会社のスケジュールの 1 つのバージョンでは、目標は最大k 人のクルーで実行可能なスケジュールを作成することです。

この問題を解決するには、境界付き循環と呼ばれる循環問題のバリエーションを使用します。境界付き循環は、ネットワーク フローの問題を一般化し、エッジ フローの下限の制約を追加します。

G = ( V , E ) を、 s、t ∈ V をソースノードとシンクノードとするネットワークとします。すべてのフライトiのソースとデスティネーションについて、Vに 2 つのノードを追加します。フライトiのソースとしてノードs _i 、デスティネーションノードとしてノードd _iです。また、 Eに次のエッジを追加します。

1. sと各s _iの間の容量 [0, 1] のエッジ。
2. 各d _iとtの間に容量[0, 1]を持つエッジ。
3. s _iとd _iの各ペア間の容量[1, 1]のエッジ。
4. フライトiの目的地からソースs _{j が}妥当な時間とコストで到達可能な場合、各d _iとs _jの間に容量 [0, 1] を持つエッジ。
5. sとtの間に容量[0, ∞ ]を持つエッジ。

上記の方法では、 sとtの間のGのフロー値kを見つけることは、最大k人の乗組員による飛行セットFの実行可能なスケジュールを見つけることに等しいと主張され、証明されています。^[29]

航空会社のスケジュール作成の別のバージョンは、すべてのフライトを実行するために必要な最小限の乗務員を見つけることです。この問題の答えを見つけるために、各フライトのコピーがセットAとセットBにある二部グラフG' = ( A ∪ B , E )が作成されます。同じ飛行機がフライトi の後にフライトj を実行できる場合、i ∈ Aはj ∈ Bに接続されます。G'のマッチングはFのスケジュールを誘導し、明らかにこのグラフの最大二部マッチングは最小数の乗務員による航空会社のスケジュールを生成します。^[29]この記事の応用の部分で述べたように、最大​​基数二部マッチングは最大フロー問題の応用です。

商品を生産する工場と、商品を配送する村がいくつかあります。これらの村は道路網で結ばれており、各道路には通過できる最大の商品に対する容量cがあります。問題は、需要を満たす循環があるかどうかを見つけることです。この問題は、最大フロー問題に変換できます。

1. ソースノードs を追加し、そこから容量p _iを持つすべての工場ノードf _iにエッジを追加します。ここで、p _{i は}工場f _iの生産率です。
2. シンクノードt を追加し、すべての村v _iからtに容量d _iのエッジを追加します。ここで、d _{i は}村v _iの需要率です。

この新しいネットワークをG = ( V , E ) とします。次の場合にのみ需要を満たす循環が存在します。

最大流量値( G ) 。${\displaystyle =\sum _{i\in v}d_{i}}$

循環が存在する場合、最大フローソリューションを見ると、需要を満たすために特定の道路でどれだけの量の商品を送る必要があるかがわかります。

この問題は、いくつかの辺のフローに下限を追加することで拡張できる。^[30]

クラインバーグとタルドスは、その著書の中で、画像を分割するアルゴリズムを提示している。 ^[32]彼らは、画像の背景と前景を見つけるアルゴリズムを提示している。より正確には、アルゴリズムはビットマップを入力として次のようにモデル化する。a i ≥ 0 はピクセルi が前景に属する可能性、 b _{i ≥ 0}はピクセルi が背景に属する可能性、 p _{ij は}隣接する 2 つのピクセルiとj が一方が前景に、他方が背景に配置される場合のペナルティである。目標は、次の量を最大化するピクセル集合の パーティション ( A、B )を見つけることである。

${\displaystyle q(A,B)=\sum _{i\in A}a_{i}+\sum _{i\in B}b_{i}-\sum _{\begin{matrix}i,j{\text{ adjacent}}\\|A\cap \{i,j\}|=1\end{matrix}}p_{ij}}$、

実際、A（前景とみなされる）のピクセルではa _iが得られ、 B（背景とみなされる）のすべてのピクセルではb _{i が}得られる。隣接する2つのピクセルiとjの間の境界ではp _{ij が}失われる。これは、量を最小化することと同等である。

${\displaystyle q'(A,B)=\sum _{i\in A}b_{i}+\sum _{i\in B}a_{i}+\sum _{\begin{matrix}i,j{\text{ adjacent}}\\|A\cap \{i,j\}|=1\end{matrix}}p_{ij}}$

なぜなら

${\displaystyle q(A,B)=\sum _{i\in A\cup B}a_{i}+\sum _{i\in A\cup B}b_{i}-q'(A,B).}$

ここで、ピクセル、ソース、シンクをノードとするネットワークを構築します (右の図を参照)。ソースをピクセルiに重みa _iのエッジで接続します。ピクセルi をシンクに重みb _iのエッジで接続します。ピクセルiをピクセルjに重みp _ijで接続します。これで、そのネットワークの最小カット (または最大フローと同等) を計算する作業が残っています。最後の図は最小カットを示しています。

1.最小コストフロー問題では、各エッジ ( u、v)には、その容量に加えてコスト係数 a _uvもあります。エッジを通るフローがf _uvの場合、合計コストはa _uv f _uvです。指定されたサイズd のフローを最小コストで見つける必要があります。ほとんどのバリアントでは、コスト係数は正または負のいずれかになります。この問題には、さまざまな多項式時間アルゴリズムがあります。

2. 最大フロー問題は、選言的制約によって拡張することができます。選言的制約が負の場合、特定のエッジのペアは同時に非ゼロフローを持つことはできません。選言的制約が正の場合、特定のエッジのペアのうち少なくとも 1 つは非ゼロフローを持つ必要があります。 負の制約があると、単純なネットワークであっても、問題はNP 困難になります。 正の制約があると、分数フローが許される場合、問題は多項式ですが、フローが整数でなければならない場合はNP 困難になる可能性があります。^[33]

• Joseph Cheriyan およびKurt Mehlhorn ( 1999)。「プリフロープッシュ最大フローアルゴリズムにおける最高レベルの選択ルールの分析」。Information Processing Letters。69 ( 5 ): 239–242。CiteSeerX 10.1.1.42.8563。doi :10.1016/S0020-0190(99)00019-8。 
• Daniel D. SleatorおよびRobert E. Tarjan (1983)。「動的ツリーのデータ構造」(PDF)。Journal of Computer and System Sciences。26 ( 3): 362–391。doi : 10.1016 /0022-0000(83)90006-5。ISSN 0022-0000  。
• ユージン・ローラー(2001)。「4. ネットワークフロー」。組み合わせ最適化: ネットワークとマトロイド。ドーバー。pp. 109–177。ISBN 978-0-486-41453-9。