Топ-100
Indietro

ⓘ Componente fortemente connessa. Una componente fortemente connessa di un grafo diretto G è un sottografo massimale di G in cui esiste un cammino orientato tra o ..




                                     

ⓘ Componente fortemente connessa

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

Le componenti fortemente connesse formano una partizione di G poiché un nodo non può trovarsi contemporaneamente in due componenti fortemente connesse, di conseguenza un grafo diretto è fortemente connesso se e solo se ha una sola componente connessa.

Due vertici di G sono fortemente connessi se e solo se fanno parte dello stesso ciclo orientato.

                                     

1.1. Algoritmi per il calcolo delle componenti fortemente connesse Algoritmo di Tarjan

Lalgoritmo di Tarjan per le componenti fortemente connesse è uno degli algoritmi più efficienti per effettuare la ricerca delle strutture fortemente connesse in un grafo. Opera infatti a complessità lineare al numero degli archi e dei vertici O|V|+|E|.

                                     

1.2. Algoritmi per il calcolo delle componenti fortemente connesse Algoritmo di Kosaraju

Lalgoritmo di Kosaraju-Sharir consiste nelleseguire una visita in profondità del grafo e una successiva visita in profondità del grafo trasposto, in cui gli archi sono invertiti, scegliendo i nodi nellordine di fine visita ottenuto durante la prima visita in profondità. In tal modo si riesce a identificare le componenti fortemente connesse del grafo in tempo ΘV+E. Risulta quindi più semplice da implementare ma meno efficiente dellalgoritmo di Tarjan e di quello di Gabow che effettuano una sola visita in profondità del grafo.

                                     

1.3. Algoritmi per il calcolo delle componenti fortemente connesse Algoritmo di Gabow

Lalgoritmo di Cheriyan–Mehlhorn/Gabow consiste nelleseguire una sola ricerca in profondità sul grafo, utilizzando uno stack per tenere traccia dei vertici che non sono ancora stati assegnati ad una componente. Come lalgoritmo di Tarjan viene effettuata una sola ricerca in profondità.

                                     
  • una componente fortemente connessa Il punto centrale dell algoritmo consiste nel determinare se un nodo è la radice di una componente fortemente connessa
  • Componente elettrico Componente lineare Componente passivo Componenti di un vettore Componente fortemente connessa Componente COTS Altri progetti Wikizionario
  • pages, DOI: 10.1145 1391289.1391291. Componente fortemente connessa un concetto correlato per i grafi diretti Componente biconnessa Scomposizione modulare
  • se nessun letterale e la sua negazione derivano dalla stessa componente fortemente connessa del grafo associato questo metodo è utilizzato per risolvere
  • grafo aciclico diretto contraendo tutti i vertici in ciascuna componente fortemente connessa Se la relazione descritta dal grafo è transitiva, nessuna informazione
  • Il varistore è un componente elettronico che serve a proteggere gli altri componenti di un dispositivo elettronico da fenomeni transitori di sovratensione
  • secrezione clorico - peptidica A questa secrezione viene aggiunta una componente acquosa nel canalicolo di secrezione esterno - breve tratto tra le pareti
  • effettuate su di esso. Un esempio è l algoritmo di Kosaraju per le componenti fortemente connesse che applica una ricerca in profondità due volte, una sul dato
  • nube è suddivisibile in due componenti la Componente A, corrispondente alla nube visibile otticamente, e la Componente B, che consiste invece nella
  • che si desidera usare Codice del componente che verrà passato al magazzino o all ufficio acquisti se il componente non è disponibile. Altre caratteristiche
  • meno appariscenti, spicca il sistema di Lacerta OB1, un associazione OB connessa a delle tenui nebulosità in cui si sono verificati recenti fenomeni di