クリーク (clique)

あるグラフ H がグラフ G のクリークであるとは,H が完全グラフで G の部分グラフであること.

だが,さらに極大であることを条件に加える場合もある. H が極大であるとは,G の完全部分グラフ G' で,H を部分グラフとするものが存在しないこと.

最大のクリークに含まれるノード数を求める最大クリーク問題はNP完全であることはよく知られている.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:12:19 (2494d)