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.