Boruvka

個人的メモ

(Boruvka 法の正当性)
Boruvka 法の正当性を考えてみる. 基本的には "縮約前のグラフに全域木が存在する $\Leftrightarrow$ 縮約後のグラフに全域木が存在する" および "(縮約後のグラフの最小全域木) $\cup$ (縮約した辺の集合) は縮約前のグラフの最小全域木となる" を示せば問題なさそうである. ここで辺コストはすべて異なるとして一般性を失わない.
$1$ つ目は縮約操作によってグラフの連結成分の数は変わらないので明らかで良いだろう.
$2$ つ目はまず元のグラフに全域木が存在するなら各頂点の隣接する最小コストの辺をすべて含む最小全域木が存在することを示す. もし最小全域木 $T \subseteq E$ 内に頂点 $u$ に隣接する最小コストの辺 $e^*$ が含まれていない場合, $T \cup \{ e^* \}$ は頂点 $u$ を含む閉路をちょうど $1$ つ含む. ここで閉路内の辺で $u$ に隣接する辺のうち $e^*$ でないものを $e'$ とする. このとき $(T \setminus \{ e' \}) \cup \{ e^* \}$ はグラフの全域木となり, $cost(e^*) < cost(e')$ という仮定より $T$ よりもコストの小さい最小全域木となり仮定に矛盾する. よって元のグラフに全域木が存在するなら各頂点の隣接する最小コストの辺をすべて含む最小全域木が存在する. 次に (縮約後のグラフの最小全域木) $\cup$ (縮約した辺の集合) が縮約前のグラフの最小全域木とならない場合を考える. ここで (縮約した辺の集合) を $S$ とおく(辺コストはすべて異なるという仮定から元のグラフについて一意に定まる). (縮約後のグラフの全域木) $\cup$ $S$ が (縮約前のグラフの全域木) となるという事実から (縮約後のグラフの最小全域木) $\cup$ $S$ は縮約前のグラフの最小でない全域木となることになる. ここで各頂点の隣接する最小コストの辺をすべて含む最小全域木 $T^*$ を取ってきたとする. $T^*$ 内の辺で各頂点の隣接する最小コストの辺に対応するもの(つまり辺集合 $S$) を縮約した木を $T'$ とする. $T'$ が縮約後のグラフの最小でない全域木になるとすると (縮約後のグラフの最小全域木) $\cup$ $S$ が縮約前のグラフの $T^*$ よりもコストの小さい全域木となることになり矛盾する. よって $T'$ は縮約後のグラフの最小全域木となる. ゆえに $T^* = T' \cup S$ のコストと比較すると (縮約後のグラフの最小全域木) $\cup$ $S$ は必ず縮約前のグラフの最小全域木となっている. よって示せた.

(平面グラフの辺数の上界について)
かなり基本的だが一応記す. 単純連結な平面グラフ $G=(V, E)$, $|V| \ge 3$ について考える. オイラーの多面体定理より $|V| - |E| + |F| = 2$ ($F$ は便宜上外側の面も含む面集合とする) が成り立つ. 各辺はちょうど $2$ 回数え上げられる & 各面は少なくとも $3$ 本以上の辺を含むことより $3|F| \le 2|E|$ が成り立つ. これと上記の定理より $|E| \le 3 |V| - 6$ となる.