Componente connessa (teoria dei grafi)

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
Un grafo con tre componenti connesse.

Nella teoria dei grafi, una componente connessa (o semplicemente una componente) di un grafo indiretto è un sottografo in cui:

  • qualsiasi coppia di vertici è connessa da cammini
  • il sottografo non è connesso a nessun vertice addizionale del supergrafo.

Ad esempio, il grafo mostrato nell'illustrazione sulla destra ha tre componenti connesse. Un grafo che è esso stesso connesso ha esattamente una componente connessa, che consiste nell'intero grafo.

Componenti connesse a partire da classi di equivalenza[modifica | modifica wikitesto]

In modo analogo a quanto avviene con gli spazi topologici, un modo alternativo di definire le componenti connesse coinvolge le classi di equivalenza di una relazione di equivalenza definita sui vertici del grafo. In un grafo indiretto, un vertice v è detto raggiungibile da un vertice u se c'è un cammino da u a v. In questa definizione, per convenzione, un singolo vertice si conta come un cammino di lunghezza zero, e lo stesso vertice si può presentare più di una volta all'interno di un cammino. La raggiungibilità è una relazione di equivalenza, poiché:

  • È riflessiva: esiste un cammino banale di lunghezza zero da un qualsiasi vertice a sé stesso.
  • È simmetrica: se c'è un cammino da u a v, gli stessi spigoli formano un cammino da v a u.
  • È transitiva: se c'è un cammino da u a v, e un cammino da v a w, i due cammini possono essere concatenati insieme per formare un cammino da u a w. Le componenti connesse sono allora i sottografi indotti formati dalle classi di equivalenza di questa relazione.

Il numero di componenti connesse[modifica | modifica wikitesto]

Il numero di componenti connesse è un'importante invariante topologica di un grafo. Nella teoria topologica dei grafi può essere interpretato come lo zeresimo numero di Betti del grafo. Nella teoria algebrica dei grafi esso uguaglia la molteplicità di 0 come autovalore della matrice laplaciana del grafo. È anche l'indice del primo coefficiente diverso da zero del polinomio cromatico di un grafo. I numeri delle componenti connesse svolgono un ruolo chiave nel teorema di Tutte caratterizzando i grafi che hanno abbinamenti perfetti, e nella definizione della durezza dei grafi.

Algoritmi[modifica | modifica wikitesto]

È immediato calcolare le componenti connesse di un grafo nel tempo lineare (in termini dei numeri dei vertici e degli spigoli del grafo) usando o la ricerca in ampiezza o la ricerca in profondità. In entrambi i casi, una ricerca che comincia in qualche particolare vertice v troverà l'intera componente connessa contenente v (e non altro) prima di ritornare. Per trovare tutte le componenti connesse di un grafo, occorre scorrere attraverso i suoi vertici, iniziando una nuova ricerca in ampiezza o in profondità ogni volta che si raggiunge un vertice che non è già stato incluso in una componente connessa trovata in precedenza. Hopcroft e Tarjan (1973)[1] descrivono essentialmente questo algoritmo, e affermano che a questo punto era "ben conosciuto".

Ci sono anche algoritmi efficienti per tracciare dinamicamente le componenti connesse di un grafo quando si aggiungono i vertici e gli spigoli, come applicazione immediata di una struttura dati di insiemi disgiunti. Questi algoritmi richiedono un tempo O(α(n)) ammortizzato per ogni operazione, in cui aggiungere vertici e spigoli e determinare la componente connessa nella quale un vertice ricade sono entrambe operazioni, e α(n) è un inverso a crescita lenta della funzione di Ackermann a crescita rapidissima. Un problema correlato è tracciare le componenti connesse quando tutti gli spigoli sono cancellati da un grafo, uno per uno; esiste un algoritmo per risolvere questo con un tempo costante per ogni interrogazione, e un tempo O(|V||E|) per mantenere la struttura dati; questo comporta un costo ammortizzato di O(|V|) per ogni cancellazione di spigoli. Per le foreste, il costo può essere ridotto a O(q + |V| log |V|), o al costo ammortizzato O(log |V|) per ogni cancellazione di spigoli.[2]

I ricercatori hanno studiato anche algoritmi per trovare componenti connesse in modelli di computazione più limitati, come programmi in cui la memoria operativa è limitata a un numero logaritmico di bit (definito dalla classe di complessità L). Lewis & Papadimitriou (1982) chiesero se sia possibile verificare in uno spazio logaritmico se due vertici appartengano alla stessa componente connessa di un grafo indiretto, e definirono una classe di complessità SL di problemi equivalenti alla connettività in spazio logaritmico. Finalmente Reingold (2008) riuscì a trovare un algoritmo per risolvere questo problema di connettività in spazio logaritmico, dimostrando che L = SL.

Note[modifica | modifica wikitesto]

  1. ^ John Hopcroft e Robert Tarjan, Efficiente algorithms for graph manipulation, in Communication of the ACM, vol. 16, n. 6, giugno 1973, 372-378, DOI:10.1145/362248.362272.
  2. ^ Y. Shiloach e S. Even, "An On-Line Edge-Deletion Problem", Journal of the ACM, vol. 28, n° 1, gennaio 1981, pp. 1-4.

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica
Estratto da "https://it.wikipedia.org/w/index.php?title=Componente_connessa_(teoria_dei_grafi)&oldid=131412748"