Топ-100
Indietro

ⓘ Cricca, teoria dei grafi. In teoria dei grafi, una cricca è un insieme V di vertici in un grafo non orientato G, tale che, per ogni coppia di vertici in V, esis ..




Cricca (teoria dei grafi)
                                     

ⓘ Cricca (teoria dei grafi)

In teoria dei grafi, una cricca è 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.

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

Il concetto complementare a quello di cricca è linsieme 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, 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.

                                     

1. Definizioni

Una cricca in un grafo indiretto G = V, E è un sottoinsieme dellinsieme 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 linsieme 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 dintersezione di G è il più piccolo numero di cricche che insieme coprono tutti gli spigoli di G.

Lopposto 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.

                                     

2. Matematica

I risultati matematici concernenti le cricche comprendono i seguenti.

  • 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 è unaltra affermazione non dimostrata che collega la colorazione dei grafi alle cricche.
  • 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.
  • 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 n {\displaystyle n} vertici e più di ⌊ n 2 ⌋ ⋅ ⌈ n 2 ⌉ {\displaystyle \scriptstyle \lfloor {\frac {n}{2}}\rfloor \cdot \lceil {\frac {n}{2}}\rceil } spigoli deve contenere una cricca con tre vertici.
  • Secondo un risultato di Moon & Moser 1965, un grafo con 3 n vertici può avere al massimo 3 n 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.

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

  • 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 senza triangoli è un grafo che non ha cricche distinte dai suoi vertici e dai suoi spigoli.
  • 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 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 nellordinamento formano una cricca.
  • Un grafo dintervallo è un grafo le cui cricche massimali possono essere ordinate in modo tale che, per ciascun vertice v, le cricche contenenti v sono consecutive nellordinamento.
  • Un grafo diviso è un grafo nel quale alcune cricche contengono almeno un estremo di ogni spigolo.

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

  • La somma delle cricche è un metodo per combinare due grafi fondendoli lungo una cricca condivisa.
  • Il numero dintersezione di un grafo è il numero minimo di cricche necessarie per coprire tutti gli spigoli del grafo.
  • Il complesso delle cricche di un grafo G è un complesso simpliciale astratto X G cvon un simplesso per ogni cricca in G
  • Lampiezza 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.
  • 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 unalgebra 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.

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.

                                     

3. Informatica

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 lalgoritmo 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.

                                     

4. Applicazioni

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 sullespressione genica come quello di trovare il numero minimo di cambiamenti necessari per trasformare per trasformare un grafo che descrive i dati in un grafo formato come lunione disgiunta delle cricche; Tanay, Sharan & Shamir 2002 discutono un problema simile di biraggruppamento per dati sullespressione 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 dinterazione 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. Lanalisi dei grafi di potenza è un metodo per semplificare le reti biologiche complesse trovando le cricche 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 dincompatibilità di possibili guasti fornisce un limite inferiore sulla dimensione di un insieme di prove. Cong1993, Cong & Smith 1993 descrivono unapplicazione 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 luna allaltra.



                                     
  • il problema della cricca si riferisce a uno qualsiasi dei problemi legati alla ricerca di particolari sottografi completi cricche in un grafo, cioè
  • l insieme dei nodi connessi. Un albero è una foresta connessa. Può essere definito anche come un grafo connesso ed aciclico. Oppure: nella teoria dei grafi un
  • Clique - serie televisiva britannica del 2017 Clique - singolo di artisti vari del 2012 Clique - cricca in teoria dei grafi Clic Click The Clique
  • Nella teoria dei grafi un insieme indipendente o insieme stabile è un insieme di vertici in un grafo, nessuno dei quali è adiacente a due a due. Cioè
  • Nella teoria dei grafi la colorazione dei grafi è un caso speciale di etichettamento dei grafi è un assegnazione di etichette, tradizionalmente chiamate
  • Nella teoria dei grafi un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cricca più
  • insiemi indipendenti di vertici nella teoria dei grafi vedi Insieme indipendente teoria dei grafi Nella teoria dei grafi un insieme indipendente massimale
  • 1978. Wagner è noto per i suoi contributi alla teoria dei grafi e in particolare alla teoria dei grafi minori, che possono essere derivati da un grafo
  • verifica se ciascuna delle cricche risultanti è massimale. La cricca massimale più grande è una cricca massima e, poiché i grafi cordali sono perfetti, la
  • Nella teoria della complessità computazionale, trovare una copertura delle cricche minima è un problema NP - completo di teoria dei grafi Il probalma era