最大流量問題

強多項式時間アルゴリズムは、入力の数のみに依存し、これらの数の大きさには依存しない多項式時間境界を持ちます。ここで、入力は頂点（以下、として番号付けされています）です。${\displaystyle V}$）とエッジ（番号は${\displaystyle E}$各アルゴリズムの複雑さは、ビッグオー記法を用いて表されます。

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

ネットワークが与えられた場合${\displaystyle N=(V,E)}$情報源のセットとともに${\displaystyle S=\{s_{1},\ldots ,s_{n}\}}$そしてシンク一式${\displaystyle T=\{t_{1},\ldots ,t_{m}\}}$1つのソースと1つのシンクだけでなく、最大フローを見つける必要があります${\displaystyle N}$複数のソースと複数のシンクの問題を最大フロー問題に変換するには、各頂点に接続する統合ソースを追加する必要があります。${\displaystyle S}$そして各頂点によって接続された統合シンク${\displaystyle T}$（スーパーソースおよびスーパーシンクとも呼ばれる）各エッジに無限の容量を持つ（図4.1.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}$各${\displaystyle e\in E'}$（図4.3.1を参照）。

次に、最大流量の値は${\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'}$その代わり。

一致するものが見つかったと仮定します${\displaystyle M}$の${\displaystyle G'}$カバーを構築しました${\displaystyle C}$そこから。直感的には、2 つの頂点が${\displaystyle u_{\mathrm {out} },v_{\mathrm {in} }}$一致する${\displaystyle M}$すると端が${\displaystyle (u,v)}$に含まれる${\displaystyle C}$明らかに、エッジの数は${\displaystyle C}$は${\displaystyle m}$それを見るために${\displaystyle C}$頂点が互いに素である場合、以下を考慮してください。

1. 各頂点${\displaystyle v_{\textrm {out}}}$で${\displaystyle G'}$一致しない可能性があります${\displaystyle M}$この場合、出る辺はありません${\displaystyle v}$で${\displaystyle C}$または、一致する場合、ちょうど1つのエッジが残ります${\displaystyle v}$で${\displaystyle C}$いずれの場合も、どの頂点からも出る辺は1本以下である。${\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}$頂点は互いに素である。

表紙を示すために${\displaystyle C}$サイズがあります${\displaystyle n-m}$まず、空のカバーから始めて、段階的に構築していきます。頂点を追加するには${\displaystyle u}$カバーに対して、既存のパスに追加するか、その頂点から始まる長さゼロの新しいパスを作成するかのいずれかを選択できます。前者のケースは、${\displaystyle (u,v)\in E}$そしてカバー内のパスは${\displaystyle v}$、 または${\displaystyle (v,u)\in E}$そして、ある道はそこで終わる${\displaystyle v}$後者の場合が常に適用可能です。前者の場合、被覆内のエッジの総数は 1 増加し、パスの数は変わりません。後者の場合、パスの数は増加し、エッジの数は変わりません。これで、すべてを被覆した後、${\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\}.}$

つまり、頂点を通過する流量はその容量を超えることはできません。${\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}}}$（図4.4.1参照）。この拡張されたネットワークでは、頂点容量の制約が取り除かれているため、この問題は元の最大フロー問題として扱うことができる。

有向グラフが与えられた場合${\displaystyle G=(V,E)}$そして2つの頂点${\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. パスは辺が互いに素であること、および/または頂点が互いに素であることに加えて、長さの制約もあります。長さがちょうど のパスのみをカウントします。${\displaystyle k}$またはせいぜい${\displaystyle k}$この問題のほとんどの変種はNP完全であるが、 の値が小さい場合は例外である。${\displaystyle k}$[ ^{43 ]​}

有向グラフの閉包とは、頂点の集合 C からどの辺も出ないような頂点の集合 C のことである。閉包問題とは、頂点重み付き有向グラフにおいて、最大重みまたは最小重みの閉包を見つける問題である。この問題は、最大フロー問題への還元を用いることで多項式時間で解くことができる。

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

G = ( V , E )を、s、t ∈ Vをそれぞれソースおよびシンクとするネットワークとする。ゲームノード_ijを追加する。これは、これら 2 つのチーム間のプレイ数を表す。また、各チームにチームノードを追加し、i < jである各ゲームノード{ i、j }をVに接続し、 sからそれぞれをエッジで接続する。エッジの容量はr _ijであり、これはこれら 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を始点ノードおよび終点ノードとするネットワークとする。各フライト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. 出発地s _jがフライトiの目的地から妥当な時間とコストで到達可能な場合、各d _iとs _jの間に容量 [0, 1] のエッジが存在する。
5. sとtの間に容量[0, ∞ ]のエッジが存在する。

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

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

製品を生産する工場と、その製品を配送する村々がある。これらは道路網で結ばれており、各道路には通過できる最大貨物量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}}$。

循環が存在する場合、最大流量解を調べることで、需要を満たすために特定の道路でどれだけの貨物を輸送する必要があるかという答えが得られる。

この問題は、一部のエッジにおけるフローの下限を追加することで拡張できる。^{[ 46 ]}

クラインバーグとタルドスは著書の中で、画像のセグメンテーションアルゴリズムを提示している_{[48]。彼らは、画像内の背景と前景を検出するアルゴリズムを提示している。より正確には、このアルゴリズムは、以下のようにモデル化されたビットマップを入力として受け取る。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で接続します。あとは、このネットワークにおける最小カット（または同等の最大フロー）を計算するだけです。最後の図は最小カットを示しています。