Olimpiadi di Informatica 2010 Giornate preparatorie Dipartimento di Informatica Università di Torino marzo 2010 12 Algoritmi sui grafi: ordinamento topologico. (versione 22/12/2015) 12/22/2015 E. Giovannetti -- OI09. 1 Una proprietà dei grafi orientati aciclici. Nei grafi orientati aciclici la relazione “da A è raggiungibile B” è una relazione d’ordine parziale. Infatti è: • riflessiva: A è raggiungibile da A; • transitiva: se B è raggiungibile da A e C è raggiungibile da B allora C è raggiungibile da A; • antisimmetrica: se A è raggiungibile da B e B è raggiungibile da A, allora A e B sono coincidenti (cioè non vi può essere una coppia di nodi distinti mutuamente raggiungibili). Una relazione d’ordine parziale può venire completata (generalmente in più modi) in una relazione d’ordine totale. Un tale ordine totale dei nodi si chiama ordine topologico. Possiamo quindi dare la seguente equivalente definizione. 22/12/2015 00:52 E. Giovannetti - AlgELab-09-10 - Lez.45 2 Definizione Dato un grafo orientato aciclico, un ordine topologico è: un ordine lineare dei suoi nodi tale che se nel grafo vi è un arco (u, v), allora u precede v nell’ordine. Cioè: ordine topologico su un grafo orientato aciclico G = (V, E) è una relazione d’ordine totale ““ sull’insieme V dei nodi, tale che (u, v) E u v Equivalentemente, un ordine topologico su un grafo è: un ordine lineare dei suoi nodi tale che se nel grafo vi è un cammino da u a v, allora u precede v nell’ordine. Cioè: ordine topologico su un grafo orientato aciclico G = (V, E) è una relazione d’ordine totale ““ sull’insieme V dei nodi, tale che esiste un cammino da u a v u v 22/12/2015 00:52 E. Giovannetti - AlgELab-09-10 - Lez.45 3 Proprietà ed esempi • Un grafo orientato aciclico possiede sempre un ordine topologico. • Un grafo può possedere diversi ordini topologici. (a) Un grafo aciclico; 22/12/2015 00:52 (b) Ordine topologico dei nodi del grafo (a) E. Giovannetti - AlgELab-09-10 - Lez.45 4 Esempio (1/2) Dato il grafo: C F A E B D L’ordine: F C E D A B è un ordine topologico Infatti disegnando gli archi del grafo essi risultano tutti orientati nello stesso verso (da sinistra verso destra): F C E D A B 5 Esempio (2/2) F C A E B D Ma non è l’unico, anche i seguenti sono ordini topologici A B C F D E C D A F E B 6 Un’altra proprietà dei grafi orientati aciclici. Per comodità, diamo le seguenti due definizioni: • nodo sorgente = nodo che non ha archi entranti; • nodo pozzo = nodo che non ha archi uscenti. Proprietà. In un grafo orientato aciclico vi sono almeno un nodo pozzo e almeno un nodo sorgente. (ovvio, perché in un insieme parzialmente ordinato costituito da un numero finito di elementi vi sono sicuramente sia elementi minimali che elementi massimali). 22/12/2015 00:52 E. Giovannetti - AlgELab-09-10 - Lez.45 7 Come trovare un nodo sorgente. Nelle prossime slides vedremo che per trovare un sorgente basta operare una visita per profondità, grazie alla seguente proprietà: il nodo col massimo tempo di fine-visita è un nodo-sorgente. I nodi con tempi di fine-visita via via decrescenti sono a loro volta nodi-sorgente del grafo cui sono stati tolti i sorgenti precedenti, ecc. Si ottiene così un algoritmo semplicissimo, che in realtà è ricavabile direttamente da una proprietà di base della visita in profondità, da cui deriva anche la proprietà di cui sopra (il nodo col max tempo di fine-visita è un nodo sorgente). 22/12/2015 00:52 E. Giovannetti - AlgELab-09-10 - Lez.45 8 Ricorda la visita in profondità ricorsiva: visitaInProfondità (il grafo G a partire dal nodo s) { marca tutti i nodi di G come non visitati; T = albero vuoto; visitaRic(s, T); } visitaRic (il grafo G dal nodo u) { inizia_visita(u); marca u come visitato; for each (nodo v adiacente a u) if (v è non visitato) { aggiungi l'arco (u, v) a T; visitaRic(v, T); } termina_visita(u); } 22/12/2015 00:52 E. Giovannetti - AlgELab-09-10 - Lez.41 9 Una proprietà della visita in profondità. Se in un grafo G esiste un arco (orientato) (u, v), o se più in generale esiste un cammino da u a v, allora in qualunque visita in profondità di G il tempo di fine-visita di u è maggiore del tempo di fine-visita di v. Dimostrazione. Caso 1: v viene raggiunto a partire da u, cioè l’istante di inizio visita di u precede l’ l’istante di inizio visita di v. Allora l’attivazione di visitaRic(u), che effettua la chiamata di visitaRic(v), ovviamente termina dopo la terminazione di questa; Caso 2: v non viene raggiunto a partire da u, quindi deve essere stato visitato prima di u (altrimenti da u si sarebbe arrivati a v) . D’altra parte, poiché G è aciclico, non vi può essere un cammino da v a u, e quindi l’attivazione di v deve essere completamente terminata prima dell’attivazione di u. 22/12/2015 00:52 E. Giovannetti - AlgELab-09-10 - Lez.45 10 Esempio C F A E B D arco (C, E): fine(C) fine(E) arco (F, E): fine(F) fine(E) ecc. Supponiamo che si inizi la visita dal nodo C. Si ha, nell’ordine: iniz C; iniz D; fine D; iniz E; fine E; fine C; iniz F; fine F. tempo stack stack stack stack stack C C C C C D 22/12/2015 00:52 stack stack stack F E E. Giovannetti - AlgELab-09-10 - Lez.45 11 Un algoritmo di ordinamento topologico. • L’ordine degli istanti di fine visita in una visita del grafo in profondità del grado è quindi tale che: esiste un cammino da u a v fineVisita(u) > fineVisita(v) • L’ordine dei nodi secondo il tempo di fine visita in una visita in profondità è quindi l’inverso di un ordine topologico. • Per eseguire un ordinamento topologico dei nodi di un grafo orientato aciclico è allora sufficiente effettuare una visita in profondità del grafo, inserendo ad ogni fine-visita il nodo nella struttura ordinata, a partire dal fondo (ad esempio in un array a partire dal fondo, oppure in una lista inserendolo ogni volta in testa). 22/12/2015 00:52 E. Giovannetti - AlgELab-09-10 - Lez.45 12 Esempio Nella semplice rappresentazione in cui i nodi sono gl’indici dell’array degli array degli adiacenti, si ha: ... ordine = new int[N]; numOrd = N – 1; dove N è il numero dei nodi del grafo ... void visitaRic(int i) { if(visitato[i]) return; visitato[i] = true; for(int j = 0; j < grado[i]; j++) { visitaRic(nodi[i][j]); } ordine[numOrd--] = i; inserisco in ordine inverso } di tempo di fine-visita void visitaTutto() {...} 22/12/2015 00:52 E. Giovannetti - AlgELab-09-10 - Lez.45 13 Esercizio Risolvere il problema “torero” modificato nel modo seguente: date le precedenze degli indumenti (senza l’intervento di Carmen), si scriva una sequenza possibile di vestizione di tutti gli indumenti. 22/12/2015 00:52 E. Giovannetti - AlgELab-09-10 - Lez.45 14