極大2部クリーク

グラフ $G = (V = V_1 \cup V_2, A)$ の任意の枝が$V_1$と$V_2$の頂点を結ぶ枝であるとき，$G$は2部グラフとよばれる．$G$の頂点部分集合 $H\subseteq V_1$, $K\subseteq V_2$ に対して，$H$の任意の頂点と$K$の任意の頂点の間に枝があるとき，$H$と$K$を合わせた頂点集合を2部クリークとよぶ．$K=\emptyset$, $H=V_1$ である場合，あるいはその逆である場合も2部クリークである．ある2部クリークが他の2部クリークに含まれないとき，その2部クリークを極大2部クリークとよぶ (via 宇野 毅明, 有村 博紀, 浅井 達哉, 極大2部クリークの高速列挙法とデータマイニングへの応用, 夏のLAシンポジウム, 2003年7月)

(v0,v1,v2,v5,v6), (v2,v5,v6,v8), (v2,v3,v8), (v3,v7,v8,v9), (v3,v4,v9)がそれぞれ極大2部クリーク．

program codesよりLCM ver. 5.3をダウンロード．使い方はlcm readmeに．ここでは極大2部クリークの計算だけ利用する．以下上図の例．各行は各ノードの隣接リスト．たとえばノード0には5,6へのエッジがあることを示す．

% cat input
% ./lcm53/lcm CI input 1 output
5 6
5 6
5 6 8
7 8 9
9

結果は以下．最初の2行はHが空集合の場合か．これら以降をみると「6,5」と「0,1,2」などが極大2部クリークになっていることがわかる．

% cat output

 0 1 2 3 4
6 5
 0 1 2
9
 3 4
8
 2 3
8 6 5
 2
7 9 8
 3