Cricca (teoria dei grafi)

In teoria dei grafi, una cricca (o clique) è un insieme V di vertici in un grafo non orientato G, tale che, per ogni coppia di vertici in V, esiste un arco che li collega. In modo equivalente, si potrebbe dire che il sottografo indotto da V è un grafo completo. La dimensione di una cricca è definita come il numero di vertici che contiene. Alcuni autori chiamano cricca ogni sottografo completo che sia di dimensione massima^[1].

Il problema di trovare, se esiste, una cricca di una dimensione fissata all'interno di un grafo è detto problema della cricca, ed è NP-completo.

Il concetto complementare a quello di cricca è l'insieme indipendente, nel senso che a ogni cricca corrisponde un insieme indipendente nel grafo complemento.

Sebbene lo studio dei sottografi completi risalga almeno alla riformulazione della teoria dei grafi con la teoria di Ramsey da parte di Erdős & Szekeres (1935),^[2] il termine "cricca" viene da Luce & Perry (1949), che utilizzarono sottografi completi nelle reti sociali per modellare le cricche (in inglese cliques) di persone, vale a dire gruppi ristretti di persone che si conoscono tutte fra di loro. Le cricche hanno molte applicazioni nelle scienze e particolarmente in bioinformatica.

Una cricca in un grafo indiretto G = (V, E) è un sottoinsieme dell'insieme dei vertici C ⊆ V, tale che per ogni due vertici in C, esiste uno spigolo che li connette. Questo equivale a dire che il sottografo indotto da C è completo (in alcuni casi, il termine cricca si può anche riferire al sottografo).

Una cricca massimale è una cricca che non può essere estesa includendo un altro vertice adiacente, cioè una cricca che non esiste esclusivamente dentro l'insieme dei vertici di una cricca più grande.

Una cricca massima è una cricca della dimensione più grande possibile in un dato grafo. Il numero di cricca ω(G) di un grafo G è il numero di vertici in una cricca massima in G. Il numero d'intersezione di G è il più piccolo numero di cricche che insieme coprono tutti gli spigoli di G.

L'opposto di una cricca è un insieme indipendente, nel senso che ogni cricca corrisponde a un insieme indipendente nel grafo complemento. Il problema di copertura delle cricche riguarda il trovare quante più cricche possibile che includano ogni vertice nel grafo. Un concetto correlato è una bicricca (biclique in inglese), un sottografo bipartito completo. La dimensione bipartita di un grafo è il numero minimo di bicricche necessario per coprire tutti gli spigoli del grafo.

I risultati matematici concernenti le cricche comprendono i seguenti.

• Il teorema di Turán (1941) dà un limite inferiore alla dimensione di una cricca nei grafi densi. Se un grafo ha un numero sufficientemente alto di spigoli, deve contenere una grande cricca. Ad esempio, ogni grafo con ${\displaystyle n}$ vertici e più di ${\displaystyle \scriptstyle \lfloor {\frac {n}{2}}\rfloor \cdot \lceil {\frac {n}{2}}\rceil }$ spigoli deve contenere una cricca con tre vertici.
• Il teorema di Ramsey Graham, Rothschild & Spencer (1990) afferma che ogni grafo o il suo grafo complemento contiene una cricca con almeno un numero logaritmico di vertici.
• Secondo un risultato di Moon & Moser (1965), un grafo con 3n vertici può avere al massimo 3ⁿ cricche massimali. I grafi che incontrano questo limite sono i grafi di Moon–Moser K_3,3,..., un caso speciale dei grafi di Turán che emergono come i casi estremali del teorema di Turán.
• La congettura di Hadwiger, ancora non dimostrata, collega la dimensione della più grande cricca di un minore in un grafo (il suo numero di Hadwiger) al suo numero cromatico.
• La congettura di Erdős–Faber–Lovász è un'altra affermazione non dimostrata che collega la colorazione dei grafi alle cricche.

Varie importanti classi di grafi possono essere definiti dalle loro cricche:

• Un grafo cordale è un grafo i cui vertici possono essere ordinati in un perfetto ordinamento di eliminazione, un ordinamento tale che i vicini di ciascun vertice v che vengono dopo v nell'ordinamento formano una cricca.
• Un cografo è un grafo i cui sottografi indotti hanno tutti la proprietà che qualsiasi cricca massimale interseca qualsiasi insieme indipendente massimale in un unico vertice.
• Un grafo d'intervallo è un grafo le cui cricche massimali possono essere ordinate in modo tale che, per ciascun vertice v, le cricche contenenti v sono consecutive nell'ordinamento.
• Un grafo di linea è un grafo i cui spigoli possono essere coperti da cricche con gli spigoli disgiunti in modo tale che ogni vertice appartiene esattamente a due delle cricche nella copertura.
• Un grafo perfetto è un grafo nel quale il numero di cricca equivale al numero cromatico in ogni sottografo indotto.
• Un grafo diviso è un grafo nel quale alcune cricche contengono almeno un estremo di ogni spigolo.
• Un grafo senza triangoli è un grafo che non ha cricche distinte dai suoi vertici e dai suoi spigoli.

In aggiunta, molte altre costruzioni matematiche coinvolgono le cricche dei grafi. Tra di esse:

• Il complesso delle cricche di un grafo G è un complesso simpliciale astratto X(G) cvon un simplesso per ogni cricca in G
• Un grafo semplice è un grafo indiretto κ(G) con un vertice per ogni cricca in un grafo G e uno spigolo che connette due cricche che differiscono per un singolo vertice. È un esempio di grafo mediano, ed è associato a un'algebra mediana sulle cricche di un grafo: la mediana m(A,B,C) di tre cricche A, B e C è la cricca i cui vertici appartengono ad almeno due delle cricche A, B e C.^[3]
• La somma delle cricche è un metodo per combinare due grafi fondendoli lungo una cricca condivisa.
• L'ampiezza di cricca è una nozione della complessità di un grafo in termini del numero minimo di distinte etichette dei vertici necessarie per costruire il grafo a partire dalle unioni disgiunte, dalle operazioni di rietichettamento e dalle operazioni che connettono tutte le coppie di vertici con etichette date. I grafi con ampiezza di cricca uno sono esattamente le unioni disgiunte delle cricche.
• Il numero d'intersezione di un grafo è il numero minimo di cricche necessarie per coprire tutti gli spigoli del grafo.

Concetti strettamente correlati ai sottografi completi sono le suddivisioni dei grafi completi e dei minori completi dei grafi. In particolare, il teorema di Kuratowski e il teorema di Wagner caratterizzano i grafi planari rispettivamente mediante le suddivisioni e i minori completi proibiti e bipartiti completi.

Lo stesso argomento in dettaglio: Problema della cricca.

In informatica, il problema della cricca è il problema computazionale di trovare una cricca massima, o tutte le cricche, in un dato grafo. È NP-completo, uno dei 21 problemi NP-completi di Karp (M. Richard Karp, 1972). È anche intrattabile con parametri fissi, e difficile da approssimare. Nondimeno, sono stati sviluppati molti algoritmi per computare le cricche, o funzionanti in tempo esponenziale (come l'algoritmo di Bron-Kerbosch) o specializzati in famiglie di grafi come i grafi planari o grafi perfetti per i quali il problema possa essere risolto in tempo polinomiale.

La parola "cricca", nel suo uso nella teoria dei grafi, emerse dal lavoro di Luce & Perry (1949), che utilizzarono sottografi per modellare le cricche (gruppi di persone che si conoscono tutte fra di loro) nelle reti sociali. Per la continuazione dei tentativi di modellare le cricche sociali dal punto di vista della teoria dei grafi, vedi ad es. Alba (1973), Peay (1974), e Doreian & Woodard (1994).

Molti diversi problemi di bioinformatica sono stati modellati usando le cricche. Ad esempio, Ben-Dor, Shamir & Yakhini (1999) modellano il problema di raggruppare i dati sull'espressione genica come quello di trovare il numero minimo di cambiamenti necessari per trasformare un grafo che descrive i dati in un grafo formato come l'unione disgiunta delle cricche; Tanay, Sharan & Shamir (2002) discutono un problema simile di biraggruppamento per dati sull'espressione in cui si richiede che i gruppi siano cricche. Sugihara (1984) usa le cricche per modellare le nicchie ecologiche nelle reti alimentari. Sankoff descrive il problema di inferire gli alberi evolutivi come quello di trovare le massime cricche in un grafo che ha come suoi vertici le caratteristiche della specie, dove due vertici condividono uno spigolo se esiste una perfetta filogenia che combina quei due caratteri. Samudrala & Moult (1998) modellano la predizione di struttura proteica come un problema di trovare le cricche in un grafo i cui vertici rappresentano posizioni di sottounità nella proteina. E cercando le cricche in una rete d'interazione proteina-proteina, Spiron & Mirny (2003) trovarono raggruppamenti di proteine che interagiscono strettamente tra loro e hanno poche interazioni con le proteine al di fuori del raggruppamento. L'analisi dei grafi di potenza è un metodo per semplificare le reti biologiche complesse trovando le cricche e le strutture relative in queste reti.

In ingegneria elettrica, Prihar (1956) usa le cricche per analizzare le reti di comunicazione, e Paull, 1959 le usano per progettare circuiti efficienti per computare funzioni booleane parzialmente specificate. Le cricche sono state usate anche nella generazione di programmi di prova automatici: una grande cricca in un grafo d'incompatibilità di possibili guasti fornisce un limite inferiore sulla dimensione di un insieme di prove.^[5] Cong1993, Cong & Smith (1993) descrivono un'applicazione delle cricche per trovare una partizione gerarchica di un circuito elettronico in sottounità più piccole.

In chimica, Rhodes, Willett, Calvet & Dunbar (2003) usano le cricche per descrivere le sostanze chimiche in una base di dati chimica che hanno un alto grado di similarità con una struttura bersaglio. Kuhl, Crippen & Friesen (1983) usano le cricche per modellare le posizioni in cui due sostanze chimiche si legheranno l'una all'altra.

• Problema della cricca
• Insieme indipendente (teoria dei grafi)

• (EN) Eric W. Weisstein, Cricca, su MathWorld, Wolfram Research.

Portale Informatica

Portale Matematica