DAA-マックスクリーク

無向グラフでは、 clique与えられたグラフの完全なサブグラフです。完全なサブグラフとは、このサブグラフのすべての頂点がこのサブグラフの他のすべての頂点に接続されていることを意味します。

最大クリーク問題は、グラフの最大クリークを見つける計算上の問題です。マックスクリークは、多くの現実の問題で使用されています。

頂点が人々のプロファイルを表し、エッジがグラフ内の相互の知人を表すソーシャルネットワーキングアプリケーションについて考えてみましょう。このグラフでは、クリークはすべてがお互いを知っている人々のサブセットを表しています。

最大クリークを見つけるには、すべてのサブセットを体系的に検査できますが、この種のブルートフォース検索は、数十を超える頂点で構成されるネットワークには時間がかかりすぎます。

Algorithm: Max-Clique (G, n, k) 
S := Φ 
for i = 1 to k do 
   t := choice (1…n)  
   if t Є S then 
      return failure 
   S := S ∪ t  
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do 
   if (i, j) is not a edge of the graph then  
      return failure 
return success