Algoritmi/Le applicazioni degli algoritmi di visita dei grafi

Grafo aciclico

Un grafo è ciclico se ha almeno un arco all'indietro.

Componenti connesse (per grafi non orientati)

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)

Bridge (= arco la cui rimozione disconnette il grafo)

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)

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

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.

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)

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

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