グラフ 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