DAA - Max Cliques

In un grafo non orientato, a cliqueè un sottografo completo del grafico dato. Il sottografo completo significa che tutti i vertici di questo sottografo sono collegati a tutti gli altri vertici di questo sottografo.

Il problema Max-Clique è il problema computazionale di trovare la massima clique del grafico. Max clique viene utilizzato in molti problemi del mondo reale.

Consideriamo un'applicazione di social networking, in cui i vertici rappresentano il profilo delle persone e i bordi rappresentano la conoscenza reciproca in un grafico. In questo grafico, una cricca rappresenta un sottoinsieme di persone che si conoscono tutte.

Per trovare una cricca massima, è possibile ispezionare sistematicamente tutti i sottoinsiemi, ma questo tipo di ricerca a forza bruta richiede troppo tempo per le reti che comprendono più di poche dozzine di vertici.

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

Analisi

Il problema di Max-Clique è un algoritmo non deterministico. In questo algoritmo, proviamo prima a determinare un insieme dik vertici distinti e quindi proviamo a verificare se questi vertici formano un grafo completo.

Non esiste un algoritmo deterministico temporale polinomiale per risolvere questo problema. Questo problema è NP-Complete.

Esempio

Dai un'occhiata al grafico seguente. Qui, il sottografo contenente i vertici 2, 3, 4 e 6 forma un grafo completo. Quindi, questo sottografo è un fileclique. Poiché questo è il sottografo completo massimo del grafico fornito, è un file4-Clique.