ストアー・ワグナーアルゴリズム

最小カット重み4を持つ重み付きグラフの最小カット^{[ 1 ]}

グラフ理論において、ストアー・ワグナーアルゴリズムは、非負の重みを持つ無向重み付きグラフの最小カット問題を解く再帰アルゴリズムである。これは1995年にメヒチルト・ストアーとフランク・ワグナーによって提案された。このアルゴリズムの基本的な考え方は、グラフが結合された2つの頂点セットのみを含むまで、最も集約的な頂点をマージすることでグラフを縮小することである。^{[ 2 ]}各フェーズで、アルゴリズムは2つの頂点の最小-カットを見つけ、それを任意に選択します。次に、アルゴリズムは と の間の辺を縮小して、非-カットを検索します。すべてのフェーズで見つかった最小カットが、グラフの最小重み付きカットになります。 ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$

カットとは、グラフの頂点を2つの空でない互いに素な部分集合に分割することです。最小カットとは、カットのサイズまたは重みが他のどのカットのサイズよりも大きくならないカットのことです。重みのないグラフの場合、最小カットは単に辺の数が最も少ないカットになります。重みのあるグラフの場合、カット上のすべての辺の重みの合計によって、それが最小カットであるかどうかが決まります。実際には、最小カットはグラフまたはネットワークのボトルネックとなるため、最小カットの問題は常に最大フロー問題と併せて議論され、ネットワークの最大容量を探ります。

Stoer-Wagner 最小カット アルゴリズム

を重み付き無向グラフとする。 とする。または のちょうど1つがに含まれるとき、そのカットは-カットと呼ばれる。 の最小カットで-カットでもあるものは、 の-最小カットと呼ばれる。^{[ 3 ]}${\displaystyle G=(V,E,w)}$ ${\displaystyle s,t\in V}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle G}$

このアルゴリズムは、 における と、および の最初の最小カットを見つけることから始まります。任意の のペアについて、が の大域最小カットであるか、と が の大域最小カットの同じ側に属しているかの2 つの状況が考えられます。したがって、グラフ を調べることで大域最小カットを見つけることができます。グラフは、頂点と を新しい頂点 にマージした後のグラフです。マージ中に、と が辺で接続されている場合、この辺は消えます。と の両方に頂点 への辺がある場合、新しい頂点 からへの辺の重みはです。^{[ 3 ]}このアルゴリズムは次のように説明されます。^{[ 2 ]}${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle V}$ ${\displaystyle (S,T)}$ ${\displaystyle G}$ ${\displaystyle \left\{s,t\right\}}$ ${\displaystyle (S,T)}$ ${\displaystyle G}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle G}$ ${\displaystyle G\cup \{st\}/\left\{s,t\right\}}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle st}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle v}$ ${\displaystyle st}$ ${\displaystyle v}$ ${\displaystyle w(s,v)+w(t,v)}$

MinimumCutPhase を最も密に接続された頂点の 端 に追加します${\displaystyle (G,w,a)}$ ${\displaystyle A\gets \left\{a\right\}}$ ${\displaystyle \A\neq V}$ ${\displaystyle A}$  最後に残った頂点が単独で存在するカット（「位相のカット」）を保存する 最後に追加された 2 つの頂点 (s、t) をマージして縮小します(「位相カット」の値は、最小の s、t カットの値です)。${\displaystyle G}$ MinimumCut、MinimumCutPhaseの場合、カットオブザフェーズが現在の最小カットよりも軽い場合 は、カットオブザフェーズを現在の最小カットとして保存します。 ${\displaystyle (G,w,a)}$ ${\displaystyle |V|>1}$ ${\displaystyle (G,w,a)}$ 

アルゴリズムは段階的に機能します。 MinimumCutPhase では、グラフの頂点のサブセットは、任意の 1 つの頂点から始めて がに等しくなるまで成長します。各ステップで、 の外側にあるが、 と最も密接に接続されている頂点がセット に追加されます。この手順は、正式には次のように示されます。^{[ 2 ]}となる頂点 を追加します。ここで、はとの間のすべてのエッジの重みの合計です。したがって、1 つのフェーズで、頂点のペアおよび、および最小カットが決定されます。^{[ 4 ]} MinimumCutPhase の 1 つのフェーズの後、2 つの頂点は新しい頂点としてマージされ、2 つの頂点から残りの頂点へのエッジは、前の 2 つのエッジの重みの合計によって重み付けされたエッジに置き換えられます。マージされたノードを接続するエッジは削除されます。と を分離するの最小カットがある場合、はの最小カットです。そうでない場合、 の最小カットは同じ側にと を持っている必要があります。したがって、アルゴリズムはそれらを1つのノードとして統合します。さらに、MinimumCutは各MinimumCutPhaseの後にグローバル最小カットを記録し、更新します。フェーズが完了すれば、最小カットを決定できます。^{[ 4 ]}${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle V}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle z\notin A}$ ${\displaystyle w(A,z)=\max\{w(A,y)\mid y\notin A\}}$ ${\displaystyle w(A,y)}$ ${\displaystyle A}$ ${\displaystyle y}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s{\text{-}}t}$ ${\displaystyle C}$ ${\displaystyle G}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle C}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle n-1}$

例

このセクションでは、原著論文の図1～6を参照します。^{[ 2 ]}

ステップ 1 のグラフは元のグラフを示しており、このアルゴリズムの開始ノードとしてノード 2 をランダムに選択します。 MinimumCutPhase では、セット にはノード 2 のみがあり、最も重いエッジはエッジ (2,3) であるため、ノード 3 がセット に追加されます。 次に、セット にはノード 2 とノード 3 が含まれ、最も重いエッジは (3,4) であるため、ノード 4 がセット に追加されます。 この手順に従うと、最後の 2 つのノードはノード 5 とノード 1 になり、このフェーズでは と になります。 これらをノード 1+5 にマージすると、新しいグラフはステップ 2 のようになります。 このフェーズでは、カットの重みは 5 で、これはエッジ (1,2) と (1,5) の合計です。 これで、MinimumCut の最初のループが完了しました。 ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle s}$ ${\displaystyle t}$

ステップ2では、ノード2から始めて、最も重いエッジは(2,1+5)なので、ノード1+5がセットに追加されます。次に重いエッジは(2,3)または(1+5,6)なので、(1+5,6)を選択し、ノード6がセットに追加されます。次に、エッジ(2,3)と(6,7)を比較し、ノード3を選択してセットに追加します。最後の2つのノードはノード7とノード8です。したがって、エッジ(7,8)をマージします。最小カットは5なので、最小値は5のままです。 ${\displaystyle A}$ ${\displaystyle A}$

次の手順では、手順 7 に示すように、グラフ内のエッジが 1 つだけになるまで、マージされたグラフに対して同じ操作を繰り返します。グローバル最小カットにはエッジ (2,3) とエッジ (6,7) があり、これは手順 5 で検出されます。

正しさの証明

このアルゴリズムの正しさを証明するには、MinimumCutPhaseによって与えられたカットが、実際にはグラフの最小カットであることを証明する必要があります。ここで、sとtはフェーズで最後に追加された2つの頂点です。したがって、以下の補題が示されます${\displaystyle s{\text{-}}t}$

補題 1 : MinimumCutPhase は の最小-カットを返します。${\displaystyle s{\text{-}}t}$ ${\displaystyle G}$

を任意のカットとし、をフェーズで与えられたカットとします。 となることを示さなければなりません。MinimumCutPhase を 1 回実行すると、グラフ内のすべての頂点の順序がわかります (は最初の頂点、と はフェーズで最後に追加された 2 つの頂点です)。 頂点がアクティブであるとは、その直前に追加された頂点がカットの反対側にあることを意味します。 この補題は、アクティブ頂点の集合に対する帰納法で証明します。 をの前に に追加された頂点の集合と定義し、を の両端が にあるの辺の集合と定義します。つまり、は によって誘導されるカットです。 それぞれのアクティブ頂点 について、${\displaystyle C=(X,{\overline {X}})}$ ${\displaystyle s{\text{-}}t}$ ${\displaystyle CP}$ ${\displaystyle W(C)\geq W(CP)}$ ${\displaystyle a}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle A_{v}}$ ${\displaystyle A}$ ${\displaystyle v}$ ${\displaystyle C_{v}}$ ${\displaystyle C}$ ${\displaystyle A_{v}\cup \{v\}}$ ${\displaystyle C_{v}\subseteq C}$ ${\displaystyle A_{v}\cup \{v\}}$ ${\displaystyle v}$

${\displaystyle w(A_{v},v)\leq w(C_{v})}$

を最初のアクティブ頂点とします。これら2つの量の定義により、とは同値です。は単に より前に に追加されたすべての頂点であり、これらの頂点と の間の辺はカット を横切る辺です。したがって、上記のように、より前に が追加されたアクティブ頂点と について、次のようになります。${\displaystyle v_{0}}$ ${\displaystyle w(A_{v_{0}},v_{0})}$ ${\displaystyle w(C_{v_{0}})}$ ${\displaystyle A_{v_{0}}}$ ${\displaystyle A}$ ${\displaystyle v_{0}}$ ${\displaystyle v_{0}}$ ${\displaystyle C}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle A}$ ${\displaystyle u}$

${\displaystyle w(A_{u},u)=w(A_{v},u)+w(A_{u}-A_{v},u)}$

${\displaystyle w(A_{u},u)\leq w(C_{v})+w(A_{u}-A_{v},u)}$ 誘導によって、${\displaystyle w(A_{v},u)\leq w(A_{v},v)\leq w(C_{v})}$

${\displaystyle w(A_{u},u)\leq w(C_{u})}$ はに寄与するが には寄与しないので（そして他の辺は非負の重みを持つ）${\displaystyle w(A_{u}-A_{v},u)}$ ${\displaystyle w(C_{u})}$ ${\displaystyle w(C_{v})}$

したがって、定義により、位相の最後のカットが から分離するので、 は常にアクティブ頂点であり、任意のアクティブ頂点 に対して次のようになります。${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle t}$

${\displaystyle w(A_{t},t)\leq w(C_{t})=w(C)}$

したがって、位相のカ​​ットの大きさは最大で になります。 ${\displaystyle C}$

時間計算量

MinimumCutアルゴリズムの実行時間は、頂点と辺の数が減少するグラフで呼び出される MinimumCutPhaseの実行時間の合計に等しくなります${\displaystyle |V|-1}$

MinimumCutPhaseの場合、1 回の実行で最大時間かかります。 ${\displaystyle O(|E|+|V|\log |V|)}$

したがって、全体の実行時間は2つのフェーズの複雑さの積になるはずであり、それは^{[ 2 ]}である。${\displaystyle O(|V||E|+|V|^{2}\log |V|)}$

さらなる改善の鍵は、集合 に追加する次の頂点、つまり最も密に接続された頂点の選択を容易にすることです。フェーズの実行中、 にないすべての頂点は、キー フィールドに基づく優先キューに存在します。頂点のキーは、現在の に接続するエッジの重みの合計、つまり です。頂点が に追加されるたびに、キューの更新を実行する必要があります。をキューから削除し、に接続されにないすべての頂点のキーを、エッジ の重み (存在する場合) だけ増やす必要があります。 これはすべてのエッジに対して 1 回だけ実行されるため、全体としてExtractMax 操作とIncreaseKey 操作を実行する必要があります。フィボナッチ ヒープを使用することで、ExtractMax 操作を償却時間で実行し、IncreaseKey 操作を償却時間で実行できます。したがって、フェーズの残りの大部分を占めるこの重要なステップに必要な時間は です。^{[ 2 ]}${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle V}$ ${\displaystyle A}$ ${\displaystyle w(A,v)}$ ${\displaystyle v}$ ${\displaystyle A}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle A}$ ${\displaystyle v}$ ${\displaystyle vw}$ ${\displaystyle |V|}$ ${\displaystyle |E|}$ ${\displaystyle O(\log |V|)}$ ${\displaystyle O(1)}$ ${\displaystyle O(|E|+|V|\log |V|)}$

サンプルコード

以下は、ストアー・ワグナーアルゴリズムの簡潔なC++実装です。 ^{[ 5 ]}

// Stoer–Wagner min cut アルゴリズムの隣接行列実装。// //実行時間: // O(|V|^3)#include <bits/stdc++.h> using namespace std ;ペア< int 、ベクター< int >> globalMinCut (ベクター<ベクトル< int >> mat ) {ペア< int 、ベクター< int >> best = { INT_MAX 、{}}; int n = mat . size ();ベクター<ベクトル< int >> co ( n );for ( int i = 0 ; i < n ; i ++ ) co [ i ] = { i };for ( int ph = 1 ; ph < n ; ph ++ ) { vector < int > w = mat [ 0 ]; size_t s = 0 , t = 0 ; for ( int it = 0 ; it < n - ph ; it ++ ) { // O(V^2) -> O(E log V)、prio.queue の場合w [ t ] = INT_MIN ; s = t , t = max_element ( w . begin ()、w . end ()) - w . begin () ; for ( int i = 0 ; i < n ; i ++ ) w [ i ] += mat [ t ][ i ] ; } best = min ( best , { w [ t ] - mat [ t ][ t ]、co [ t ]} ); co [ s ] .挿入( co [ s ]. end ()、co [ t ]. begin ()、co [ t ]. end ()); for ( int i = 0 ; i < n ; i ++ ) mat [ s ][ i ] += mat [ t ][ i ]; for ( int i = 0 ; i < n ; i ++ ) mat [ i ][ s ] = mat[ s ][ i ];マット[ 0 ][ t ] = INT_MIN ; }ベストを返す; }

const int maxn = 550 ; const int inf = 1000000000 ; int n , r ; int edge [ maxn ][ maxn ], dist [ maxn ]; bool vis [ maxn ], bin [ maxn ];void init () { memset ( edge , 0 , sizeof ( edge )); memset ( bin , false , sizeof ( bin )); }int contract ( int & s , int & t ) // s、t を検索{ memset ( dist , 0 , sizeof ( dist )); memset ( vis , false , sizeof ( vis )); int i , j , k , mincut , maxc ;for ( i = 1 ; i <= n ; i ++ ) { k = -1 ; maxc = -1 ; for ( j = 1 ; j <= n ; j ++ ) if ( ! bin [ j ] && ! vis [ j ] && dist [ j ] > maxc ) { k = j ; maxc = dist [ j ]; } if ( k == -1 ) return mincut ; s = t ; t = k ; mincut = maxc ; vis [ k ] = true ; for ( j = 1 ; j <= n ; j ++ ) if ( ! bin [ j ] && ! vis [ j ]) dist [ j ] += edge [ k ][ j ]; }mincutを返します; }int Stoer_Wagner () { int mincut 、i 、j 、s 、t 、ans ;for ( mincut = inf 、i = 1 、i < n 、i ++ ) { ans = contract ( s 、t ); bin [ t ] = true ; if ( mincut > ans ) mincut = ans ; if ( mincut == 0 ) return 0 ; for ( j = 1 、j <= n 、j ++ ) if ( ! bin [ j ]) edge [ s ][ j ] = ( edge [ j ][ s ] += edge [ j ][ t ] ); }mincutを返します; }

参考文献

1. 「Boost Graph Library: Stoer– Wagner Min-Cut - 1.46.1」 . www.boost.org . 2015年12月7日閲覧
2. 「単純な最小カットアルゴリズム」。
3. 「アルゴリズム分析の講義ノート：グローバル最小カット」（PDF）。
4. 「StoerとWagnerの最小カットアルゴリズム」（PDF）。
5. 「KTHアルゴリズムコンペティションテンプレートライブラリ」 . github.com . 2021年11月17日閲覧。

外部リンク

• StoerWagnerMinCut.java - ストアー・ワグナーアルゴリズムを実装したJavaライブラリ