最小全域木問題の「凸性」①
☆この記事は、室田一雄・塩浦昭義『離散凸解析と最適化アルゴリズム』の1章及び8～13章をを参考にしていますが、証明の流れや定理の置き方などがかなり大幅に変わっています。誤りがあったらご報告いただけますと幸いです。
はじめに
重み付きグラフの全域木のうち、辺の重みの合計が最小になるものを求める問題を最小全域木問題と呼ぶ。
突然だが、「最小全域木問題は『離散版の凸関数の最大化問題』に帰着する」と言われてピンとくるだろうか。少なくとも僕はこの文章だけ見たら全然ピンと来ない。でも学んでいくうちに、確かに最小全域木の「凸っぽさ」が現れてきて、離散的な凸関数を定義することでこの文章の厳密な意味もわかる。そこで本稿ではまず、「最小全域木の凸っぽさ」をなんとなくつかめるようにして、アルゴリズムを紹介し、そこから離散的な凸関数を厳密に定義して、アルゴリズムを一般的な観点から再導出するという流れで話を進める。
この記事は3回に分け、今回は最小全域木の「凸っぽさ」の紹介とアルゴリズムの紹介・正当性の証明をおこなう。次回離散版の凸関数を定義し、そのうえでの最適化アルゴリズムを紹介して今回のアルゴリズムとの関連を述べる。3回目でより発展的な話題につなげる。
本稿の前提知識はグラフの基本的な用語および凸関数の定義・基本的な性質のみである。
1.最小全域木問題の「凸っぽさ」
辺に重み$w( \cdot )$がつけられた無向グラフ$G=(V,E)$の最小全域木とは、全域木（$G$の全頂点を要素に持つ木）であって、辺の重みの合計が最小になるものをいう。*1
$G$の最小とは限らない全域木$T$をひとつ取る。$T$よりも重みの小さい全域木を作りたかったら、どうすればよいだろうか？
$T$に含まれない辺$e$をひとつとる。$T$に$e$を付け加えると閉路（サイクル）が一つできる。この閉路を$C(T,e)$と書く。$C(T,e)$に含まれる辺$f$で$e$と異なるもの（これは$T$の要素である）を一つ選び$T \cup e$から除くと、$T \cup e \setminus f$は$T$とは異なる全域木になる。ここで、$w(e) < w(f)$が成り立つなら、新しくできた全域木$T \cup e \setminus f$は重みが$T$より真に小さい。*2
逆にいえば、$T$が最小全域木ならばこのようなことはできないはずだ。つまり、$T$が最小全域木ならば、「任意の$e \not\in T$と$f \in C(T,e)$に対して$w(e) \geq w(f)$」…（★）である。
（★）の条件は、「極小」に近い概念に見えないだろうか。関数の極小点と言われれば、近傍が存在して近傍内で最小になるような点であるが、上記のように$T$から辺$e$と$f$を入れ替えて到達できる全域木を「近傍」のように見るとすると、あたかも（★）は$T$の極小性を言っているように見える。そうすると、$T$が最小全域木ならば（★）が成り立つことも「最小⇒極小」というごく当たり前の性質に見えてくる。
ここで非自明なのは、今述べたことの逆が成り立つことである。すなわち、$T$が（★）をみたすならば、実は$T$は最小全域木になる。これを証明しよう。
定理1 任意の$e \not\in T$と$f \in C(T,e)$に対して$w(e) \geq w(f)$ が成り立つならば、$T$は最小全域木となる。
証明 もしも$T$より重みの真に小さい全域木$S$が存在したとする。$S,T$の辺の要素数は$ |V|-1$で等しいことに注意すると、$S \setminus T = \emptyset$だと$T=S$となり矛盾するので、$S \setminus T \neq \emptyset$である。
$S \setminus T$から辺$e$を選ぶ。$C(T,e)$の要素のうち$e$と異なるもので、さらに$S$に含まれないものをひとつとり$f$とする。もしそのような辺が存在しないと、$C(T,e)$の要素はすべて$S$の要素となり、$S$に閉路が存在することになり矛盾する。とり方より$f \in T \setminus S$である。ここで$T' =T\cup {e} \setminus {f}$とすると$T'$は全域木で、$T'$と$S$の共通部分の大きさは$T$と$S$のそれよりも1だけ大きくなっている。また定理の仮定より、$T'$の重みは$T$の重み以上である。このように$T$を更新することを繰り返せば最終的に$S$と等しくなり、したがって$S$の重みは$T$の重み以上である。これは最初の仮定に矛盾するので、$T$は最小全域木である。■
証明は意外にも単純であるが、ここで重要なのはこの定理が（気持ちとして）「極小⇒最小」を表していることである。こう見ると、早くも「凸っぽさ」がお分かりいただけたと思う。よく知られているように凸関数では、極小値がそのまま最小値になっている。
ただしもちろん「へえじゃあ最小全域木問題は凸関数なのね」と早合点することはできない。この場合の近傍は普通の実数での近傍と同じ意味では当然ない。また、ここでいう凸関数の定義域は全域木の全体で、各全域木に評価値が定義されていると思うと、定義域は実数のような連続的なものではなく、離散的なものである。この辺りを厳密に書くには凸関数の離散版のような定義が必要そうだ。そこでこの問題はいったん棚に上げることにして、最小全域木を求めるアルゴリズムを2つ紹介する。
2-1.クラスカル法
クラスカル法は、貪欲法（その場で最良のものを選択する）によって最小全域木を求めるアルゴリズムである。具体的には、次のように求める。
グラフを$G=(V,E)$とし、辺集合$T$をはじめ空集合とする。次の順番で$T$に辺を加えていく。まず、$T= \emptyset$に、$E$の辺で重みが最小の辺を加える。以降は、まだ加えていない$E$の辺で、加えても$T$に閉路ができないもののうち重みが最小の辺を加える。
このようにクラスカル法は「加えられる辺のうち一番良いものを加えていく」という貪欲的なもので、実装も楽で非常に有名なアルゴリズムである。競技プログラミングなどをやっている人は親の顔より実装していそうだ。
これが全域木を出力して停止することは少し考えれば明らかなので省略する。一方、「最小」全域木を出力することは全く自明ではない。これの証明はよい演習問題のようでどの本にも載っている。*3ここでは、定理1を用いることでシンプルに証明する。
証明（クラスカル法の正当性）
全域木を出力することの証明は省略する。クラスカル法を次のように等価に言い換えておくと見通しが良い。
「辺集合$T$をはじめ空集合とする。$E$を辺の重みが小さい順に並べ替え$ \{e_1, \cdots,e_m \}$とする。$k = 1,2, \cdots, m $の順で$T$に$e_k$を加えていく。但し$T$に$e_k$を加えたとき閉路ができてしまう場合は加えない。」
紛らわしいので今後$T$は最終的にできた全域木を表すものとする。ここで、クラスカル法において加えられなかった辺全体の集合が$E \setminus T$であることに注意する。加えられなかった辺$e \in E \setminus T$は、「加えると閉路ができてしまう辺」であり、その「閉路」とは$C(T,e)$に他ならない。$C(T,e)$の$e$以外の要素は$e$以前に加えられた辺なので重みは$e$のそれ以下である。ゆえに定理1より、$T$は最小全域木である。■
このように定理1を用いてうまく証明できることを見ると、この貪欲法は実は「加えなくていい辺を見事にスルー」できていることがわかる。
2-2.カラバ法
最小全域木を求めるもうひとつのアルゴリズムであるカラバ法を紹介する。クラスカル法が空集合から徐々に木を構成していくのに対し、カラバ法はまず全域木を適当に作り、それを「改善」していく。
アルゴリズム2（カラバ法）
グラフを$G=(V,E)$の頂点数を$n$,辺数を$ m $とする。$G$の最小全域木$T_0$をひとつとる。$F=E \setminus T_0 =\{f_1,\cdots,f_{m-n+1} \}$として、$t=1,\cdots,m-n+1$において次のステップ$t$を実行する：
ステップ$t$：$T_{t-1}$に$f_t$を加えると閉路$C_t=C(T_{t-1},f_t)$がひとつできる。$C_t$を構成する辺のうち重み最大のものを$e_t$とする（複数ある場合は一つ適当に選ぶ）。この時、$T_{t-1}$に$f_t$を加えたあと$e_t$を除去したものはまた全域木であるからこれを$T_t$とする。
最終的にできた$T_{m-n+1}$が出力である。
このアルゴリズムは計算量がヤバそうだが、何も考えずに木を良い方向に更新するのではなく、閉路で一番重みの大きいものを除去するという工夫をするだけでステップ数が$m-n+1$になっている。しかしなぜこれで最小全域木が出力されるかはやはり自明ではない。以下ではまた定理1を用いて正当性を証明する。
証明（カラバ法の正当性）
$T:=T_{m-n+1}$とする。一度除去された辺は二度と追加されないので、$\{e_1, \cdots,e_{m-n+1}\}=E \setminus T$である。クラスカル法のときと同様、「$C(T,e_t)$の任意の要素の重みが$e_t$の重み以下である」…（☆）ことを示せばよい。$C(T_{t},e_t)=C(T_{t-1},f_t)$なので、$C(T_{t},e_t)$の任意の要素の重みが$e_t$の重み以下であることは自明であるが、$C(T,e_t)$と$C(T_{t},e_t)$は異なるので少し注意しなければならない。
（☆）を帰納法で示す。$u \geq t$とする。$e_t$が$C(T_u,e_t)$で最大の重みをもつとして、$C(T_{u+1},e_t)$でも最大の重みをもつことを示す。
$C(T_u,e_t)=C(T_{u+1},e_t)$のときは良い。$C(T_u,e_t) \neq C(T_{u+1},e_t)$となるのは、ステップ$u+1$で$C(T_u,e_t)$の構成要素$e_{u+1}$が除去されるときである。この時、$C(T_{u+1},e_t)$はふたつの閉路の「合成」となる：$C(T_{u+1},e_t)=C(T_u,e_t) \cup C(T_u,f_{u+1}) \setminus e_{u+1} $である。ここで、$w(e_{u+1}) \leq w(e_t)$かつ$e_{u+1}$は$C(T_u,f_{u+1})$で重み最大の辺であることに注意すれば、$e_t$は$C(T_{u+1},e_t)$でも重み最大の辺となる。
$u=t$での成立は自明であるから、帰納法より$e_t$は$C(T,e_t)$の要素の中で重みが最大である。ゆえに定理1から、$T$が最小全域木であることが従う。■
カラバ法はクラスカル法と全然違うアルゴリズムに見えるが、「要らない辺を的確に除去している」という点ではクラスカル法とある意味似ていることがわかる。ただし、計算量はクラスカル法の方がよさそうである。*4
今回の議論を軽くまとめる。最小全域木問題はある種の「凸っぽさ（極小⇒最小）」を持っていることを示した（定理1）。次に定理1を用いて、2種類のアルゴリズムの正当性を示した。
繰り返しになるが、このように考えたときの「凸関数」の定義域は離散的である。すると今度は、「離散的な凸関数」を厳密に定義して以上の議論を一般化し、今出た2種類のアルゴリズムを導出してみたくなる。以下ではそれをやっていく。
