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

Definizione (grafo diretto, grado entrante e uscente). 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$ (ogni arco ha una sola coda e una sola testa, quindi contribuisce $1$ a una somma di uscenti e $1$ a una somma di entranti: a differenza dei grafi non diretti, dove la somma dei gradi è $2m$, Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →). Nei circuiti elettrici il grafo ha archi orientati secondo il verso di riferimento delle correnti (Grafo di una rete ed equazioni indipendentiIl grafo di una rete tiene solo i collegamenti (nodi e lati). Scelto un albero (n−1 lati, connesso, senza maglie), ogni lato di coalbero dà una LKT indipendente e ogni lato d'albero una LKC indipendente: in totale ℓ − n + 1 LKT e n − 1 LKC, che con le ℓ equazioni dei bipoli fanno 2ℓ equazioni per 2ℓ incognite.Grafo di una rete ed equazioni indipendenti →).

Esempio. Con archi $A\to B$, $A\to C$, $C\to B$: $\text{out}(A)=2$ e $\text{in}(B)=2$.

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

Definizione (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. Anche una rete combinatoria di porte logiche è un DAG (le uscite dipendono dagli ingressi senza retroazione: Reti combinatorie e mappe di KarnaughRete combinatoria (uscite funzione dei soli ingressi attuali); mintermini e maxtermini, forme canoniche SOP e POS; mappe di Karnaugh a 3 e 4 variabili con esempi svolti; condizioni di indifferenza; costo e ritardo di una rete a due livelli.Reti combinatorie e mappe di Karnaugh →), e per calcolare l'uscita si valutano le porte proprio in ordine topologico; una retroazione crea un ciclo e dà una rete sequenziale (Reti sequenziali e automi a stati finitiModello di una rete sequenziale sincrona (stato in flip-flop, logica di stato prossimo e di uscita); automi di Moore e di Mealy; procedimento di sintesi con esempio svolto di un riconoscitore della sequenza 11.Reti sequenziali e automi a stati finiti →). Una relazione "$u$ deve precedere $v$" senza cicli è un ordine parziale: un ordine topologico ne è un'estensione a ordine totale.

Esempio. Gli archi $A\to B$ e $B\to C$ formano un DAG; aggiungendo $C\to A$ si crea un ciclo diretto e il grafo non è più un DAG.

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. Esempio: nel grafo $A\to B$, $B\to C$, $C\to A$ la DFS da $A$ scende a $B$, poi a $C$, e l'arco $C\to A$ punta ad $A$, che è ancora "in corso" (antenato di $C$): back edge, quindi ciclo. Nel DAG $A\to B$, $A\to C$, $B\to C$ la DFS da $A$ scende a $B$, poi a $C$; tornando ad $A$ l'arco $A\to C$ punta a $C$, già terminato: è un forward edge (verso un discendente già visitato), non un back edge, e non c'è ciclo.

Ordinamento topologico

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

Esempio. Per il DAG con archi $A\to B$ e $A\to C$ sono ordini topologici sia $A,B,C$ sia $A,C,B$.

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. Perché: ogni vertice rimasto ha in $\ge1$, cioè ha almeno un predecessore tra i rimasti; partendo da uno qualsiasi e risalendo di predecessore in predecessore tra i rimasti, poiché i vertici sono finiti prima o poi se ne ripete uno, e ciò chiude un ciclo. Il calcolo dei gradi entranti si fa in una sola scansione degli archi (v.in <- v.in + 1 per ogni arco $u\to v$), in $\Theta(n+m)$; la coda è una coda FIFO (Liste, pile e codeRipasso degli ADT elementari: lista index-based (array) e position-based (lista doppiamente concatenata con sentinelle), pila LIFO, coda FIFO, deque, iteratori; interfacce, implementazioni e costi; array estendibile e coda circolare.Liste, pile e code →) e la logica ricorda la BFS (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 →). Con una pila al posto della coda si ottiene un altro ordine topologico valido.

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)$. La DFS è ricorsiva (Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.Algoritmi ricorsivi →) e "termina" un vertice quando ritorna dalla chiamata, cioè nell'ordine postorder come nelle visite degli alberi (Visite di alberiVisite in preorder e postorder come schemi generali (template) da adattare; complessità Theta(n + somma dei costi di visita) perché la somma dei figli è n-1; esempi (indice di un libro, spazio occupato in un file system); profondità con il preorder, altezza con il postorder; antenato comune più basso.Visite di alberi →): il reverse postorder è l'analogo, sui DAG, dell'ordine "genitore prima dei figli" del preorder.

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. Controllo dell'ordine $A,F,B,C,D,E$ sugli archi: $A\to B$ ($A$ in posizione 1, $B$ in 3 ✓), $A\to C$ (1 e 4 ✓), $B\to D$ (3 e 5 ✓), $C\to D$ (4 e 5 ✓), $D\to E$ (5 e 6 ✓), $F\to C$ (2 e 4 ✓). Traccia della DFS (si segnano inizio e fine di ogni vertice, in ordine di successori alfabetico): inizio $A$, inizio $B$, inizio $D$, inizio $E$, fine $E$, fine $D$, fine $B$, inizio $C$ (il suo successore $D$ è già finito), fine $C$, fine $A$; poi, partendo dal vertice non visitato $F$: inizio $F$ ($C$ è già finito), fine $F$. Ordine di fine $E,D,B,C,A,F$, rovesciato $F,A,C,B,D,E$. (Verificati eseguendo le due implementazioni.)

Proprietà (cammini minimi in un DAG pesato). 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).

Esempio. Con archi $s\to a\,(2)$, $s\to b\,(3)$, $b\to a\,(-2)$ l'ordine topologico $s,b,a$ dà $d(a)=\min(2,\,3-2)=1$. Passo per passo: $d(s)=0$; si rilassano gli archi uscenti di $s$: $d(a)=2$, $d(b)=3$; si passa a $b$ (secondo nell'ordine): l'arco $b\to a$ dà $3+(-2)=1<2$, quindi $d(a)=1$; si passa ad $a$ e non ci sono archi uscenti. Qui non c'è il problema di Dijkstra con pesi negativi (Cammini minimi e algoritmo di DijkstraGrafi pesati, lunghezza di un cammino e distanza; sottocammini di un cammino minimo; problema SSSP; algoritmo di Dijkstra con cloud e priority queue, rilassamento degli archi, esempio svolto; correttezza (due lemmi) e complessità O(min(n^2, (n+m) log n)) con lista non ordinata o heap; pesi non negativi.Cammini minimi e algoritmo di Dijkstra →) perché $b$ è elaborato prima di $a$: l'ordine topologico garantisce che quando si arriva a un vertice tutti i suoi 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.