最小全域木

この記事は
https://adventar.org/calendars/3598
の6日目の記事として書かれました。
昨日の記事はsatosさんの独断と偏見による根津/本郷飯事情でした。

19erのomochana2というものです。
最小全域木を扱う際で有効な定理を紹介したいと思います。めっちゃ数学っぽい話になって申し訳ないです。結果だけ知りたかったら四角で囲ってある部分をサーっと読んでください。一番下に定理を使って解ける演習問題も置いといたので、よかったら解いてください。

要は、辺が最小全域木に含まれたり含まれなかったりするための条件を考えようぜって話です。
カット特性

辺のコストが全て異なるとする。 Sは空集合でも V全体でもない点の部分集合であるとし、辺 e=(v,w)は端点の一方が Sに他方が V-Sに属する辺のうちでコストが最小のものであるとする。すると、どの最小全域木も辺 eを含む。

図にするとこうなっています。
ここで辺 eのコストは e',fよりも小さいです。

軽く証明します。 eが最小全域木に含まれていないとします。すると、 e'のような、 Sと V-Sにまたがり、かつ vから wへのパス上(図でオレンジ色で示してあります)にある辺が存在します。 e'を削除して、 eを追加しましょう。すると新しいグラフも全域木となり、元の全域木よりもコストが下がりました。これは仮定と矛盾するので証明完了です。
簡単に言えば eと、ある Sと V-Sにまたがる辺を交換しているわけですが、またがってさえすればどんな辺でもいいわけではないことです。実際 eと fを交換してしまうと、閉路ができてしまい、全域木ではなくなってしまいます。

この定理を利用するとKruskal法やPrim法の正当性が出来ますが、ここでは割愛します。

閉路特性

辺のコストは全て異なるとする。 Cを Gの任意の閉路とし、 Cに属する辺で最もコストの大きい辺を eとする。このとき eはGのどの最小全域木にも属さない。

カット特性は最小全域木に含まれる辺の条件だったのに対し、閉路特性は最小全域木に含まれない辺の条件です。これもカット特性のように辺を交換することによって証明できるので考えてみてください。

カット特性と閉路特性の合わせ技
ここからがアツいです。上の2つの定理を使うとこんなことが言えます。

辺のコストは全て異なるとする。辺 e=(v,w)について、 eよりコストの小さい辺のみからなるパス Pで vと wを結ぶことができる \Leftrightarrow eは Gの最小全域木に含まれない。

証明.

  1. eよりコストの小さい辺のみからなるパス Pで vと wを結ぶことができる。 \Rightarrow eは Gの最小全域木に含まれない。
  2. eよりコストの小さい辺のみからなるパスで vと wを結ぶことができない。 \Rightarrow eは Gの最小全域木に含まれる。

この1,2が示されれば証明できたことになります。 まず、 Pに eを加えると eがコスト最大であるような閉路が得られるため、閉路特性から eは Gの最小全域木には含まれません。これで1は示されました。
逆に vと wは eよりコストの小さい辺のみからなるパスで結ぶことができないとします。点の集合 Sを、 eよりコストの小さな辺のみからなるパスで vから到達可能な全ての点の集合とします。すると、仮定から w \in V - Sです。また、 Sの定義から、一方の端点xが Sに属し、他方yが V-Sに属して、eよりコストの小さい辺 fは存在しません。もしそのような辺が存在したとすると、 xは eよりコストの小さい辺のみからなるパスで vから到達可能であるので、 yもまた到達可能になり、 Sの定義に属するからです。これによりカット特性を使えば、2も示されたので証明完了です。

コストが同じ辺がある場合
コストが全て異なるなら場合分けが、

  1. eよりコストの小さい辺のみからなるパス Pで vと wを結ぶことができる。
  2. eよりコストの小さい辺のみからなるパスで vと wを結ぶことができない。
    の2つでよかったんですが、コストが同じ辺がある場合は、
  3. e未満のコストの辺のみからなるパス Pで vと wを結ぶことができる。
  4. e未満のコストの辺のみからなるパスで vと wを結ぶことは出来ないが、 e以下のコストの辺のみからなるパス P'では vと wを結ぶことができる。
  5. e以下のコストの辺のみからなるパスで vと wを結ぶことができない。

と3つになります。ここで1と3、2と5が対応していることに注意します。

実は3と5は1,2の証明をほぼそのまま適用できます。よって結果も同じです
問題は4ですが、もし eが最小全域木に含まれていないとするなら、最小全域木上のパス Qに eとコストが同じ辺 e'が存在します。もし Q上に eよりも大きい辺 fが存在するならば eと fを交換することによって、全域木のコストを下げることが出来てしまい矛盾します。よって Qにはコストが e以下の辺しかないことになりますが、4の仮定により、 e未満のコストの辺のみからなるパスは存在しないため、全域木の全ての点が互いに到達可能であるという条件から e'が存在します。よって eと e'を交換することによって、 eを最小全域木に含めることができました。
eが最小全域木に含まれているとすると、 P'上の eとコストが同じで、最小全域木上にない辺 e'が存在するので、これを eと交換すれば eを最小全域木から除外できました。

以上より、4が成り立つときは、全ての最小全域木には eは含まれないが、 eを含む最小全域木は存在する、となります。証明できたことをまとめると、

グラフ G=(V,E)上の辺 e=(v,w)について、

  1. e未満のコストの辺のみからなるパス Pで vと wを結ぶことができる。 \Rightarrow eを含む Gの最小全域木は存在しない。
  2. e未満のコストの辺のみからなるパスで vと wを結ぶことは出来ないが、 e以下のコストの辺のみからなるパス P'では vと wを結ぶことができる。 \Rightarrow eは Gの全ての最小全域木には含まれないが、 eを含む Gの最小全域木は存在する。
  3. e以下のコストの辺のみからなるパスで vと wを結ぶことができない。 \Rightarrow eは Gの全ての最小全域木に含まれる。

となります。これがおそらく一番使いやすい形になっています。

演習問題

  1. 連結グラフG(全ての点が互いに行き来可能)が与えられる。Gの特定の辺 eが指定されるので eを含むGの最小全域木が存在するかどうか O(|V|+|E|)で判定せよ
  2. 最小全域木が複数あるかどうか判定せよ
  3. "ほぼ木"が与えられる。このグラフは連結であり、 |E|=|V|+8を満たす。この時最小全域木を O(|V|)で与えよ
  4. (難)(これも紹介したかった)最小全域木の辺 |V|-1本をコスト順に並び替えたものを aとする。ある全域木の辺 |V|-1本をコスト順に並び替えたものを bとした時、全ての 0 \leq i \leq |V|-2を満たす自然数 iに対し、 a_i \leq b_iを示せ(元ネタ:http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2012%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=MedianTree.pdf)

参考文献

  1. Jon Kleinberg, Eva Tardos(2008)「アルゴリズムデザイン」浅野 孝夫, 浅野 泰仁, 小野 孝男, 平田富夫訳, 共立出版

明日の記事はlmt-swallowさんの"Browsing History Leakage (Sniffing?) について書きます"です。楽しみですね。