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

Da WikiAppunti.
Nota disambigua.svg 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.
Gtk-go-back-ltr.svg  13. Gli algoritmi di visita dei grafi Gtk-home.svg  Algoritmi e programmazione 15. Gli alberi ricoprenti minimi  Gtk-go-forward-ltr.svg

Grafo aciclico[modifica]

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

Componenti connesse (per grafi non orientati)[modifica]

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]

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

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]

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]

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]

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:

  1. si traspone il grafo;
  2. si esegue la visita in profondità sul grafo trasposto, calcolando i tempi di scoperta e di fine elaborazione;
  3. eseguendo la visita in profondità sul grafo originale per quei tempi di fine elaborazione decrescenti, si trovano man mano le componenti fortemente connesse;
  4. 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.
Nota disambigua.svg 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.
Gtk-go-back-ltr.svg  13. Gli algoritmi di visita dei grafi Gtk-home.svg  Algoritmi e programmazione 15. Gli alberi ricoprenti minimi  Gtk-go-forward-ltr.svg