無向グラフの最小カットを求めるアルゴリズム

Nagamochi-Ibaraki考案らしいです。

はじめに

この記事は無向グラフの最小カット、つまり無向グラフを2つに分断する時、切らなくてはならない道の本数の最小を高速に求めるアルゴリズムの解説をします。

アルゴリズムへの下準備

最大隣接順序

f(x, y)をxとyの間に張っている道の本数と定義します。
最初に、最大隣接順序というものを定義します。
最大隣接順序とは、まず好きな頂点を1つ選び、v_1とします。
次に、v_1と最も多い本数の道で繋がっている頂点をv_2とします。
つまり、v_1とv_2以外の任意の頂点mについて
f(v_1, v_2) ≧ f(v1, m)が成立します。
次に、v_1, v_2と最も多い本数の道で繋がっている頂点をv_3とします。
つまり、v_1とv_2とv_3以外の任意の頂点nについて
f(v_1, v_3) + f(v_2, v_3) ≧ f(v_1, n) + f(v_2, n)が成立します。
その後も同様にv_4, v_5,…, v_nと頂点を取っていきます。
このようにして定義したv_1, v_2,…,v_nの事が最大隣接順序です。

最大隣接順序による最小カット

最大隣接順序によって頂点を定義したとき、
c(v_n, v_n-1) = d(v_n) (①とします)
が成立します
なお、c(x, y)とはv_nとv_n-1の最小カット
d(x)とはf(v_1, x)+f(v_2, x)+…+f(x-1, v_n)の事をさします。
つまりd(v_n)とはf(v_1, v_n) + f(v_2, v_n) + … + f(v_n-1, v_n)の事をさします。

c(v_n, v_n-1) = d(v_n)の証明

まずはv_1, v_2, …, v_nから成り立つグラフをGとしましょう。
次に,Gからv_n-1とv_nの間の道だけを取り除いたグラフをG'とします。
G'で①が成立するならば、Gでも①が成立する事を示します。
この証明は簡単で、
c(v_n, v_n-1 : G') = c(v_n, v_n-1 : G) - f(v_n-1, v_n : G)
d(v_n : G') = d(v_n : G) - f(v_n-1, v_n : G)
の二式が明らかに成立ことから示せます。
なお、c(x, y : G), d(x, y : G)とはグラフGで考えた最小カット、道の本数、
c(x, y : G'), d(x, y : G')とはグラフG'で考えた最小カット、道の本数の事を示します。
以上の証明により、v_n-1とv_nの間に道が存在しない、つまりf(v_n-1, v_n)=0であるグラフのみを考えれば良い事が示せました。
以降、cやdにおいてグラフの指定が無い場合、G'のもとで考えているとします。

では①の証明を行いましょう。
証明は数学的帰納法で行います。
紙とペンを持って実際にグラフを書いてみる事をオススメしますが、n=3ぐらいまでは簡単に証明が出来ます。
よって①がn-1→nで成り立つ事を示せばよいですを示せばよいです。
v_1, v_2, …, v_n-1から成り立つグラフ、つまりG'からv_nとv_nから生えてる道を消したグラフをG'-v_nとします。

まずは
c(v_n-1, v_n-2) ≧ c(v_n-1, v_n-2 : G'-v_n) ≧ d(v_n-1 : G'-v_n) ≧ d(v_n)
を示します

c(v_n-1, v_n-2) ≧ c(v_n-1, v_n-2 : G'-v_n)
これは明らかです。

c(v_n-1, v_n-2 : G'-v_n) ≧ d(v_n-1 : G'-v_n)
G-v_nはn-1頂点のグラフゆえ、数学的帰納法の仮定から示せます。

d(v_n-1 : G'-v_n) ≧ d(v_n)
この式についてはまず、v_1, v_2, …, v_nが最大隣接順序であることを思い出してください。
v_n-1の頂点を決めるとき、v_1, v_2, …, v_n-2から生えている橋の本数が最も多い頂点を選びました。
つまり、
f(v_1, v_n-1) + f(v_2, v_n-1) + … + f(v_n-2, v_n-1) ≧ f(v_1, v_n) + f(v_2, v_n) + … + f(v_n-2, v_n)が成立します。
左辺はd(v_n-1 : G'-v_n)、右辺はd(v_n)-f(v_n-1, v_n)に他ならないですが、G'はf(v_n-1, v_n)=0ゆえ示せました。

次に、
c(v_n, v_n-2) ≧ c(v_n, v_n-2 : G'-v_n-1) ≧ d(v_n)
を示します。
G'-v_n-1とはG'からv_n-1,およびv_n-1から生えている橋を除去したグラフの事をさします。
c(v_n, v_n-2) ≧ c(v_n, v_n-2 : G'-v_n-1)
これは明らかです

c(v_n, v_n-2 : G'-v_n-1) ≧ d(v_n)
まず、G'-v_n-1はn-1頂点のグラフゆえ、数学的帰納法の仮定より
c(v_n, v_n-2 : G'-v_n-1) ≧ f(v_1, v_n) + f(v_2, v_n) + … + f(v_n-2, v_n)
が示せます。
さらに、G'ではf(v_n-1, v_n)=0ゆえ、
c(v_n, v_n-2 : G'-v_n-1) ≧ f(v_1, v_n) + f(v_2, v_n) + … + f(v_n-2, v_n) + f(v_n-1, v_n) = d(v_n)
が示せました。

以上示した式は2つで、
c(v_n-1, v_n-2 : G') ≧ d(v_n)
c(v_n, v_n-2 : G') ≧ d(v_n)
です。
v_nとv_n-1を最小カットで2つに分けたとき、v_n-2がv_nの側にあるならば
c(v_n, v_n-1) = c(v_n-1, v_n-2) ≧ d(v_n)
v_n-2がv_n-1の側にあるならば
c(v_n, v_n-1) = c(v_n, v_n-2) ≧ d(v_n)
が成り立ちます。つまり
c(v_n, v_n-1) ≧ d(v_n)
が成り立ち、数学的帰納法により①が示せました。

アルゴリズム

概要

①より、最大隣接順序を求めれば、
n-1とnの最小カットが求められます。
ここで、n-1とn-2の、n-1とnが同じ部分にある最小カットは、
n-1とnを仮想的に1つの頂点と見なす事で求められます。
同様に、どんどん頂点を統合していくことで、k+1, k+2, …, nがkと同じ部分にある(k, k+1)の最小カットが求められます
このようにして求めた(1, 2), (2,3), …, (n-1, n)の最小カットの中から、最小のものがグラフ全域での最小カットとなっています。
証明は、グラフ全域を最小カットで二つに分けたとき、
kとk+1が別の部分にあり、かつk+2, k+3, …, nがk+1と同じ部分にある、というkが必ず1つは存在する事によります。

計算量

最大隣接順序はV^2で求められ、それをV回行えば良いのでO(V^3)です。
なお、最大隣接順序はフィボナッチヒープを使うとO(E + log V)で求める事が出来るそうです。この場合はO(V E + V log V)となります。