無向グラフが与えられたとき、最大位数の完全部分グラフを求める問題

無向グラフが与えられたとき、最大位数の完全部分グラフを求める問題
最大クリーク問題無向グラフが与えられたとき、最大位数の完全部分グラフを求める問題

最大クリーク問題とは？無向グラフG＝（V,E)が与えられたとき、ノード（点）の部分集合C（⊆V）は、Cによって導かれた部分グラフが完全なときクリークと呼ばれる（完全グラフとは、すべてのノードの間にアークがあるグラフである）。クリークに含まれるノードの数｜C｜が最大になるクリークを求めよ。

アルゴリズム評価値（Ｓ）＝Ｓに含まれるアークの数１）適当なノードの部分集合Sからはじめる。２）以下の操作を時間が尽きるまで繰り返す。
　ａ）Ｓによって導かれたグラフが完全ならば、Ｓに含まれないノードｉで評価値（Ｓ∪{ｉ}）が最大のものをＳに加える。このとき、追加したノードはしばらく削除しないように設定する。　ｂ）Ｓによって導かれたグラフが完全でないならば、Ｓに含まれるノードｉで評価値（Ｓ-{ｉ}）が最大のものをＳから除く。このとき、削除したノードはしばらく追加しないように設定する。