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