アルゴリズムイントロダクション第21章「最小全域木」
binomialsheepこれは
アルゴリズムイントロダクション第4版 21章「最小全域木」の気になった問題を解いたりする。
単にプリム法とクラスカル法の紹介だけではなく、いくつかの興味深い話題がある。
binomialsheep21.1 最小全域木の成長
プリム法、クラスカル法は、どちらも「辺を1本ずつ加えて手持ちの最小全域木を成長させる貪欲戦略」だが、どちらも「常にある最小全域木の部分集合であるような普遍指揮を維持しながら、安全な辺（safe edge）を加える」手続きとして捉えることができる。
このsafe edgeの性質と定理の証明を行っている。
練習問題
21.1-8
あるグラフにおける任意の最小全域木は、辺の重みの多重集合が等しい。これを証明せよ。
21.1-11
MSTに属さない1本の辺の重みが減少した時、変更されたグラフの最小全域木を求めるアルゴリズムを設計せよ。
→その辺(u, v)を加えてできる閉路（つまりMST中の(u, v)パスと(u,v)）のうち重みが最大のものを取り除けばよい
binomialsheep21.2 Kruskal とPrim のアルゴリズム
クラスカル法の計算量は辺のソートがボトルネックでO(E lg E)。E<V^2で、lg(V^2)=2lgVなので、O(E lg V)でもある。
プリム法も二分ヒープを使うと同じだが、フィボナッチヒープを使うとO(E+VlgV)に改善できる。
練習問題
21.2-2
隣接行列を用いたプリム法のΘ(V^2)実装について。
「現在到達可能な頂点集合から、各頂点までの最小の重み」を長さVの配列で管理すればよい。
適当に到達不能をINFで管理し、到達可能な頂点が増えるごとにΘ(V)で更新、最小の重みをΘ(V)で取得し、これをV回繰り返すのでΘ(V^2)。
21.2-3で、疎グラフの場合は二分ヒープ実装より漸近的に遅いが、密グラフの場合は漸近的に速いことを確認する。
21.2-8
既にMSTが求まっているグラフに、頂点とその頂点への辺を追加した場合にMSTを再計算する方法について。
単に最も軽い辺を採用するだけではダメ。例えば既存の辺の重みが全て2以上で、今回新しく|V|本の重み1の辺を追加したかもしれない。
改めて1からMSTを構築するよりも漸近的に高速なアルゴリズムは、簡単ではない。
(u, v)パス上の最大重み辺を高速に見つけて、更に辺を追加後に木の情報を高速に更新できる必要がある。
Link-Cut Treeでできると思う。
binomialsheep章末問題 21.1 準最小全域木
全ての辺の重みが異なる重み付き連結無向グラフについて考える。
準最小全域木（second-best minimum spanning tree）は、最小全域木以外で辺の重み和が最小の全域木のことを呼ぶ。
a
問題：最小全域木は一意だが、順最小全域木は一意とは限らないことを示せ
回答：
全ての辺の重みが異なるので、最小全域木は一意。
準最小全域木が一意でないのは具体例を構成すればよい。
b
問題：最小全域木との差が1本だけの最小全域木が存在することを示せ
回答：
最小全域木Tとの辺の差分が最小になるような準最小全域木（の1つ）T'を考える。
TになくT'にある辺を、重みの昇順に加える。
ここで、1本目の差分辺e1を加えてできる閉路から、e1を除いて重み最大の辺e2を取り除くと、それは木になる（T''と置く）
TとT'の差が2本以上と仮定すると、T''はT'ではない。T'を構築するには、T''にe1よりも重い辺e3を加えて、e3よりも軽い辺e4を取り除く必要がある。
したがってw(T)<w(T'')<w(T')になる。
これはT'が辺の差分最小の準最小全域木であることに矛盾するので、TとT'の差が1本であるような準最小全域木が存在する。
c
問題：
（最小とは限らない）任意の全域木をTとする。任意の2頂点(u, v)について、Tにおけるuとvを結ぶ（唯一の）単純路上で重み最大の辺をmax[u, v]とする。
Tが与えられた時、全ての(u, v)についてmax[u, v]をO(V^2)で求めるアルゴリズムを設計せよ。
回答：
全始点からΘ(V)で経路上の最大値を持ってDFS。
d
問題：
準最小全域木を効率的に求めるアルゴリズムを設計せよ。
回答：
- 最小全域木を構築する（Θ(ElgV))
- cの手順でmax[x, y]を計算する(Θ(V^2))
- （MST外の）全ての辺について、w(x,y)-max[x,y]を計算して最小の差分を求める（Θ(E))
これで、差分が1本の場合について、差分の重み差が最小の辺が求まる。
bより、これは準最小全域木の1つ。
計算量はΘ(E lg V + V^2)。
cで、LCAまでダブリングするようにすればmaxを求める処理が辺あたりΘ(lg V)になるので疎グラフの場合Θ(E lg V)に高速化できる。
ちなみにk‑最小全域木という問題もある。
binomialsheep章末問題 21.2 疎なグラフの最小全域木
ブルーフカ法の問題。
binomialsheep章末問題 21-3 最小全域木アルゴリズムの代案
重み付き連結無向グラフを受け取って辺の集合Tを返す以下の3つのアルゴリズムについて、
- 最小全域木を求めるアルゴリズムになっているか
- 効率のいい実装を設計せよ
MAYBE-MST-A
// 辺を重みwの単調減少順にソートする
sort(E);
T = E;
for(e : E) {
if(eを取り除いてもTが連結) eを取り除く
}
return T;
いわゆるReverse‑Delete algorithm。
重い順に閉路を壊している。各閉路から最大辺が必ず消えるので、結果はMSTになる。
「取り除いても連結か？」の判定が重い。
逆から見ればクラスカル法（重い順に取り除くか、軽い順に足すか）なので、クラスカル法実装が高速。
MAYBE-MST-B
T = {};
for(e : E) { // Eは任意の順序
Tにeを追加しても閉路にならないなら、追加する
}
return T;
任意の順序で、「閉路ができないなら追加」をした場合。
木は得られるが、もちろんMSTにならない（反例は簡単）
計算量はソートしないのでΘ(Eα(V))で済む（αはUnion-Findで現れるアッカーマンの逆関数）
MAYBE-MST-C
T = {}
Eは任意の順序
for(e : E) { // Eは任意の順序
Tにeを追加する
サイクルができたら、最も重い辺を削除する
}
辺を追加してみて閉路になったら一番重い辺を削除する。
これはBとは異なり、閉路の最も重い辺を削除しているので、MSTになる。
高速な実装は練習問題21.2-8と同じ理由で難しい。
binomialsheep章末問題21-4 ボトルネック全域木
MSTはボトルネック全域木の1つだが、ボトルネック全域木だけならより高速に求まる。
面白い分割統治法だが、ブルーフカ法の理解も必要。