この記事は
https://adventar.org/calendars/3598
の6日目の記事として書かれました。
昨日の記事はsatosさんの独断と偏見による根津/本郷飯事情でした。
19erのomochana2というものです。
最小全域木を扱う際で有効な定理を紹介したいと思います。めっちゃ数学っぽい話になって申し訳ないです。結果だけ知りたかったら四角で囲ってある部分をサーっと読んでください。一番下に定理を使って解ける演習問題も置いといたので、よかったら解いてください。
要は、辺が最小全域木に含まれたり含まれなかったりするための条件を考えようぜって話です。
カット特性
辺のコストが全て異なるとする。は空集合でも全体でもない点の部分集合であるとし、辺は端点の一方がに他方がに属する辺のうちでコストが最小のものであるとする。すると、どの最小全域木も辺を含む。
図にするとこうなっています。
ここで辺のコストはよりも小さいです。
軽く証明します。が最小全域木に含まれていないとします。すると、のような、とにまたがり、かつからへのパス上(図でオレンジ色で示してあります)にある辺が存在します。を削除して、を追加しましょう。すると新しいグラフも全域木となり、元の全域木よりもコストが下がりました。これは仮定と矛盾するので証明完了です。
簡単に言えばと、あるとにまたがる辺を交換しているわけですが、またがってさえすればどんな辺でもいいわけではないことです。実際とを交換してしまうと、閉路ができてしまい、全域木ではなくなってしまいます。
この定理を利用するとKruskal法やPrim法の正当性が出来ますが、ここでは割愛します。
閉路特性
辺のコストは全て異なるとする。をの任意の閉路とし、に属する辺で最もコストの大きい辺をとする。このときはGのどの最小全域木にも属さない。
カット特性は最小全域木に含まれる辺の条件だったのに対し、閉路特性は最小全域木に含まれない辺の条件です。これもカット特性のように辺を交換することによって証明できるので考えてみてください。
カット特性と閉路特性の合わせ技
ここからがアツいです。上の2つの定理を使うとこんなことが言えます。
辺のコストは全て異なるとする。辺について、 よりコストの小さい辺のみからなるパスでとを結ぶことができる はの最小全域木に含まれない。
証明.
この1,2が示されれば証明できたことになります。
まず、にを加えるとがコスト最大であるような閉路が得られるため、閉路特性からはの最小全域木には含まれません。これで1は示されました。
逆にとはよりコストの小さい辺のみからなるパスで結ぶことができないとします。点の集合を、よりコストの小さな辺のみからなるパスでから到達可能な全ての点の集合とします。すると、仮定からです。また、の定義から、一方の端点xがに属し、他方yがに属して、eよりコストの小さい辺は存在しません。もしそのような辺が存在したとすると、はよりコストの小さい辺のみからなるパスでから到達可能であるので、もまた到達可能になり、の定義に属するからです。これによりカット特性を使えば、2も示されたので証明完了です。
コストが同じ辺がある場合
コストが全て異なるなら場合分けが、
- よりコストの小さい辺のみからなるパスでとを結ぶことができる。
- よりコストの小さい辺のみからなるパスでとを結ぶことができない。
の2つでよかったんですが、コストが同じ辺がある場合は、 - 未満のコストの辺のみからなるパスでとを結ぶことができる。
- 未満のコストの辺のみからなるパスでとを結ぶことは出来ないが、以下のコストの辺のみからなるパスではとを結ぶことができる。
- 以下のコストの辺のみからなるパスでとを結ぶことができない。
と3つになります。ここで1と3、2と5が対応していることに注意します。
実は3と5は1,2の証明をほぼそのまま適用できます。よって結果も同じです
問題は4ですが、もしが最小全域木に含まれていないとするなら、最小全域木上のパスにとコストが同じ辺が存在します。もし上によりも大きい辺が存在するならばとを交換することによって、全域木のコストを下げることが出来てしまい矛盾します。よってにはコストが以下の辺しかないことになりますが、4の仮定により、未満のコストの辺のみからなるパスは存在しないため、全域木の全ての点が互いに到達可能であるという条件からが存在します。よってとを交換することによって、を最小全域木に含めることができました。
が最小全域木に含まれているとすると、上のとコストが同じで、最小全域木上にない辺が存在するので、これをと交換すればを最小全域木から除外できました。
以上より、4が成り立つときは、全ての最小全域木にはは含まれないが、を含む最小全域木は存在する、となります。証明できたことをまとめると、
グラフ上の辺について、
となります。これがおそらく一番使いやすい形になっています。
演習問題
- 連結グラフG(全ての点が互いに行き来可能)が与えられる。Gの特定の辺が指定されるのでを含むGの最小全域木が存在するかどうかで判定せよ
- 最小全域木が複数あるかどうか判定せよ
- "ほぼ木"が与えられる。このグラフは連結であり、を満たす。この時最小全域木をで与えよ
- (難)(これも紹介したかった)最小全域木の辺本をコスト順に並び替えたものをとする。ある全域木の辺本をコスト順に並び替えたものをとした時、全てのを満たす自然数に対し、を示せ(元ネタ: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)
参考文献
- Jon Kleinberg, Eva Tardos(2008)「アルゴリズムデザイン」浅野 孝夫, 浅野 泰仁, 小野 孝男, 平田富夫訳, 共立出版
明日の記事はlmt-swallowさんの"Browsing History Leakage (Sniffing?) について書きます"です。楽しみですね。