無向グラフが与えられたとき、最大位数の完全部分グラフを求める問題 最大クリーク問題 無向グラフが与えられたとき、最大位数の完全部分グラフを求める問題
最大クリーク問題とは？ 無向グラフG＝（V,E)が与えられたとき、ノード（点）の部分集合C（⊆V）は、Cによって導かれた部分グラフが完全なときクリークと呼ばれる（完全グラフとは、すべてのノードの間にアークがあるグラフである）。クリークに含まれるノードの数｜C｜が最大になるクリークを求めよ。
アルゴリズム 評価値（Ｓ）＝Ｓに含まれるアークの数 １）適当なノードの部分集合Sからはじめる。 ２）以下の操作を時間が尽きるまで繰り返す。 ａ）Ｓによって導かれたグラフが完全ならば、Ｓに含まれないノードｉで評価値（Ｓ∪{ｉ}）が最大のものをＳに加える。このとき、追加したノードはしばらく削除しないように設定する。 ｂ）Ｓによって導かれたグラフが完全でないならば、Ｓに含まれるノードｉで評価値（Ｓ-{ｉ}）が最大のものをＳから除く。このとき、削除したノードはしばらく追加しないように設定する。
2 2 2 2
3 1 3 3 4 1 3 しばらく削除しない
2 1 1 2 1 1
3 4 1 2 4 1
3 2 2 2