Bron-Kerbosch algorithm
ブロン-カーボッシュ・アルゴリズムは、無向グラフのすべての最大クリークを見つけるための列挙アルゴリズムである。すなわち、列挙された部分集合の1つに含まれる頂点の各対が辺で接続されており、列挙された部分集合はその完全な接続性を保持したまま頂点を追加できないという2つの性質を持つ頂点の部分集合をすべて列挙する。ブロン-ケルボッシュ・アルゴリズムは、オランダの科学者コエンラード・ブロンとヨープ・ケルボッシュによって設計され、1973年に発表された。
クリークとはなにか
クリークがわかりにくいので、以下のリンクを読み解く。
無向グラフ\(G(\text{V, E})\)(\(\text{V}\): vertex, \(\text{E}\): Edge)は方向性のないグラフである。下のグラフを見ると、例えば6から4、4から6は向きを考慮しない。これを無向グラフという。頂点の部分集合\(\text{C} \subseteq \text{V}\)を考える。\(\text{C}\)に属するあらゆる\(2\)つの頂点をつなぐ辺が存在するとき、この頂点の集合をクリークという。下のグラフでは、\(1, 2, 5\)という頂点の部分集合を考えると、これはあらゆる\(2\)つの頂点が接続されており、クリークである。また、この頂点の数をクリークの大きさという。この場合の大きさは\(3\)である。
下の図は、\(5\)つの点がすべて互いに接続されており、大きさ\(5\)のクリーク（完全グラフ）である。
ピボットなしの場合
ブロン-カーボッシュ・アルゴリズムの基本形は、与えられたグラフ\(G\)の全ての最大クリークを探索する再帰的バックトラック・アルゴリズムである。より一般的には、頂点\(\text{R、P、X}\)の3つの不連続な集合が与えられたとき、\(\text{R}\)のすべての頂点、\(\text{P}\)のいくつかの頂点、\(\text{X}\)のどの頂点も含まないクリークを見つける。各アルゴリズムの呼び出しにおいて、\(\text{P}\)と\(\text{X}\)は、\(\text{R}\)に追加されたときにクリークを形成する頂点で構成される不連続な集合である。言い換えれば、\(\text{P}\cup\text{X}\)は\(\text{R}\)の各要素に結合する頂点の集合である。\(\text{P}\)と\(\text{X}\)の両方が空のとき、\(\text{R}\)に追加できる要素はないので、\(\text{R}\)は最大(maximal)クリークであり、アルゴリズムは\(\text{R}\)を出力する。
再帰は、\(\text{R}\)と\(\text{X}\)を空集合、\(\text{P}\)をグラフの頂点集合とすることで開始される。そのような頂点がない場合、\(\text{R}\)を最大クリークとして報告するか（\(\text{X}\)が空の場合）、バックトラックする。\(\text{P}\)から選択された各頂点\(v\)について、\(v\)が\(\text{R}\)に追加され、\(\text{P}\)と\(\text{X}\)が\(v\)の近傍集合\(N(v)\)に制限される再帰的な呼び出しを行う。次に、\(v\)を\(\text{P}\)から\(\text{X}\)に移動させ、将来のクリークから除外し、\(\text{P}\)の次の頂点に進む。
以下は、上記をPythonのコードで表現したものである。
def BronKerbosch(P, R = None, X = None): #find cliques in graph (Bron-Kerbosch Algorithm)
P = set(P)
R = set() if R is None else R
X = set() if X is None else X
if not P and not X:
yield R
while P:
v = P.pop()
yield from BronKerbosch(
P = P.intersection(g[v]), R = R.union([v]), X = X.intersection(g[v]))
X.add(v)ピボットありの場合
上述のアルゴリズムの基本形は、多数の非最大クリークを持つグラフの場合には非効率的である（これは、最大かどうかにかかわらず、すべてのクリークに対して再帰的な呼び出しを行う）。BronとKerboschは、時間を節約し、アルゴリズムが最大クリークを含まない探索の枝をより迅速にバックトラックできるようにするために、\(\text{P}\)から（あるいは、より一般的には、後の研究者が気づいたように、\(\text{P} \cup \text{X}\)から選択される「ピボット頂点」\(u\)を含むアルゴリズムの変形を導入した。その場合、そのピボット要素の近傍要素は再帰的にテストされない。\(u\)の近傍探索で見つかる可能性のある最大クリークは、\(u\)またはその非近傍探索でも見つかる。そうでなければ、\(u\)の近傍だけがその最大クリークに含まれることになり、\(u\)を加えてクリークを増やすことができるが、これはそのクリークが最大であることと矛盾する。したがって、\(u\)とその非隣接のみが、アルゴリズムの各再帰呼び出しでRに追加される頂点\(v\)の選択肢としてテストされる必要がある。以下はそのPythonコードである。
def BronKerboschWithPivot(P, R=None, X=None, g=None):
P = set(P)
R = set() if R is None else R
X = set() if X is None else X
if not P and not X:
yield R
if P or X:
u = next(iter(P.union(X)), None)
if u is None:
return
for v in P.difference(g[u]):
yield from BronKerboschWithPivot(P.intersection(g[v]), R.union({v}), X.intersection(g[v]), g)
P.remove(v)
X.add(v)アルゴリズムが行う再帰呼び出しの回数を最小化するようにピボットを選択した場合、ピボットを使用しないバージョンのアルゴリズムと比較して、実行時間を大幅に短縮することができる。
具体例
上の無向グラフを再度利用する。グラフの例では、最初に\(\text{R} = \emptyset, \text{P} = \{1,2,3,4,5,6\}, \text{X} = \emptyset\)でアルゴリズムが呼び出される。ピボット\(u\)は、再帰呼び出しの回数を最小にするために、次数\(3\)の頂点の1つとして選ぶべきである。例えば、\(u\)が頂点\(2\)に選ばれたとする。そうすると、\(P(u)\backslash N(v)\)には頂点\(2, 4, 6\)の\(3\)つの頂点が残る。
\(v = 2\)に対するアルゴリズムの内部ループの反復は、\(\text{R} = \{2\}, \text{P} = \{1,3,5\}, X = \emptyset\)でアルゴリズムを再帰的に呼び出す。この再帰呼び出しの中で、\(1\)か\(5\)のどちらかがピボットとして選ばれ、頂点\(3\)に対して\(1\)回、ピボットとして選ばれなかった方の頂点に対してもう\(1\)回、第2レベルの再帰呼び出しが行われる。これらの\(2\)つの呼び出しは、最終的に\(2\)つのクリ ーク\(\{1,2,5\}\)と\(\{2,3\}\)を報告する。これらの再帰呼び出しから戻ると、頂点\(2\)が\(\text{X}\)に追加され、\(\text{P}\)から削除される。
\(v = 4\)に対するアルゴリズムの内部ループの反復は、\(\text{R} = \{4\}, \text{P} = \{3,5,6\}, \text{X} = \emptyset\)のアルゴリズムを再帰的に呼び出す（頂点\(2\)はアルゴリズムの外側呼び出しで集合\(\text{X}\)に属するが、それは\(v\)の近傍ではなく、再帰呼び出しに渡される\(\text{X}\)のサブセットから除外される）。この再帰呼び出しは、3つのクリーク\(\{3,4\}, \{4,5\}, \{4,6\}\)を報告するアルゴリズムに\(3\)つの第\(2\)レベルの再帰呼び出しを行うことになる。そして、頂点\(4\)が\(\text{X}\)に追加され、\(\text{P}\)から削除される。
アルゴリズムの内部ループの\(3\)回目の最後の反復では、\(v = 6\)に対して、\(R = \{6\}, P = \emptyset, X = \{4\}\)でアルゴリズムが再帰的に呼び出される。この再帰呼び出しは\(\text{P}\)が空で\(\text{X}\)が空でないため、頂点\(6\)を含み頂点\(4\)を除く最大閥は存在し得ないので、それ以上のクリークを報告することなく直ちにバックトラックする。
Pythonでこれを実行してみる。
# 集合の作成
g = collections.defaultdict(set)
g[1].update({2, 5})
g[2].update({1, 3, 5})
g[3].update({2, 4})
g[4].update({3, 5, 6})
g[5].update({1, 2, 4})
g[6].update({4})
# Pの設定
P = set(g.keys())
# 結果の取り出し
result = BronKerbosch(P, R = None, X = None)
result = sorted((i for i in BronKerbosch(P, R = None, X = None)), key = lambda x: x)
print(len(result[0]))関連問題
Project Eulerの上記の問題が、このアルゴリズムを適応して解決することができる。
コメント