Algoritmi e programmazione/Le applicazioni degli algoritmi di visita dei grafi

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 14. Le applicazioni degli algoritmi di visita dei grafi.

[[{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/Le applicazioni degli algoritmi di visita dei grafi}}/Gli algoritmi di visita dei grafi{{#ifcategory:Traduzioni\|/Le applicazioni degli algoritmi di visita dei grafi\|\|/Le applicazioni degli algoritmi di visita dei grafi}}\|13. Gli algoritmi di visita dei grafi]]	[[{{#ifcategory:Traduzioni\|/Le applicazioni degli algoritmi di visita dei grafi\|Algoritmi e programmazione\|/Le applicazioni degli algoritmi di visita dei grafi}}\|{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/Le applicazioni degli algoritmi di visita dei grafi}}]]	[[{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/Le applicazioni degli algoritmi di visita dei grafi}}/Gli alberi ricoprenti minimi{{#ifcategory:Traduzioni\|/Le applicazioni degli algoritmi di visita dei grafi\|\|/Le applicazioni degli algoritmi di visita dei grafi}}\|15. Gli alberi ricoprenti minimi]]

Grafo aciclico[modifica | modifica sorgente]

2 Un grafo è ciclico se ha almeno un arco di tipo Backward.

Componenti connesse (per grafi non orientati)[modifica | modifica sorgente]

3 Individuando le componenti connesse (= insieme massimale di tutti i vertici raggiungibili) degli alberi della visita in profondità, si può verificare se esiste almeno un cammino tra due nodi dati.

Connettività (per grafi che rappresentano una rete)[modifica | modifica sorgente]

Bridge (= arco la cui rimozione disconnette il grafo)[modifica | modifica sorgente]

6 Un arco Tree è un bridge se non esiste nessun arco Backward che collega un qualsiasi discendente a un qualsiasi antenato nell'albero della visita in profondità. Solo gli archi Tree possono essere dei bridge, perché l'esistenza di un arco Backward implica l'esistenza di un altro cammino che collega i due nodi.

Punti di articolazione (= vertice la cui rimozione disconnette il grafo)[modifica | modifica sorgente]

7 Si distinguono due casi:

vertice radice del grafo: è un punto di articolazione se ha almeno due figli nell'albero della visita in profondità;
altro vertice: è un punto di articolazione se almeno un sottoalbero figlio di quel nodo non ha un arco Backward che lo collega a un nodo antenato.

DAG[modifica | modifica sorgente]

11 I DAG sono grafi orientati privi di cicli che rappresentano dei modelli di ordine parziale, dove gli archi sono dei vincoli di precedenza di esecuzione dei compiti: un compito è eseguibile solamente dopo il completamento dei precedenti, e così via → scheduling: azioni da svolgere in un certo ordine.

13 L'ordinamento topologico di un DAG è la riscrittura del DAG in una linea di vertici con il vincolo che tutti gli archi vadano da sinistra a destra o viceversa (inverso). Per effettuare l'ordinamento topologico, si ordinano i nodi per tempi di fine elaborazione di una visita in profondità, quindi si disegnano tutti gli archi secondo una visita topologica diretta/inversa del grafo.

Componenti fortemente connesse (per grafi orientati)[modifica | modifica sorgente]

10 grafo trasposto = grafo con gli stessi vertici ma con gli archi di direzione inversa

24 Per trovare le componenti fortemente connesse si usa l'algoritmo di Kosaraju:

si traspone il grafo;
si esegue la visita in profondità sul grafo trasposto, calcolando i tempi di scoperta e di fine elaborazione;
eseguendo la visita in profondità sul grafo originale per quei tempi di fine elaborazione decrescenti, si trovano man mano le componenti fortemente connesse;
27 s'interpreta il grafo in classi di equivalenza (= componenti fortemente connesse) secondo la proprietà di mutua raggiungibilità, cioè si ricostruisce un grafo semplificato considerando ogni componente fortemente connessa come un unico nodo rappresentativo e considerando solo gli archi che connettono componenti fortemente connesse.