最大流量問題

Computational problem in graph theory

問題に対するフローネットワーク：各人間（r i）は、猫（w i 1）と犬（w i 2）のどちらか、あるいは両方を飼うことを希望している。しかし、各ペット（p i）は、人間の一部のみを好みます。ペットと人間のマッチングにおいて、最も多くのペットが、そのペットが好む人間のうちの一人に飼われるようにするマッチングを見つけなさい。

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

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

歴史

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

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

複数の中間都市を経由して2つの都市を結ぶ鉄道網を考えてみましょう。各リンクには、その輸送能力を表す番号が割り当てられています。定常状態を仮定し、ある都市から別の都市への最大流量を求めてください。

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

この問題は1955年春にT.E.ハリス氏から著者らに提起された。ハリス氏はF.S.ロス退役将軍と共同で鉄道交通流の簡略化モデルを作成し、この特定の問題がそのモデルによって示唆された中心的な問題であると指摘した[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)})}$

意味

ソースsとシンクtを持つフローネットワーク。エッジの横にある数字は容量です。

まず、いくつかの表記法を定めます。

• をフロー ネットワークとし、をそれぞれソースとシンクとします。 ${\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}$

方法	年	複雑	説明
エドモンズ・カープアルゴリズム[16]	1969	${\displaystyle O(VE^{2})}$	フォード・フルカーソンの特殊化。幅優先探索で増加パスを見つけます。
ディニックのアルゴリズム[17]	1970	${\displaystyle O(V^{2}E)}$（任意の重み）（単位重み） ${\displaystyle O(\min\{V^{2/3},E^{1/2}\}E)}$	幅優先探索を用いて、最短経路に属する残余グラフエッジの「階層化」サブグラフを構築し、各フェーズごとにブロッキングフロー（この階層化グラフにおける最大フロー）を見つける繰り返しフェーズ。最短経路の長さはフェーズごとに増加するため、フェーズは最大で 個存在する。 ${\displaystyle O(VE)}$ ${\displaystyle V-1}$
カルザノフのアルゴリズム[18]	1974	${\displaystyle O(V^{3})}$	プッシュ・リラベルアルゴリズムの前身であり、プレフロー（頂点における過剰を許容するフロー関数）を用いて、Dinicアルゴリズムの各フェーズにおけるブロッキングフローをフェーズごとの時間で検出する。初の3次時間フローアルゴリズム。 ${\displaystyle O(V^{2})}$
チェルカスキーのアルゴリズム[19]	1977	${\displaystyle O{\bigl (}V^{2}{\sqrt {E}}{\bigr )}}$	Dinic法（連続するBFS層のブロック内）とKarzanov法（ブロック結合）のブロッキングフロー法を組み合わせたもの。疎グラフに対する初のサブキュービック強多項式時間上界。KRT 1988まで、いくつかの値に対して最良の結果を維持していた。 ${\displaystyle E}$
マルホトラ、クマール、マヘシュワリ[20]	1978	${\displaystyle O(V^{3})}$	Karzanov 法に比べて複雑さが改善されたわけではなく、簡素化された手法です。階層化グラフの「参照ノード」と、そのノードの入側または出側のエッジをすべて飽和させるフローを繰り返し探索することで、ブロッキングフローを検出します。この探索時間は、ノード数と飽和エッジ数の合計に比例します。
ガリルのアルゴリズム[21]	1978	${\displaystyle O(V^{5/3}E^{2/3})}$	連続するレイヤーのブロック内の流れを見つける方法を置き換えることで、Cherkasky のアルゴリズムを変更します。
ガリル、ナアマド、シロアチ[22] [23]	1978	${\displaystyle O{\bigl (}VE(\log V)^{2}{\bigr )}}$	階層化グラフの幅優先探索フォレストにおける木縮約を用いて、ブロッキングフローを高速化します。これは多くのアルゴリズムの最初のものであり、強多項式アルゴリズムにおける最良の多項式指数として現在でも知られています。 ${\displaystyle O(VE\operatorname {polylog} V)}$
リンク/カットツリーによるフローのブロック[24 ]	1981	${\displaystyle O(VE\log V)}$	リンク/カット ツリーデータ構造を導入し、それを使用して、パスあたりの対数償却時間で階層化ネットワーク内の増加パスを見つけます。
リンク/カットツリーを用いたプッシュ・リラベルアルゴリズム[25]	1986	${\displaystyle O\left(VE\log {\frac {V^{2}}{E}}\right)}$	プッシュ・リラベル・アルゴリズムは、プリフローと、シンクまでの残余距離を推定する高さ関数を維持します。このアルゴリズムは、余分なエッジをより低い高さの頂点にプッシュすることでプリフローを修正し、残余エッジのない頂点の高さ関数をより低い高さに増加させます。この処理は、余分なエッジがすべてソースに戻るまで続きます。リンク/カットツリーでは、エッジを1つずつプッシュするのではなく、パスに沿ってプッシュできます。
チェリヤンとハゲルップ[26]	1989	ランダム化、高確率 ${\displaystyle O{\bigl (}VE+V^{2}(\log V)^{2}{\bigr )}}$	一度に1つのエッジが追加されるサブグラフにプッシュ再ラベル付けを行い、過剰量の多いプッシュを優先し、隣接リストをランダムに並べ替える
アロン[27]	1989	${\displaystyle O(VE+V^{8/3}\log V)}$	チェリヤンとハゲルップの非ランダム化
チェリヤン、ハゲラップ、メルホルン[28]	1990	${\displaystyle \displaystyle O\left({\frac {V^{3}}{\log V}}\right)}$	Alon による Cheriyan と Hagerup の非ランダム化を、4 人のロシア人の方法に関連するアイデアと組み合わせて使用​​し、余剰を押し出す高さを減らすエッジの検索を高速化します。
キング、ラオ、タルジャン[29]	1992	${\displaystyle O(VE+V^{2+\varepsilon })}$ いかなる ${\displaystyle \varepsilon >0}$	CheriyanとHagerupによるもう一つの非ランダム化。King、Rao、Tarjan（1994）の境界を弱めた予備版。
フィリップスとウェストブルック[30]	1993	${\displaystyle O(VE\log _{E/V}V+V(\log V)^{2+\varepsilon })}$ いかなる ${\displaystyle \varepsilon >0}$	同様のアイデアを使用して、King、Rao、および Tarjan 1992 から改良されました。
キング、ラオ、タルジャン[31]	1994	${\displaystyle O\left(VE\log _{\frac {E}{V\log V}}V\right)}$	同様のアイデアを使用して、フィリップスとウェストブルックから改良されました。
オーリン[9]	2013	${\displaystyle O(VE)}$	動的推移閉包のデータ構造を用いて維持される圧縮ネットワークに、ゴールドバーグとラオの擬似多項式アルゴリズムを適用します。 の時間は かかり、の場合に まで簡略化されます。一方、以前の境界は の場合に まで簡略化されます。 ${\displaystyle O{\bigr (}VE+E^{31/16}(\log V)^{2}{\bigr )}}$ ${\displaystyle O(VE)}$ ${\displaystyle E=O(V^{16/15-\varepsilon })}$ ${\displaystyle O(VE)}$ ${\displaystyle E=\Omega (V^{1+\epsilon })}$
オーリンとゴング[32]	2021	${\displaystyle \displaystyle O\left({\frac {VE\log V}{\log \log V+\log {\tfrac {E}{V}}}}\right)}$	Ahuja、Orlin、Tarjanの擬似多項式アルゴリズムに基づいています。King、Rao、Tarjanよりも高速で、リンク/カットツリーを使用しませんが、Orlin + KRTよりは高速ではありません。

擬似多項式と弱多項式

強多項式フローアルゴリズムの開発と並行して、入力容量の大きさに応じて実行時間が異なる擬似多項式および弱多項式の時間境界が数多く提案されてきました。ここで、 の値は、すべての容量を整数値に再スケーリングした後の最大エッジ容量を指します。（ネットワークに無理容量が含まれている場合、この再スケーリングは不可能な場合があり、これらのアルゴリズムは正確な解を生成しないか、近似解にさえ収束しない可能性があります。）擬似多項式境界と弱多項式境界の違いは、擬似多項式境界は において多項式になる可能性があるの に対し、弱多項式境界は においてのみ多項式になる点です。 ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle \log U}$

方法	年	複雑	説明
フォード・フルカーソンアルゴリズム[33]	1956	${\displaystyle O(EU)}$	残余グラフに開いているパスがある限り、そのパス上の残余容量の最小値を送信します。
バイナリブロッキングフローアルゴリズム[34]	1998	${\displaystyle O\left(E\cdot \min\{V^{2/3},E^{1/2}\}\cdot \log {\frac {V^{2}}{E}}\cdot \log U\right)}$
Kathuria-Liu-Sidford アルゴリズム[35]	2020	${\displaystyle E^{4/3+o(1)}U^{1/3}}$	内点法と-ノルムフローを用いたエッジブースティング。実行時間を達成したMadryの以前のアルゴリズムに基づいている。[36] ${\displaystyle \ell _{p}}$ ${\displaystyle {\tilde {O}}(E^{10/7}U^{1/7})}$
BLNPSSSW / BLLSSSWアルゴリズム[37] [38]	2020	${\displaystyle {\tilde {O}}((E+V^{3/2})\log U)}$	内点法とエキスパンダー分解による電流フローの動的維持。
Gao-Liu-Pengアルゴリズム[39]	2021	${\displaystyle {\tilde {O}}(E^{{\frac {3}{2}}-{\frac {1}{328}}}\log U)}$	Gao、Liu、およびPengのアルゴリズムは、[Mądry JACM '16]の内点法に基づくアルゴリズムの中核を成す、増大する電気の流れを動的に維持することに重点を置いています。これは、抵抗更新中のグラフにおいて、限られた設定において、大きな電気エネルギーを持つエッジを返すデータ構造を設計することを伴います。
Chen、King、Liu、Peng、Gutenberg、Sachdeva のアルゴリズム[10]	2022	${\displaystyle O(E^{1+o(1)}\log U)}$ 正確な複雑さは論文では明確に述べられていないが、 ${\displaystyle E\exp O(\log ^{7/8}E\log \log E)\log U}$	Chen、Kyng、Liu、Peng、Gutenberg、および Sachdeva のアルゴリズムは、一連の近似無向最小比率サイクルを通じてフローを構築することにより、最大フローおよび最小コスト フローをほぼ線形時間で解決します。各サイクルは、動的データ構造を使用して償却時間で計算および処理されます。 ${\displaystyle E^{1+o(1)}}$ ${\displaystyle E^{o(1)}}$
バーンスタイン、ブリクスタッド、サラヌラック、トゥー[40]	2024	${\displaystyle O(n^{2+o(1)}\log U)}$エッジ容量がセットから得られる場合のランダム化アルゴリズム ${\displaystyle \{1,\dots ,U\}}$	このアルゴリズムは、重み付き変種を導入したプッシュ・リラベル・アルゴリズムの変種です。本論文では、有向非巡回グラフ（DAG）上の重み関数を確立し、有向エクスパンダー階層を用いて一般グラフ上でそれを模倣しようと試みます。有向エクスパンダー階層は、自然な頂点順序付けを誘導し、DAGの特殊ケースと同様の重み関数を生成します。ランダム化の側面（そして結果として生じる係数）は、自然な動的更新が不可能なスパースカットの計算に有向エクスパンダー階層を適用することの難しさから生じています。 ${\displaystyle n^{o(1)}}$

積分フロー定理

積分フロー定理は、

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

主張は、フロー値が整数である（これは最大フロー最小カット定理から直接導かれる）というだけでなく、すべての辺におけるフローが整数であるという点も主張している。これは、多くの組み合わせ論的応用（後述）において極めて重要であり、ある辺を横切るフローは、その辺に対応するアイテムが求める集合に含まれるかどうかを符号化する可能性がある。

応用

多源多シンク最大フロー問題

図4.1.1. 多源多シンク最大フロー問題から単一源単一シンク最大フロー問題への変換

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}$

最大基数二部マッチング

図4.3.1. 最大二部マッチング問題から最大フロー問題への変換

二部グラフ が与えられたとき、における最大濃度マッチング、すなわち可能な限り最大の辺数を含むマッチングを求めます。この問題は、ネットワーク を構築することで最大フロー問題に変換できます。ここで、 ${\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}$

頂点容量による最大流量

図4.4.1. 頂点容量制約付き最大フロー問題をノード分割により元の最大フロー問題に変換する

ネットワークを仮定する。各ノードにはエッジ容量に加えて容量があり、つまり、フローが容量制約とフローの保存だけでなく、頂点容量制約も満たすよう なマッピングがあるとする。 ${\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}}}$

sからtへのパスの最大数

有向グラフと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完全である。^[41] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

閉鎖問題

有向グラフの閉包とは、頂点 C の集合であって、Cから辺が離れることのない集合である。閉包問題とは、頂点重み付き有向グラフにおいて、重みが最大または最小となる閉包を求める問題である。これは、最大フロー問題への帰着を用いて多項式時間で解くことができる。

現実世界の応用

野球の敗退

野球の消去問題のためのネットワークフローの構築

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

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

航空会社のスケジュール

航空業界における主要な問題の一つは、運航乗務員のスケジューリングです。航空スケジューリング問題は、拡張最大ネットワークフロー問題の応用として考えることができます。この問題の入力は、各フライトの出発地と到着地の情報を含むフライト集合Fです。航空スケジューリング問題の一つのバージョンでは、最大k人の乗務員で実現可能なスケジュールを作成することが目標となります。

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

G = ( V , E )を、 s , t ∈ V をソースノード、 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の実行可能なスケジュールを見つけることに等しいと主張され、証明されています。^[43]

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

循環と需要の問題

商品を生産する工場と、商品を配送する村がいくつかあります。これらの村は道路網で結ばれており、各道路は最大量の商品を流通させる容量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}}$

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

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

画像セグメンテーション

サイズ 8x8 のソース イメージ。

ビットマップから構築されたネットワーク。ソースは左側、シンクは右側にあります。エッジが暗いほど、その容量は大きくなります。ピクセルが緑のときa _{iは高く、緑でないときb i}は高くなります。ペナルティp _ijはすべて同じです。^[45]

クラインバーグとタルドスは著書の中で、画像を分割するアルゴリズムを提示している_。 ^[46]彼らは画像の背景と前景を見つけるアルゴリズムを提示している。より正確には、このアルゴリズムはビットマップを入力として以下のようにモデル化する。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).}$

ネットワーク上に表示される最小カット (三角形 VS 円)。

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

拡張機能

1.最小コストフロー問題では、各辺 ( u , v ) には、その容量に加えてコスト係数 a _uvも存在します。辺を通るフローがf _uvの場合、総コストはa _uv f _uvです。与えられたサイズdで、コストが最小となる フローを見つけることが求められます。ほとんどの変種において、コスト係数は正または負のいずれかになります。この問題には、様々な多項式時間アルゴリズムが存在します。

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

参考文献

1. Schrijver, A. (2002). 「輸送問題と最大フロー問題の歴史について」.数理計画. 91 (3): 437– 445. CiteSeerX  10.1.1.23.5134 . doi :10.1007/s101070100259. S2CID  10210675.
2. Gass, Saul I.; Assad, Arjang A. (2005). 「1951年から1956年までのオペレーションズ・リサーチの数学的、アルゴリズム的、そして専門的発展」.オペレーションズ・リサーチの注釈付き年表. オペレーションズ・リサーチ＆マネジメント・サイエンス国際シリーズ. 第75巻. pp.  79– 110. doi :10.1007/0-387-25837-X_5 (2025年7月1日現在休止). ISBN 978-1-4020-8116-3。{{cite book}}: CS1 maint: DOI inactive as of July 2025 (link)
3. Harris, TE ; Ross, FS (1955). 「鉄道の純輸送力評価方法の基礎」(PDF) .研究覚書. 2014年1月8日時点のオリジナル(PDF)からアーカイブ。
4. Ford, LR ; Fulkerson, DR (1956). 「ネットワークを通じた最大フロー」. Canadian Journal of Mathematics . 8 : 399–404 . doi : 10.4153/CJM-1956-045-5 .
5. Ford, LR, Jr.; Fulkerson, DR, Flows in Networks、プリンストン大学出版局 (1962)。
6. シャーマン、ジョナ (2013). 「ほぼ線形時間でほぼ最大フローを実現」.第54回IEEEコンピュータサイエンス基礎シンポジウム議事録. pp.  263– 269. arXiv : 1304.2077 . doi :10.1109/FOCS.2013.36. ISBN 978-0-7695-5135-7. S2CID  14681906。
7. Kelner, JA; Lee, YT; Orecchia, L.; Sidford, A. (2014). 「無向グラフにおける近似最大フローのためのほぼ線形時間アルゴリズムとその多種多様一般化」(PDF) .第25回ACM-SIAM離散アルゴリズムシンポジウム論文集. p. 217. arXiv : 1304.2338 . doi :10.1137/1.9781611973402.16. ISBN 978-1-61197-338-9. S2CID  10733914. 2016年3月3日時点のオリジナル（PDF）からアーカイブ。
8. ヘレン・ナイト（2014年1月7日）「新しいアルゴリズムは『最大フロー』問題の解決策を劇的に効率化できる」MITニュース。 2014年1月8日閲覧。
9. Orlin, James B. (2013). 「O(nm)時間で最大フロー、もしくはそれ以下」第45回ACMコンピューティング理論シンポジウム議事録. pp.  765– 774. CiteSeerX 10.1.1.259.5759 . doi :10.1145/2488608.2488705. ISBN  9781450320290. S2CID  207205207。
10. Chen, L.; Kyng, R.; Liu, YP; Gutenberg, MP; Sachdeva, S. (2022). 「ほぼ線形時間における最大フローと最小コストフロー」. arXiv : 2203.00671 [cs.DS].
11. Klarreich, Erica (2022年6月8日). 「研究者らがネットワークフローのための『驚くほど高速』なアルゴリズムを開発」. Quanta Magazine . 2022年6月8日閲覧。
12. Bernstein, Aaron; Nanongkai, Danupon; Wulff-Nilsen, Christian (2022年10月30日). 「近線形時間における負の重みを持つ単一源最短経路」. arXiv : 2203.03456 [cs.DS].
13. Brubaker, Ben (2023年1月18日). 「ついに負のグラフ上の最短経路のための高速アルゴリズムが発見された」Quanta Magazine . 2023年1月25日閲覧。
14. “FOCS 2022”. focs2022.eecs.berkeley.edu . 2023年1月25日閲覧。
15. サントシュ、ナガラカッテ. 「FOCS 2022 アーロン・バーンスタイン教授の論文が最優秀論文賞に選出」www.cs.rutgers.edu . 2023年1月25日閲覧。
16. エドモンズ, ジャック; カープ, リチャード M. (1972年4月). 「ネットワークフロー問題におけるアルゴリズム効率の理論的改善」. Journal of the ACM . 19 (2): 248– 264. doi :10.1145/321694.321699.1969 年アルバータ州カルガリーで開催された「組み合わせ構造とその応用に関する国際会議」において以前に発表されました ( MR  0266680)。
17. Dinic, EA (1970). 「ネットワークにおける最大フロー問題の解法と電力推定」. Doklady Akademii Nauk SSSR . 194 : 754–757 . MR  0287976.
18. Karzanov, AV (1974). 「ネットワークにおける最大フローを求める問題：プリフロー法による」. Doklady Akademii Nauk SSSR . 215 : 49–52 . MR  0343879.
19. Čerkasskiĭ, BV (1977). 「ネットワークにおける最大フロー構築のためのアルゴリズム（行動の労働消費を伴う）」『経済問題解決のための数学的手法』7 : 117–126 . MR  0503654. ${\displaystyle O(n^{2}{\sqrt {p}})}$
20. Malhotra, VM; Kumar, M. Pramodh; Maheshwari, SN (1978). 「ネットワークにおける最大フローを求めるためのO ( | V | 3 ) {\displaystyle O(|V|^{3})}アルゴリズム」(PDF) . Information Processing Letters . 7 (6): 277– 278. doi :10.1016/0020-0190(78)90016-9.
21. Galil, Zvi (1980). 「最大フロー問題に対するアルゴリズム」. Acta Informatica . 14 (3): 221– 242. doi :10.1007/BF00264254. MR  0587133. ${\displaystyle O(V^{5/3}E^{2/3})}$予備版、「最大フロー問題のための新しいアルゴリズム」、第 19 回コンピュータ サイエンスの基礎に関する年次シンポジウム (FOCS)、1978 年。
22. Galil, Zvi ; Naamad, Amnon (1980). 「最大フロー問題のためのアルゴリズム」. Journal of Computer and System Sciences . 21 (2): 203– 217. doi :10.1016/0022-0000(80)90035-5. ${\displaystyle O{\bigl (}EV(\log V)^{2}{\bigr )}}$1978 年に未発表原稿として配布され、1979 年に「ネットワーク フローと一般化パス圧縮」、第 20 回コンピュータ サイエンスの基礎に関する年次シンポジウム (FOCS)で予備的な形で公開されました ( doi :10.1145/800135.804394)。
23. Shiloach, Yossi.最大フローアルゴリズム（技術レポートSTAN-CS-78-802）. スタンフォード大学コンピュータサイエンス学部. ${\displaystyle O(nI\log ^{2}I)}$ガリル＆ナアマド（1980）による引用
24. Sleator, Daniel D. ; Tarjan, Robert Endre (1983). 「動的ツリーのためのデータ構造」. Journal of Computer and System Sciences . 26 (3): 362– 391. doi :10.1016/0022-0000(83)90006-5. MR  0710253.暫定版、第13回ACMコンピューティング理論シンポジウム（STOC）、1981年、doi :10.1145/800076.802464
25. Goldberg, AV ; Tarjan, RE (1988). 「最大フロー問題への新しいアプローチ」Journal of the ACM . 35 (4): 921. doi : 10.1145/48014.61051 . S2CID  52152408.暫定版、第18回ACMコンピューティング理論シンポジウム（STOC）、1986年、doi :10.1145/12130.12144
26. Cheriyan, Joseph; Hagerup, Torben (1995). 「ランダム化最大フローアルゴリズム」. SIAM Journal on Computing . 24 (2): 203– 226. doi :10.1137/S0097539791221529. MR  1320205.1989年の第30回コンピュータサイエンスの基礎に関する年次シンポジウム（FOCS）の予備版、doi :10.1109/SFCS.1989.63465
27. Alon, Noga (1990). 「擬似乱数順列の生成と最大フローアルゴリズム」(PDF) .情報処理レター. 35 (4): 201– 204. doi :10.1016/0020-0190(90)90024-R. MR  1066123.1989 年の原稿として Cheriyan、Hagerup、Mehlhorn (1990) に引用されました。
28. Cheriyan, Joseph; Hagerup, Torben; Mehlhorn, Kurt (1996). 「-時間最大フローアルゴリズム」. SIAM Journal on Computing . 25 (6): 1144– 1170. doi :10.1137/S0097539791278376. MR  1417893. ${\displaystyle o(n^{3})}$暫定版、「最大フローは時間内に計算できるか？」、第17回オートマトン、言語、プログラミング国際コロキウム（ICALP）、1990年、doi :10.1007/BFb0032035 ${\displaystyle o(nm)}$
29. King, Valerie ; Rao, S. ; Tarjan, Robert Endre (1992). 「より高速な決定論的最大フローアルゴリズム」. Frederickson, Greg N. (編). Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 27-29 January 1992, Orlando, Florida, USA . pp.  157– 164.
30. Phillips, Steven J. ; Westbrook, Jeffery R. (1998). 「オンライン負荷分散とネットワークフロー」. Algorithmica . 21 (3): 245– 261. doi :10.1007/PL00009214.暫定版、第25回ACMコンピューティング理論シンポジウム（STOC）、1993年、doi :10.1145/167088.167201。
31. King, V. ; Rao, S. ; Tarjan, R. (1994). 「より高速な決定論的最大フローアルゴリズム」. Journal of Algorithms . 17 (3): 447– 474. doi :10.1006/jagm.1994.1044. MR  1300259.
32. Orlin, James B.; Gong, Xiao-yue (2021). 「高速最大フローアルゴリズム」. Networks . 77 (2): 287– 321. doi :10.1002/net.22001. hdl :1721.1/134021. MR  4264487.
33. Ford, LR Jr. ; Fulkerson, DR (1956). 「ネットワークを通じた最大フロー」. Canadian Journal of Mathematics . 8 : 399–404 . doi :10.4153/CJM-1956-045-5. MR  0079251.
34. Goldberg, AV ; Rao, S. (1998). 「フロー分解障壁を超えて」Journal of the ACM . 45 (5): 783. doi : 10.1145/290179.290181 . S2CID  96030.
35. Kathuria, T.; Liu, YP; Sidford, A. (2020年11月16～19日). 「Almost Time」におけるユニット容量最大流量. 米国ノースカロライナ州ダーラム: IEEE. pp.  119～ 130. ${\displaystyle O(m^{4/3})}$
36. Madry, Aleksander (2016年10月9～11日). 「電気フローの増強による最大フロー計算」ニューブランズウィック、ニュージャージー州: IEEE. pp.  593– 602.
37. ブランド、J. vd;リー、YT;ナノンカイ、D.ペン、R.サラヌラック、T.シドフォード、A.ソング、Z。ワン・D. (2020 年 11 月 16 ～ 19 日)中程度に密なグラフ上のほぼ線形時間での 2 部マッチング。米国ノースカロライナ州ダーラム: IEEE。919–930ページ 。
38. Brand, J. vd; Lee, YT; Liu, YP; Saranurak, T.; Sidford, A; Song, Z.; Wang, D. (2021). 「密なインスタンスに対するほぼ線形時間での最小コストフロー、MDP、およびℓ1回帰」. arXiv : 2101.05719 [cs.DS].
39. Gao, Y.; Liu, YP; Peng, R. (2021). 「完全に動的な電気の流れ：スパースな最大流はゴールドバーグ・ラオ法よりも高速」. arXiv : 2101.07233 [cs.DS].
40. バーンスタイン、A.;ブリクスタッド、J.サラヌラック、T.火、T. (2024)。 「時間内の経路を拡張することによる最大の流れ」。 arXiv : 2406.03648 [cs.DS]。 ${\displaystyle n^{2+o(1)}}$
41. Itai, A.; Perl, Y.; Shiloach, Y. (1982). 「長さ制約下での最大分離パス探索の複雑さ」. Networks . 12 (3): 277– 286. doi :10.1002/net.3230120306. ISSN  1097-0037.
42. Schwartz, BL (1966). 「部分的に完了したトーナメントにおける可能性のある勝者」. SIAM Review . 8 (3): 302– 308. Bibcode :1966SIAMR...8..302S. doi :10.1137/1008062. JSTOR  2028206.
43. Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein (2001). 「26. 最大フロー」.アルゴリズム入門 第2版. MIT Press and McGraw-Hill. pp.  643– 668. ISBN 978-0-262-03293-3。{{cite book}}: CS1 maint: multiple names: authors list (link)
44. カール・キングスフォード. 「最大フロー拡張：需要のある循環」（PDF） .
45. のイラストを作成するためのソースコードを含むプロジェクトimagesegmentationwithmaxflow」。GitLab 。2019年12月22日時点のオリジナルよりアーカイブ。 2019年12月22日閲覧。
46. 「アルゴリズム設計」pearson.com . 2019年12月21日閲覧。
47. Schauer, Joachim; Pferschy, Ulrich (2013年7月1日). 「選言制約付き最大フロー問題」. Journal of Combinatorial Optimization . 26 (1): 109– 119. CiteSeerX 10.1.1.414.4496 . doi :10.1007/s10878-011-9438-7. ISSN  1382-6905. S2CID  6598669. 

さらに読む

• ジョセフ・チェリヤン、カート・メルホーン(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。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Maximum_flow_problem&oldid=1317651871"