Топ-100
Indietro

ⓘ Componente connessa, teoria dei grafi. Nella teoria dei grafi, una componente connessa di un grafo indiretto è un sottografo in cui: il sottografo non è conness ..




Componente connessa (teoria dei grafi)
                                     

ⓘ Componente connessa (teoria dei grafi)

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

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

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

                                     

1. Componenti connesse a partire da classi di equivalenza

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

2. Il numero di componenti connesse

Il numero di componenti connesse è unimportante 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 lindice 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.

                                     

3. Algoritmi

È 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à lintera 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 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 Oq + |V| log |V|, o al costo ammortizzato Olog |V| per ogni cancellazione di spigoli.

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



                                     
  • Etichettamento di componenti connesse o labelling delle componenti connesse è un applicazione algoritmica della teoria dei grafi nella quale sottoinsiemi
  • studio, la teoria dei grafi costituisce un importante parte della combinatoria i grafi inoltre sono utilizzati in aree come topologia, teoria degli automi
  • Nella teoria dei grafi una contrazione dei grafi è un operazione che rimuove uno spigolo da un grafo mentre fonde simultaneamente i due vertici che connetteva
  • Nella teoria dei grafi un ponte conosciuto anche come bridge, cut - edge, cut arc o istmo è un arco la cui eliminazione aumenta il numero di componenti connesse
  • Nel campo matematico della teoria dei grafi il grafo nullo può riferirsi o al grafo di ordine - zero o, alternativamente, a qualunque grafo privo di ponti
  • usato nella teoria dei grafi per trovare le componenti fortemente connesse di un grafo. Un applicazione tipica dell algoritmo è la ricerca dei cicli. Ha
  • disciplina matematica della teoria dei grafi il teorema di Tutte, che prende nome da William Thomas Tutte, è una caratterizzazione dei grafi con accoppiamenti perfetti
  • Una componente fortemente connessa di un grafo diretto G è un sottografo massimale di G in cui esiste un cammino orientato tra ogni coppia di nodi ad esso
  • In teoria dei grafi un albero è un grafo non orientato nel quale due vertici qualsiasi sono connessi da uno e un solo cammino grafo non orientato, connesso
  • teoria dei grafi un grafo aleatorio è un grafo generato da un procedimento aleatorio, ovvero è una variabile aleatoria le cui realizzazioni sono dei grafi
  • Nella teoria dei grafi un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cricca più