Algoritmi - Appunti

GRAFI

I grafi sono coppie <V, E> dove V è un insieme di nodi (o vertici) ed E è una collezione di

archi. Entrambi sono posizioni e contengono elementi: ad esempio si può pensare ai vertici

come a delle città e agli archi come ai percorsi dall'una all'altra, definiti dalla loro lunghezza.

Sono spesso associati ai multi-insiemi, ossia insiemi che ammettono duplicati. È ammissibile

anche un arco che punta al suo stesso vertice (cappio).

La rappresentazione grafica dei grafi è arbitraria: sia vertici che archi possono essere disegnati

in molti modi diversi. È comunque un problema importante nell'informatica il graph drawing,

ossia la rappresentazione più conveniente di un grafo. Ci si concentra in modo particolare su

come evitare sovrapposizioni di archi nel disegno. Famoso è il problema del grafo K(3, 3),

con tre case e tre centrali: non ammette soluzioni senza sovrapposizioni di archi.

Il grafo orientato o diretto ha frecce su almeno un arco; viceversa, non è orientato. Col

termine spigolo si indica un nodo che non è puntato da una freccia, mentre vertice indica un

nodo puntato da freccia (la distinzione tra i due non sussiste ai fini del corso).

Un grafo è essenzialmente una relazione binaria R = V x V su V. Ogni coppia è ordinata,

ovvero (Vi, Vj) != (Vj, Vi). Quindi, dal punto di vista matematico, esiste solo il grafo orientato.

Viene tuttavia soddisfatta la proprietà simmetrica: se (a, b) appartiene alla relazione, ossia

esiste un arco tra a e b, allora anche (b, a) vi appartiene, ovvero c'è anche l'arco di ritorno. Il

grafo non è orientato, essenzialmente, se l'arco di andata coincide con l'arco di ritorno.

La coppia ordinata viene indicata con (a, b) oppure <a, b>. Quella non ordinata viene indicata

come {a, b}, ovvero come insieme.

Due vertici collegati sono detti adiacenti. Il grado dei vertici è il numero dei suoi archi. I

cappi sono archi che puntano allo stesso vertice. Si usa il termine percorso o cammino per

indicare una sequenza vertice-spigolo-vertice... mentre i cicli indicano la ricorrenza di un dato

percorso. I vertici si indicano con n e gli spigoli con m.

In un grafo non orientato, senza self-loop e spigoli multipli, m <= n(n-1)/2

Questo significa che il numero massimo degli spigoli è quadratico. Un grafo di ordine di n^2

archi è detto denso, quello di ordine n è detto sparso.

Se un grafo si può disegnare in maniera planare, è sparso.

Il grafo diretto ha m + (n(n+1)). Metodi principali:

insert (vertex ed edge)

⁃ remove (vertex ed ed edge)

⁃ vertices () ed edges():

⁃ endVertices

⁃ replace

⁃

Ci sono tre implementazioni fondamentali per i grafi. Una si basa su tre array: quello

contenente gli elementi, quello per gli oggetti e i riferimenti agli oggetti collegati, e quello per

gli edge. Quella con gli array ha però la limitazione di non saper trovare tutti gli spigoli

adiacenti a un vertice in tempo veloce.

Si può quindi cambiare a favore della rappresentazione in lista delle adiacenze, ove ogni

vertice ha un puntatore aggiuntivo costituito dalla lista collegata di tutte le sue incidenze.

Questo comporta che, per trovare n nodi adiacenti, è necessario un tempo pari a O(n), con

O(1) per nodo.

Ancora più famosa è la matrice delle adiacenze, in cui esistono ancora la lista delle

adiacenze e la lista degli archi, ma si aggiunge una matrice nxn di boolean in cui il valore è

true se l'arco tra Vi e Vj esiste, e false se non esiste tra Vj e Vi. La proprietà di simmetria si

riflette anche nella matrice, simmetrica rispetto alla sua diagonale, che può rappresentare

anche autoanelli e può essere allocata solo per metà se il grafo è simmetrico.

L'operazione "trova tutte le adiacenze" si svolge in Theta(n), perché bisogna controllare tutte le

adiacenze di un dato vertice. Nel complesso l'implementazione via matrice delle adiacenze è

sconveniente: esegue la verifica di adiacenza in O(1), gli altri tempi però sono almeno pari

agli altri due. L'implementazione è quindi adeguata a un utilizzo che prevede tante verifiche di

adiacenza; altrimenti è preferibile la rappresentazione in lista delle adiacenze.

Lista spigoli Lista adiacenze Matrice adiacenze

Spazio m + n m n^2

incidentEdges(v)

areAdjacent(v, w) m min(m, n) 1

insertVertex(o) n^2

insertEdge(v, w, o) 1 1 n^2

removeVertex(o)

Il sottografo G' è un grafo tale che i suoi vertici e spigoli sono un sottoinsieme di quelli di G.

Un sottografo ricoprente (spanning graph) è un sottografo che include tutti i vertici di G.

Un sottografo indotto o sui vertici ha un sottoinsieme dei vertici e tutti gli archi di G.

Un grafo è connesso se esiste un percorso tra ogni coppia di vertici, altrimenti può avere delle

componenti connesse.

Un albero libero è un grafo non orientato connesso e aciclico, non-rooted, ossia senza

un'orientazione (come gli alberi studiati con radice). Una foresta è un grafo non orientato

aciclico, le cui componenti connesse sono alberi. Un albero ricoprente è un sottografo

ricoprente che è anche un albero, e non sempre esiste; la foresta ricoprente è l'estensione alle

foreste del medesimo concetto.

Costruire un albero ricoprente è il primo passo per la visita in profondità di un grafo.

DFS -- (algoitmo per spanning trees)

depth-first search --

L'algoritmo DFS visita i grafi e consulta le etichette assegnate a vertici e spigoli. Per evitare di

rivisitare lo stesso spigolo o lo stesso vertice, si usa una variabile boolean explored

inizializzata a false. L'esplorazione viene lanciata ciclicamente dal metodo principale a partire

da un vertice casuale, esplorando tutti gli spigoli e i vertici possibili; poi si ricontrolla se il

grafo è stato totalmente esplorato e, in caso contrario, l'esplorazione viene rilanciata a partire

dal primo vertice inesplorato.

L'algoritmo che visita effettivamente il grafo è ricorsivo. La prima azione compiuta è il

cambiamento della variabile explored. Successivamente il metodo viene chiamato nel caso dei

vertici per ogni spigolo incidente inesplorato, nel caso degli spigoli per ogni vertice incidente

inesplorato.

Supponiamo di avere il seguente grafo:

Si parte da 1, chiamando ricorsivamente per tutti gli archi incidenti a partire da uno a caso,

il cui label è posto su DISCOVERY se sono precedentemente UNEXPLORED. Se uno spigolo

UNEXPLORED porta a un vertice visitato, lo si marca come BACK. Finite le marcature, si

controlla ciclicamente se ci sono altri vertici inesplorati; se ci sono, l'esplorazione riparte da lì.

Le componenti connesse sono spanning forests. Se il grafo è connesso, si parla di spanning

trees.

Il costo dell'algoritmo si calcola approssimativamente considerando che: il ciclo sui vertici

costa n; quello sugli spigoli costa m; ogni vertice o spigolo genera al massimo deg(x)

chiamate ricorsive (con l'opportuna implementazione dell'algoritmo che trova le adiacenze,

quello basato sulle liste di adiacenza). Si tratta quindi di un O(m). Sommando i costi si ottiene

O(n + m) o, con maggiore precisione, Theta(n + m), considerato che nessun vertice o

spigolo viene visitato due volte.

GRAFI E LABIRINTI

L'algoritmo DFS può essere usato per esplorare labirinti. A ogni incrocio si va a sinistra, e a

ogni passaggio si marca come attraversato il percorso. Il metodo ricorsivo richiede un

parametro aggiuntivo, z, che rappresenta la configurazione finale, in modo tale da

confrontarla con la configurazione attuale. Una struttura a pila memorizza il percorso

effettuato per giungere al nodo corrente.

Per sapere se un grafo è ciclico o meno basta aggiungere un controllo sulla visita: se viene

posto anche un solo label BACK, il grafo contiene cicli. Si può anche memorizzare in una pila i

vertici e gli spigoli attraversati; poi si effettuano operazioni di pop appena viene posto un

BACK fino a che non si ritrova il vertice a cui conduce lo spigolo BACK, restituendo così tutti gli

elementi del ciclo. Questa tecnica trova un solo ciclo; trovarli tutti comporterebbe costi molto

maggiori.

I grafi diretti sono grafi orientati; ogni loro spigolo va in una sola direzione. In questo caso si

distingue tra indeg(x) e outdeg(x).

I digrafi sono utili nella pianificazione (scheduling), per decidere quale attività deve essere

svolta prima che ne inizi una nuova. L'inizio avviene da un nodo tale che indeg(x) = 0, la cui

presenza non è garantita nel digrafo; inoltre è necessario che non siano presenti cicli.

La DFS è applicabile anche ai digrafi, con la differenza che viene utilizzata ovviamente solo per

gli spigoli orientati all'esterno (outdeg(x)).

Ci sono due tipi di connessione nei grafi: la connessione forte e la connessione debole. La

connessione forte prevede che ogni vertice conduca a un qualsiasi altro vertice; la connessione

debole prevede che il corrispettivo grafo non orientato sia fortemente connesso (ovvero che ci

sia almeno un collegamento, sia esso in ingresso o in uscita, per ogni vertice).

Nei digrafi, le DFS attraversano tutti i vertici raggiungibili da un vertice dato. Se due spigoli

portano allo stesso vertice e hanno lo stesso spettro di esplorabilità del grafo, il secondo di

quelli visitati viene etichettato come CROSS.

La visita di un grafo costringe prima o poi a tornare al vertice iniziale; di qui il concetto di

abbandono definitivo di un vertice: avviene quando un vertice non si visita più. Anche qui è

possibile memorizzare i vertici abbandonati e restituirli nell'ordine di abbandono. I cicli

riportano quindi ai nodi già visitati.

La verifica di connettività forte avviene verificando che la visita sia completata dopo aver

finito le ricorsioni. Il trasposto di un grafo connesso è connesso. Anche un grafo debolmente

connesso ha delle parti fortemente connesse. L'algoritmo per individuarle prevede la DFS del

grafo originario più la DFS del grafo trasposto, effettuata a partire dai vertici abbandonati. Il

costo asintotico è identico a quello delle DFS per grafi non orientati.

La chiusura transitiva di un grafo diretto è una proprietà per cui, se esiste un cammino dal

nodo a al nodo b, allora esiste un arco tra a e b. È un problema d'interesse la verifica della

chiusura transitiva di un grafo, così come la trasformazione di un grafo non transitivo in un

grafo transitivo e viceversa (riduzione transitiva).

Un primo approccio può essere la DFS da ogni vertice, di costo O(n(n + m)), ricollegando a

ogni nodo un arco che lo connetta a ogni altro suo nodo non adiacente. Nel caso peggiore,

ovvero se siamo in presenza di un grafo denso (che ha un numero di nodi pari a O(n^2)) il

cos