最大フロー最小カット定理

コンピュータサイエンスと最適化理論における最大フロー最小カット定理は、フロー ネットワークにおいて、ソースからシンクへ通過するフローの最大量は、最小カットのエッジの合計重み、つまり、削除された場合にソースとシンクを切り離すエッジの最小の合計重みに等しいことを述べています。

これは線型計画法の双対定理の特殊なケースであり、メンガーの定理やケーニッヒ・エゲルヴァーリの定理を導くために使うことができる。^[1]

この定理は、ネットワークを通る最大フローと、ネットワークのカットにおける最小容量という 2 つの量を等しくします。定理を述べるには、まずこれらの概念をそれぞれ定義する必要があります。

ネットワークは​

• 有限有向グラフ N = ( V , E )、ここでV は頂点の有限集合を表し、E ⊆ V × V は有向辺の集合を表す。
• ソースs ∈ Vとシンクt ∈ V ;​
• 容量関数は、c _uvまたはc ( u , v )（u、v）∈ Eで表されます。これは、エッジを通過できるフローの最大量を表します。${\displaystyle c:E\to \mathbb {R} ^{+}}$

ネットワークを通るフローとは、または で表されるマッピングであり、次の2つの制約に従います。 ${\displaystyle f:E\to \mathbb {R} ^{+}}$${\displaystyle f_{uv}}$${\displaystyle f(u,v)}$

1. 容量制約: すべてのエッジについて、${\displaystyle (u,v)\in E}$${\displaystyle f_{uv}\leq c_{uv}.}$
2. フローの保存:と(つまり、それぞれソースとシンク)以外の各頂点について、次の等式が成り立ちます。${\displaystyle v}$${\displaystyle s}$${\displaystyle t}$
   ${\displaystyle \sum \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\sum \nolimits _{\{w:(v,w)\in E\}}f_{vw}.}$

フローとは、各エッジの方向に沿ってネットワークを通過する流体の物理的な流れとして視覚化できます。容量制約は、単位時間あたりに各エッジを流れる量がエッジの最大容量以下であることを示し、保存制約は、ソース頂点とシンク頂点を除いて、各頂点に流入する量が各頂点から流出する量と等しいことを示します。

フローの値は次のように定義され ます。

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

ここで、はネットワークのソースで、はシンクです。流体のアナロジーで言えば、これはソースでネットワークに入る流体の量を表します。フローの保存公理により、これはシンクでネットワークから出るフローの量と同じです。 ${\displaystyle s}$${\displaystyle t}$

最大フロー問題は、特定のネットワーク上の最大フローを求めます。

最大フロー問題。を最大化、つまり、 から に可能な限り多くのフローをルーティングします。 ${\displaystyle |f|}$${\displaystyle s}$${\displaystyle t}$

最大フロー最小カット定理のもう半分は、ネットワークの別の側面、つまりカットの集合を指します。stカット C = ( S , T )は、 s ∈ Sかつt ∈ TとなるVの分割です。つまり、s - tカットは、ネットワークの頂点を 2 つの部分に分割したもので、一方の部分にソースがあり、もう一方の部分にシンクがあります。カットCのカットセットは、カットのソース部分とシンク部分を接続するエッジの集合です。 ${\displaystyle X_{C}}$

${\displaystyle X_{C}:=\{(u,v)\in E\ :\ u\in S,v\in T\}=(S\times T)\cap E.}$

したがって、 Cのカットセット内のすべてのエッジが削除されると、結果のグラフにソースからシンクへのパスが存在しないため、正のフローは不可能になります。

stカットの容量は、そのカットセット内のエッジの容量の合計です。

${\displaystyle c(S,T)=\sum \nolimits _{(u,v)\in X_{C}}c_{uv}=\sum \nolimits _{(i,j)\in E}c_{ij}d_{ij},}$

ここで、かつ の場合は、それ以外の場合は 。 ${\displaystyle d_{ij}=1}$${\displaystyle i\in S}$${\displaystyle j\in T}$${\displaystyle 0}$

通常、グラフには多くのカットがありますが、重みが小さいカットを見つけるのは困難な場合がよくあります。

最小 st カット問題。c ( S、T )を最小化します。つまり、st カットの容量が最小になるようにSとT を決定します。

上記の状況では、ネットワークを通るフローの値は、どのstカットの容量以下であること、さらに最大値を持つフローと最小容量を持つカットが存在することを証明できます。主な定理は、ネットワークの最大フロー値と最小カット容量を結び付けます。

最大フロー最小カット定理。stフローの最大値は、すべての st カットの最小容量に等しくなります。

右の図は、ネットワーク内のフローを示しています。各矢印の数字注釈 ( f / c形式) は、矢印のフロー ( f ) と容量 ( c ) を示しています。ソースから発せられるフローの合計は 5 (2+3=5) で、シンクへのフローの合計も 5 (2+3=5) であるため、フローの値は 5 であることがわかります。

値が 5 であるs - tカットは、 S ={ s、p } およびT ={ o、q、r、t } で与えられます。このカットを横切るエッジの容量は 3 と 2 なので、カット容量は 3+2=5 になります。( oからpへの矢印は、 TからSに戻るため、考慮されません。)

フローの値はカットの容量に等しく、フローが最大フローであり、カットが最小カットであることを示します。

SとT を接続する 2 つの矢印のそれぞれを通るフローが最大容量であることに注意してください。これは常に当てはまります。つまり、最小限のカットはシステムの「ボトルネック」を表します。

最大フロー問題と最小カット問題は、2つの主双対 線形計画法として定式化できる。^[2]

最大フロー LP は簡単です。デュアル LP は、デュアル線形計画法で説明されているアルゴリズムを使用して取得されます。デュアルの変数と符号制約はプライマリの制約に対応し、デュアルの制約はプライマリの変数と符号制約に対応します。結果の LP には説明が必要です。最小カット LP の変数の解釈は次のとおりです。

${\displaystyle d_{uv}={\begin{cases}1,&{\text{if }}u\in S{\text{ and }}v\in T{\text{ (エッジ }}uv{\text{ はカット内にある) }}\\0,&{\text{otherwise}}\end{cases}}}$

${\displaystyle z_{v}={\begin{cases}1,&{\text{if }}v\in S\\0,&{\text{otherwise}}\end{cases}}}$

最小化の目的は、カットに含まれるすべてのエッジの容量を合計することです。

制約は変数が合法的なカットを表すことを保証する：^[3]

• 制約（ と同等）は、非終端ノードu、vについて、 u がSにあり、vがTにある場合、エッジ（u、v）がカット（）にカウントされることを保証します。${\displaystyle d_{uv}-z_{u}+z_{v}\geq 0}$${\displaystyle d_{uv}\geq z_{u}-z_{v}}$${\displaystyle d_{uv}\geq 1}$
• 制約( と同等) は、 v がT内にある場合、エッジ(s,v)がカットにカウントされることを保証します( s は定義によりS内にあるため)。${\displaystyle d_{sv}+z_{v}\geq 1}$${\displaystyle d_{sv}\geq 1-z_{v}}$
• 制約( と同等) は、 u がS内にある場合、エッジ(u,t)がカットにカウントされることを保証します( t は定義によりT内にあるため)。${\displaystyle d_{ut}-z_{u}\geq 0}$${\displaystyle d_{ut}\geq z_{u}}$

これは最小化の問題なので、エッジがカットに含まれないことを保証する必要はなく、カットに含まれるべき各エッジが目的関数で合計されることを保証するだけでよいことに注意してください。

最大フロー最小カット定理の等式は、線形計画法の強い双対性定理から導かれます。この定理は、主計画が最適解x * を持つ場合、双対計画も最適解y * を持ち、2 つの解によって形成される最適値は等しいと述べています。

最大フロー問題は、非線形抵抗素子で構成されたネットワークを流れる電流の最大化として定式化できます。^[4]この定式化では、入力電圧Vが_に近づくにつれて、電気ネットワークの入力端子間_の電流Iの限界は、最小重みカットセットの重みに等しくなります。   ${\displaystyle \infty}$

${\displaystyle \lim _{V_{\text{in}}\to \infty }(I_{in})=\min _{X_{C}}\sum _{(u,v)\in X_{C}}c_{uv}}$

辺容量に加えて、各頂点に容量、つまりc ( v )で表されるマッピングがあり、フローfは容量制約とフローの保存だけでなく、頂点容量制約も満たす必要があると 考える。${\displaystyle c:V\to \mathbb {R} ^{+}}$  

${\displaystyle \forall v\in V\setminus \{s,t\}:\qquad \sum \nolimits _{\{u\in V\mid (u,v)\in E\}}f_{uv}\leq c(v).}$

言い換えると、頂点を通過するフロー量は、その容量を超えることはできません。 st カットを、 sからtへの任意のパスにカットのメンバーが含まれるような頂点と辺の集合として定義します。この場合、カットの容量は、カット内の各辺と頂点の容量の合計です。

この新しい定義では、一般化された最大フロー最小カット定理は、 st フローの最大値が新しい意味での st カットの最小容量に等しいことを述べています。

無向辺互いに素なパス問題では、無向グラフG = ( V、E )と 2 つの頂点sとtが与えられ、G内の辺互いに素な st パスの最大数を見つける必要があります。

メンガーの定理によれば、無向グラフ内の辺が互いに素な st パスの最大数は、st カットセット内の辺の最小数に等しいとされています。

プロジェクト選択問題では、 n 個のプロジェクトとm 台のマシンがあります。各プロジェクトp _{i は}収益r ( p _i )を生み出し、各マシンq _jの購入コストはc ( q _j )です。プロジェクトのサブセットを選択し、マシンのサブセットを購入して、総利益 (選択したプロジェクトの収益から購入したマシンのコストを差し引いたもの) を最大化したいと考えています。次の制約に従う必要があります。各プロジェクトでは、プロジェクトを選択した場合に購入する必要があるマシンのセットを指定します。(各マシンは、購入されると、選択したどのプロジェクトでも使用できます。)

この問題を解くには、選択されなかったプロジェクトの集合をP、購入された機械の集合を Qとすると、問題は次のように定式化できます。

${\displaystyle \max\{g\}=\sum _{i}r(p_{i})-\sum _{p_{i}\in P}r(p_{i})-\sum _{q_{j}\in Q}c(q_{j}).}$

最初の項はPとQの選択に依存しないので、この最大化問題は代わりに最小化問題として定式化することができる。つまり、

${\displaystyle \min\{g'\}=\sum _{p_{i}\in P}r(p_{i})+\sum _{q_{j}\in Q}c(q_{j}).}$

上記の最小化問題は、ソースが容量r ( p _i )のプロジェクトに接続され、シンクが容量c ( q _j )のマシンに接続されたネットワークを構築することで、最小カット問題として定式化できます。プロジェクトp _{i が}マシンq _{j を}必要とする場合は、無限容量のエッジ( p _i、q _j )が追加されます。st カットセットは、それぞれPとQのプロジェクトとマシンを表します。最大フロー最小カット定理により、この問題を最大フロー問題として解くことができます。

右の図は、次のプロジェクト選択問題のネットワーク定式化を示しています。

st カットの最小容量は 250 で、各プロジェクトの収益の合計は 450 です。したがって、プロジェクトp ₂とp ₃を選択すると、最大利益gは 450 − 250 = 200 になります。

ここでの考え方は、各プロジェクトの利益をそのマシンの「パイプ」を通じて「流す」ことです。マシンからパイプを満たすことができない場合、マシンの収益はコストよりも少なくなり、最小カット アルゴリズムは、マシンのコスト エッジではなくプロジェクトの利益エッジをカットする方が安価であると判断することになります。

画像分割問題には、 n 個のピクセルがあります。各ピクセルiには、前景値 f _iまたは背景値b _iを割り当てることができます。ピクセルi、jが隣接していて割り当てが異なる場合は、 p _ijのペナルティがあります。問題は、値の合計からペナルティを引いた値が最大になるように、ピクセルを前景または背景に割り当てることです。

Pを前景に割り当てられたピクセルの集合、Qを背景に割り当てられた点の集合とすると、問題は次のように定式化できます。

${\displaystyle \max\{g\}=\sum _{i\in P}f_{i}+\sum _{i\in Q}b_{i}-\sum _{i\in P,j\in Q\lor j\in P,i\in Q}p_{ij}.}$

この最大化問題は、最小化問題として定式化することができる。つまり、

${\displaystyle \min\{g'\}=\sum _{i\in P,j\in Q\lor j\in P,i\in Q}p_{ij}.}$

上記の最小化問題は、ソース（オレンジ色のノード）が容量 f _iのすべてのピクセルに接続され、シンク（紫色のノード）が容量b _iのすべてのピクセルに接続されるネットワークを構築することにより、最小カット問題として定式化できます。 p _ij容量を持つ2 つのエッジ ( i, j ) と ( j, i )が、隣接する 2 つのピクセル間に追加されます。 st カットセットは、 Pで前景に割り当てられたピクセルとQで背景に割り当てられたピクセルを表します。

この定理の発見については、 1962年にフォードとフルカーソンによって次のように説明されている。^[5]

「アークの容量制限を条件とするネットワーク内のある地点から別の地点への最大定常フローを決定することは、1955 年春に TE Harris によって著者に提起されました。彼は FS Ross (退役) 将軍と共同で鉄道交通フローの簡略モデルを作成し、この特定の問題をそのモデルが示唆する中心的な問題として特定しました。それから間もなく、最大フロー最小カット定理と呼ばれる主要な結果である定理 5.1 が推測され、確立されました。^[6]それ以来、多くの証明が発表されています。」^{[7] [8] [9]}

G = ( V , E )をネットワーク (有向グラフ) とし、sとtをそれぞれGのソースとシンクとします。

Ford-FulkersonアルゴリズムによってGに対して計算されたフローfを考えます。Ford -Fulkersonアルゴリズムによる最終的なフロー割り当て後のGに対して得られた残差グラフ( G _f  )において、頂点の2つのサブセットを次のように定義します。   

1. A : G _fのsから到達可能な頂点の集合
2. A ^c : 残りの頂点の集合、すなわちV − A

クレーム。 値(  f  ) = c ( A , A ^c )、ここでstカットの容量は次のように定義されます。

${\displaystyle c(S,T)=\sum \nolimits _{(u,v)\in S\times T}c_{uv}}$。

ここで、頂点の任意のサブセットAについてわかっています。したがって、value(  f  ) = c ( A , A ^c )の場合、次の式が必要です。 ${\displaystyle value(f)=f_{out}(A)-f_{in}(A)}$

• カットから出るすべてのエッジは完全に飽和している必要があります。
• カットへのすべての入ってくるエッジのフローはゼロでなければなりません。

上記の主張を証明するために、次の 2 つのケースを検討します。

• Gには、飽和していない出力エッジ 、つまりf  ( x , y ) < c _xyが存在します。これは、 G _fにxからyへの順方向エッジが存在することを意味し、したがってG _fにsからyへのパスが存在しますが、これは矛盾です。したがって、出力エッジ( x , y )はすべて完全に飽和しています。${\displaystyle (x,y),x\in A,y\in A^{c}}$ 

• Gには、ゼロ以外のフロー、つまりf  ( y、x ) > 0を運ぶ入ってくるエッジが 存在します。これは、 G _fにxからyへの逆方向のエッジが存在することを意味し、したがってG _fにsからyへのパスが存在しますが、これもまた矛盾です。したがって、入ってくるエッジ( y、x )はゼロフローを持つ必要があります。${\displaystyle (y,x),x\in A,y\in A^{c}}$ 

上記の両方の記述は、上記の方法で得られたカットの容量が、ネットワークで得られたフローに等しいことを証明しています。また、フローはFord-Fulkerson アルゴリズムによって得られたため、ネットワークの最大フローでも あります。

また、ネットワーク内のフローは常にネットワーク内で可能なすべてのカットの容量以下であるため、上記のカットは最大フローを実現する最小カットでもあります。

この証明から導かれる帰結は、グラフのカット内の任意のエッジ セットを通る最大フローは、それ以前のすべてのカットの最小容量に等しいということです。

• 近似最大フロー最小カット定理
• エドモンズ・カープアルゴリズム
• フローネットワーク
• フォード・フルカーソンアルゴリズム
• GNRS予想
• 線形計画法
• 最大流量
• メンガーの定理
• 最小カット

• ユージン・ローラー(2001)。「4.5. 最大フロー最小カット定理の組み合わせ的意味、4.6. 最大フロー最小カット定理の線形計画法による解釈」。組み合わせ最適化: ネットワークとマトロイド。ドーバー。pp. 117–120。ISBN 0-486-41453-1。
• Christos H. Papadimitriou、Kenneth Steiglitz (1998)。「6.1 最大フロー、最小カット定理」。組み合わせ最適化: アルゴリズムと複雑性。ドーバー。pp. 120–128。ISBN 0-486-40258-4。
• Vijay V. Vazirani (2004)。「12. LP-Duality 入門」。近似アルゴリズム。Springer。93～100 ページ。ISBN 3-540-65367-8。