Skip to content →

ブルーフカ法

最小全域木を \(O(\min(n^2,m\log(n)))\) で求めるアルゴリズム(\(m\):辺数、\(n\):頂点数)であるブルーフカ法を解説します。

最小全域木とは、各辺 \(e\) に対して重み \(c(e)\) が定まったグラフの全域木 \(T\) のうち、重み \(\sum_{e\in T} c(e)\) 最小のものです。

ブルーフカ法は、クラスカル法やプリム法と比較して、唯一ソートがいらないアルゴリズムです。他の二つの方法はソートがボトルネックになっています。

アルゴリズム

  1. \(G\)が1頂点になるまで次の操作を繰り返します:
    1. 各頂点 \(v\) について、接続する辺のうち最も重みの辺 \(e_v\) を見つけます。
    2. 各 \(e_v\) を最小全域木の辺として(縮約を解いて)採用します。
    3. 各 \(e_v\) を縮約して、\(G \leftarrow G/e_v\) とします。自己辺が生じた場合は取り除きます。

全ての辺の重みが異なるならば、(iii) で縮約する辺がサイクルをなすことはありません。もし頂点 \(0,1,\ldots,k-1\) がこの順(\(i,i\pm1 \bmod k\) が隣接)でサイクルを成しており、各頂点の重み最小の辺が \(f_0,f_1,\ldots,f_{k-1}\) だとします。すると、\(f_0 > f_1 > \cdots > f_{k-1} > f_0\) となり矛盾です。辺の重みが同じものがある場合、ラベルの辞書順で順序付けて、重みが異なる場合に帰着する必要があります。

(iii) は \(e_1, e_2, \ldots, e_{|G|}\) で形成される森の各連結成分を DFS で求めて縮約してから、辺を全て張りなおせば \(O(m)\) でできます。Union Find を使うと \(O(\alpha(n))\) が余分に係るので注意(\(\alpha\):アッカーマンの逆関数)。

(i)-(iii) を一巡するたびに頂点数が少なくとも半減します。(i) で辺数の \(O(m)\) がかかるので、全体では \(O(m \log(n))\) です。多重辺を除去しないので、(i) の \(O(m)\) はこれ以上改善できません。

以上の計算量解析は、グラフを隣接リストで保持した場合についてです。グラフを隣接行列で保持すると、多重辺を除去できます。(i)-(iii) の \(i\) 回目のループでは 頂点数 \(O(n/2^i)\)、辺数 \(O(n^2/2^i)\) なので、計算量は \(O(\sum n^2/2^i)=O(n^2)\) となります。グラフが密な場合、隣接行列の方が高速です。

グラフが密になるまで隣接リストのブルーフカ法を行った後、隣接行列に切り替えることで計算量を最適化できます。\(O(\log(n^2/m))\) 回、(i)-(iii)のループを繰り返すと、頂点数は \(O(n/2^{\log(n^2/m)}) = O(m/n\) になります。ここから、隣接行列に切り替えると、\(O((m/n)^2)=O(m)\) 掛かり、全体では \(O(m\log(n^2/m))\) です。

あとの平面グラフの項で述べますが、基数ソートを利用すれば、\(O(m)\) 時間で多重辺の除去ができるので、隣接リストのみでこの計算量を達成できます。

アルゴリズムの正当性の証明

各頂点について、接続する重み最小の辺を採用してよいことを証明します。

証明:任意の頂点 \(v\) について、頂点 \(v\) に隣接する辺のうち、重み最小の辺 \(e_v\) を持つ最小全域木が存在することを示せば十分です。最小全域木 \(T\) を取ります。\(e_v \in T\) なら何も示すことはありません。\(e_v \not \in T\) と仮定します。\(T\) の基本閉路 \(C_{e_v}\) (\(T+e_v\) の閉路)には \(e_v\) 以外の \(v\) に接続した辺 \(e\) が含まれます。\(c(e_v) \leq c(e)\) より、\(T \leftarrow T-e+e_v\) も最小全域木です。この最小全域木は \(e_v\) を辺に持ちます。

平面グラフ: \(O(n)\)

平面グラフの場合、\(O(n)\) でブルーフカ法は終了します[1]。

一つ目のカギは、平面グラフの辺を縮約しても平面グラフであることです。平面グラフは縮約について閉じています。このことから、入力が平面グラフならば、ブルーフカ法の途中のグラフも常に平面グラフです。

二つ目のカギは二通りあります。

平面グラフの辺数を利用

一つ目の方法では平面グラフの辺の個数が \(O(n)\) であることを利用します。

定理:\(n \geq 3\) のとき、平面グラフの辺は高々 \(3n-6\) 個。
証明:辺の個数 \(m\) を上から抑えるには、辺極大な平面グラフを考えればよいです。辺極大な平面グラフの各面は3角形です。頂点数 \(n\)、面数 \(l\) のとき、オイラーの多面体定理より \(n-m+l=2\) です。各面が三角形であることから \(2l=3m\) です。多面体定理に代入して、\(m=3n-6\) を得ます。

\(i\) 回目の (i)-(iii) のループでは頂点の個数が \(O(n/2^i)\) ですから、辺の個数も平面性より \(O(n/2^i)\) となります。\(i\) について和を取って、\(O(n)\) が全体の計算量になります。

縮約で、多重辺が生じうることに注意してください。計算量を改善するには、多重辺を消去する必要があります。なぜなら \(m \leq 3n-6\) は多重辺・自己辺のない平面グラフについてだからです。多重辺を見つけるには、辺 \((u,v)\) を \(u+nv\) として基数 \(n\) の基数ソートすればよいです。基数 \(n\) で2桁の数のソートなので \(O(n)\) 時間です。多重辺が生じた際は、重みの大きい方を捨てます。

平面グラフの次数を利用

二つ目の方法では次数 12 以下の頂点が \(n/2\) 個以上あることを用います。

証明:平面グラフの辺の個数が \(3n-6\) 以下なので、次数の総和は \(\sum_v \mathrm{deg}(v) \leq 6n-12\) です。従って、\(n/2\) 個以上の頂点は次数 12 以上です。

ブルーフカ法の各ループ(i)-(iii)で次数 12 以下の頂点の辺のみを縮約することにします。すると、重み最小の辺はそれぞれ \(O(1)\) で見つかります。また、次数 12 以下の辺は \(n/2\) 個以上あるので、頂点数は \(3n/4\) 頂点以下になります。従って全体では \(O(\sum (3/4)^i n)=O(n)\) となります。

「次数12以下の頂点が \(n/2\) 個以上」は多重辺がない場合についてなので、多重辺を取り除く必要があることに注意してください。

プリム法と合体 : \(O(m\log\log(n))\)

フィボナッチヒープを用いたプリム法 \(O(m + n\log(n))\) と組み合わせて、\(O(m\log\log(n))\) にできます。\(O(\log\log(n))\) 回、ブルーフカ法の (i)-(iii) のループを行います。すると、頂点数が \(O(n/2^{\log\log(n)})=O(n/\log(n))\) 個になります。ここからプリム法に切り替えると、更に \(O(m+n)\) 掛かります。合計で \(O(m\log\log(n))\) です。\(m=o(n\log(n)/\log\log(n))\) のとき、プリム法・ブルーフカ法より高速です。

参考文献

  1. Mareš, Martin. Two linear time algorithms for MST on minor closed graph classes. ETH Zurich, 2002.
    • バケットソートで多重辺の除去が deterministic に線形でできるとあったのですが、分かりませんでした。更新:Misawaさんに教えてもらい理解できました。
  2. Problem Set no. 1 — Minimum spanning trees
      隣接行列と隣接リストを切り替えると計算量削減できるということが書いてあります
ブルーフカ法はソートを巧妙に避けてるところが、面白いと思うんですよね。更なる高速化への希望を持てて、実際未履修だけど、計算量最速のそれもブルーフカ法ベースらしいです。縮約パートがプリム法・クラスカル法と比べてやや面倒なので主流になるとは思えないのですが、観賞用としては好きです。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA