Cricca in un grafo
Nella teoria dei grafi una cricca (o clique) è un sottoinsieme di vertici adiacenti del grafo non orientato.
In altre parole, una cricca in un grafo è un insieme di vertici che formano un sottografo completo, ossia un sottografo in cui ogni possibile coppia di vertici è direttamente connessa da un arco (vertici adiacenti).
Esempio
Facciamo un esempio pratico con un grafo semplice per spiegare il concetto di clique, clique massimale e clique massimo.
Immaginiamo di avere un grafo con 5 vertici denominati A, B, C, D, e E, con i seguenti archi:
Guardando il grafo, possiamo identificare diversi clique.
Ad esempio, il sottoinsieme {A, B, C} forma una clique perché ogni vertice è connesso direttamente con tutti gli altri nel sottoinsieme.
Un grafo può essere composto da più clique di diversa cardinalità.
Ad esempio, nel grafo precedente il sottoinsieme {A, C, D} è un altro esempio di clique.
In generale ogni coppia di vertici adiacenti forma una clique minimale. Se presi a due a due, i vertici adiacenti soddisfano le proprietà di una cricca. Ad esempio, i vertici adiacenti {E,B} formano una cricca.
Allo stesso modo tutti gli altri vertici adiacenti presi a due a due come {A,B}, {A,C}, {A,D}, {B,C}, {C,D}.
Viceversa, l'inseme di vertici {A,B,C,D} non forma una cricca perché non sono tutti vertici adiacenti, i vertici B e D non sono direttamente connessi.
Una clique si dice clique massimale se non può essere estesa includendo un altro vertice adiacente a tutti i vertici della clique.
Ciò significa che aggiungendo qualsiasi altro vertice esterno alla clique, almeno una delle connessioni mancherà. In altre parole, la clique non è contenuta in una clique di dimensione maggiore.
Ad esempio, prendendo la clique {A, B, C}, notiamo che aggiungendo qualsiasi altro vertice (come D o E) romperemmo la proprietà che ogni vertice è connesso con tutti gli altri nel sottoinsieme, quindi {A, B, C} è un esempio di clique massimale.
Similmente, {A, C, D} è un altro clique massimale.
Enumerare tutti le clique massimali in un grafo è un problema che può avere una complessità esponenziale, poiché il numero delle clique può crescere esponenzialmente con la dimensione del grafo.
Una clique si dice clique massima se ha la dimensione più grande possibile rispetto a tutte le altre clique del grafo.
Questo significa che non esiste un'altra clique nel grafo che contenga più vertici del clique massimo.
Ad esempio, tra i clique massimali trovati, {A, B, C} e {A, C, D} sono i più grandi possibili in questo grafo, entrambi con 3 vertici. Non esiste un clique con più di 3 vertici in questo grafo, quindi sia {A, B, C} che {A, C, D} sono anche clique massime in questo contesto.
Quest'ultimo parametro è particolarmente significativo per valutare la coesività di una rete, poiché riflette la massima estensione di connettività stretta tra i suoi nodi.
Il problema di trovare una clique massima è un problema notoriamente difficile dal punto di vista computazionale ed è classificato come NP-completo. il che significa che non si conosce un algoritmo che lo risolva in tempo polinomiale per tutti i casi.
In un grafo le clique e gli insiemi indipendenti sono concetti intrinsecamente collegati.
In particolare, ogni clique presente in un grafo si trasforma in un insieme indipendente all'interno del suo grafo complementare, e analogamente, ogni insieme indipendente nel grafo originale diventa una clique nel complemento.
Ad esempio, la clique formata dai vertici {A,B,C} diventa un insieme indipendente nel complemento del grafo.
Questa relazione simmetrica evidenzia un legame profondo tra coesione e indipendenza strutturale nei grafi, sottolineando come la configurazione delle connessioni in un grafo determini dinamiche opposte nel suo complementare.
Le applicazioni delle clique
Identificare le clique in una rete può aiutare a comprendere la struttura e la dinamica di sistemi complessi, come le reti di comunicazione o le reti di collaborazione scientifica.
Le clique possono essere utilizzate anche per identificare gruppi di utenti strettamente connessi all'interno di reti sociali.
La loro analisi contribuisce alla comprensione delle proprietà strutturali dei grafi e delle reti.
