Grafi diretti e ordinamento topologico

Nota sulle fonti: ordinamento topologico e DAG sono nel programma ufficiale ma non nel materiale del corso consultato; la nota è scritta dal programma con conoscenze standard.

Grafi diretti

In un grafo diretto $G = (V, E)$ ogni arco è una coppia ordinata $(u \to v)$: $u$ è la coda (origine) e $v$ la testa (destinazione). Per ogni vertice si distinguono il grado uscente $\text{out}(v)$ (archi che partono da $v$) e il grado entrante $\text{in}(v)$ (archi che arrivano in $v$); vale $\sum_v \text{in}(v) = \sum_v \text{out}(v) = m$.

Cammini e cicli seguono il verso degli archi: un cammino diretto è $u_1, \dots, u_k$ con $(u_i \to u_{i+1}) \in E$; un ciclo diretto è un cammino con $u_k = u_1$. Un vertice $v$ è raggiungibile da $u$ se esiste un cammino diretto da $u$ a $v$. La rappresentazione con liste di adiacenza mantiene, per ogni vertice, la lista dei soli archi uscenti (e, se serve, quella degli entranti): lo spazio è $\Theta(n + m)$ e ogni arco compare una volta (vedi Rappresentazione dei grafiStrutture di base (lista dei vertici LV, lista degli archi LE), liste di adiacenza, matrice di adiacenza; operazioni incidentEdges, opposite, areAdjacent; spazio e tempi a confronto; esempio con un grafo di 5 vertici.Rappresentazione dei grafi →).

Visite. BFS e DFS (vedi Visite di grafi - BFS e DFSVisite in ampiezza (BFS) e in profondità (DFS) come design pattern; etichette discovery, cross e back edge; BFS tree e distanze; complessità Theta(n+m) con liste di adiacenza; applicazioni (connettività, componenti, spanning tree, cammini minimi non pesati, cicli, vertici a distanza al più d); esempio svolto su un grafo di 7 vertici.Visite di grafi - BFS e DFS →) funzionano seguendo gli archi uscenti; visitano i vertici raggiungibili dalla sorgente e costano $\Theta(n_s + m_s)$ (ogni arco è esaminato una volta). Nella DFS gli archi non-albero si distinguono in: back edge (verso un antenato nell'albero DFS), forward edge (verso un discendente già visitato) e cross edge (verso un vertice in un ramo già concluso).

DAG

Un DAG (directed acyclic graph) è un grafo diretto senza cicli diretti. Modella dipendenze: prerequisiti di corsi, compiti di un progetto, dipendenze tra moduli di un programma.

Proposizione. Un grafo diretto ha un ciclo diretto $\iff$ una DFS incontra un back edge. Idea: un back edge $(u \to v)$ con $v$ antenato di $u$ chiude, insieme al cammino albero da $v$ a $u$, un ciclo; viceversa, se esiste un ciclo, il primo suo vertice visitato dalla DFS ha tutti gli altri come discendenti e l'arco del ciclo che torna a lui è un back edge.

Ordinamento topologico

Un ordinamento topologico di un DAG è una sequenza di tutti i vertici tale che per ogni arco $(u \to v)$ il vertice $u$ precede $v$. Esiste se e solo se il grafo è un DAG (con un ciclo, ogni vertice del ciclo dovrebbe precedere il successivo: impossibile). In generale non è unico.

Algoritmo con i gradi entranti

Un vertice con $\text{in} = 0$ non ha prerequisiti e può essere messo in testa. Si mette in una coda, si "toglie" dal grafo (si decrementa il grado entrante dei suoi successori) e si ripete.

Algoritmo topologicalSort(G)
Input: grafo diretto G      Output: ordine topologico, oppure "ciclo"
forall v in V do v.in <- grado entrante di v
Q <- coda con i vertici v con v.in = 0;  ordine <- lista vuota
while Q non è vuota do
    u <- Q.dequeue(); aggiungi u a ordine
    forall (u -> v) in E do
        v.in <- v.in - 1
        if v.in = 0 then Q.enqueue(v)
if ordine ha n vertici then return ordine else return "ciclo"

Invariante: v.in è il numero di predecessori di $v$ non ancora in ordine; quindi un vertice entra in coda, e poi in ordine, solo quando tutti i suoi predecessori sono già in ordine prima di lui. Costo: il calcolo dei gradi $\Theta(n + m)$, ogni vertice entra ed esce dalla coda una volta, ogni arco è considerato una volta: $\Theta(n + m)$. Se alla fine mancano vertici, restano vertici con predecessori tutti non rimossi: c'è un ciclo.

Algoritmo con la DFS

Si esegue una DFS su tutto il grafo; quando un vertice termina (tutti i suoi successori sono stati esplorati) lo si mette in una lista; l'ordine topologico è la lista rovesciata (reverse postorder).

Correttezza. Per ogni arco $(u \to v)$ in un DAG, $v$ termina prima di $u$: se $v$ è già finito quando si esamina l'arco, ovvio; se non è ancora visitato viene esplorato (e finito) prima che $u$ termini; non può essere in corso (ci sarebbe un back edge e quindi un ciclo). Rovesciando, $u$ precede $v$. Costo $\Theta(n + m)$.

Esempio svolto

DAG con vertici $A, B, C, D, E, F$ e archi $A \to B$, $A \to C$, $B \to D$, $C \to D$, $D \to E$, $F \to C$. Gradi entranti: $A = 0$, $B = 1$, $C = 2$, $D = 2$, $E = 1$, $F = 0$.

• Con i gradi entranti: coda iniziale $[A, F]$. Estrae $A$: $B$ passa a $0$ (entra), $C$ a $1$. Estrae $F$: $C$ a $0$ (entra). Estrae $B$: $D$ a $1$. Estrae $C$: $D$ a $0$ (entra). Estrae $D$: $E$ entra. Estrae $E$. Ordine: $A, F, B, C, D, E$.
• Con la DFS (da $A$, poi $F$, successori in ordine alfabetico): fine visita $E, D, B, C, A, F$; rovesciato: $F, A, C, B, D, E$.

Entrambi sono ordini topologici validi (si controlla ogni arco), e sono diversi: l'ordinamento non è unico. (Verificati eseguendo le due implementazioni.)

Applicazione: cammini minimi in un DAG pesato in $\Theta(n + m)$, anche con pesi negativi: si rilassano gli archi uscenti dei vertici nell'ordine topologico a partire dalla sorgente (quando si arriva a $v$ tutti i predecessori sono già definitivi).

Errori comuni

• Cercare un ordine topologico in un grafo con cicli (non esiste): l'algoritmo con i gradi entranti lo segnala con ordine incompleto.
• Dimenticare di rovesciare la lista nell'algoritmo con la DFS (si ottiene un ordine inverso).
• Credere che l'ordine sia unico.
• Trattare un grafo diretto come non diretto nelle visite: si seguono solo gli archi uscenti, quindi non si visitano necessariamente tutti i vertici.