Algoritmi e Strutture di dati - Appunti

INTRODUZIONE AI GRAFI.

DEFINIZIONI:

Un grafo G = (V,E) è costituito da un insieme di nodi (o vertici) V e un insieme di

archi E ciascuno dei quali connette due nodi in V detti estremi dell’arco.

Un grafo è orientato quando vi è un ordine tra i due estremi degli archi. In questo

caso il primo estremo si dice coda ed il secondo testa.

Un cappio è un arco i cui estremi coincidono.

Un grafo non orientato semplice non ha cappi e non ci sono due archi con gli stessi

estremi.

Un grafo orientato semplice è un grafo dove non ci sono due archi con gli stessi

estremi.

Se un grafo è semplice, possiamo identificare un arco con la coppia dei suoi

estremi: e = (u,v), in questo caso diciamo che l’arco è incidente in u e v.

Se il grafo è orientato, la coppia (u,v) è ordinata. In questo caso diciamo che l’arco e

esce da u ed entra in v.

Il grado g(v) del vertice v è il numero di archi incidenti in v. Se il grafo è orientato,

g(v) si suddivide in grado entrante g-(v) che è il numero di archi entranti in v ed un

grado uscente g+(v) che è il numero di archi uscenti da v.

Se e = (u,v), diciamo che il vertice v è adiacente al vertice u. Se il grafo non è

orientato la relazione di adiacenza è simmetrica e in tal caso diciamo che u e v sono

adiacenti.

Un cammino di lunghezza k dal vertice u al vertice v in un grafo G = (V,E) è una

sequenza di k+1 vertici x(0), x(1), …, x(k) tali che x0 = u, x(k) = v e (x(i-1), x(i)) € E

per ogni i = 1..k.

Il cammino 0 ha lunghezza k = 0.

Se k > 0 e x(0) = x(k) diciamo che il percorso (cammino) è chiuso.

Un cammino semplice è un cammino i cui vertici x(0), x(1), … x(k) sono tutti distinti

con la possibile eccezione di x(0) = x(k) nel qual caso esso è un ciclo.

Un ciclo di lunghezza k = 1 è un cappio.

Un grafo aciclico è un grafo che non contiene cicli.

Quando esiste almeno un cammino dal vertice u al vertice v, diciamo che il vertice v

è accessibile o raggiungibile da u.

Un grafo non orientato si dice connesso se esiste almeno un cammino tra ogni

coppia di vertici.

Le componenti connesse di un grafo sono le classi di equivalenza dei suoi vertici

rispetto alla relazione di accessibilità. (se da un nodo posso raggiungere tutti i nodi

ho una sola componente connessa contenente tutti i vertici).

Un grafo orientato si dice fortemente connesso se per ogni coppia di vertici u e v

esiste un cammino da u a v e uno da v a u.

Le componenti fortemente connesse di un grafo orientato sono le classi di

equivalenza dei suoi vertici rispetto alla relazione di mutua accessibilità.

Un sottografo del grafo G = (V, E) è un grafo G’ = (V’, E’) tale che V’ è contenuto in

V ed E’ è contenuto in E.

Vi sono due modi standard per rappresentare un grafo G = (V,E):

- Con le liste di adiacenza;

- Con la matrice di adiacenza.

La rappresentazione di G = (V,E) mediante liste di adiacenza è costituita da una lista

Adj[u] per ogni vertice u € V in cui vengono memorizzati i vertici adiacenti al vertice

u (ossia tutti i vertici v tali che (u,v) € E).

Nella rappresentazione di G = (V,E) mediante matrice di adiacenza assumiamo che i

vertici siano numerati 1, 2, …, n in qualche modo arbitrario. La rappresentazione è

quindi costituita da una matrice booleana A = A[i,j] tale che:

a(i,j) = 1 se ij € E

a(i,j) = 0 se ij non € E

La rappresentazione di G = (V,E) mediante liste di adiacenza richiede memoria per

n = |V| puntatori alla testa delle liste Adj[u] e memoria per m = |E| elementi delle liste

se il grafo è orientato, un totale di 2m elementi se è non orientato.

La rappresentazione di G = (V,E) mediante matrice di adiacenza richiede memoria

per una matrice A di n x n valori booleani.

ALGORITMI DI RICERCA:

- RICERCA IN AMPIEZZA (BFS):

Dato un grafo G = (V,E) ed un vertice particolare s € V, la ricerca in

ampiezza partendo dalla sorgente s visita sistematicamente il grafo

per scoprire tutti i vertici che sono raggiungibili da s.

Nel contempo calcola la distanza di ogni vertice del grafo dalla

sorgente s (lunghezza minima di un cammino dalla sorgente al

vertice).

Esso produce inoltre l’albero della ricerca in ampiezza i cui rami sono

cammini di lunghezza minima.

La ricerca viene detta in ampiezza perché l’algoritmo espande

uniformemente la frontiera tra i vertici scoperti e quelli non ancora

scoperti.

In altre parole scopre tutti i vertici a distanza k da s prima di scoprire

quelli a distanza k + 1.

Per mantenere traccia del punto a cui si è arrivati nell’esecuzione

dell’algoritmo i vertici sono colorati bianco (vertici non ancora

raggiunti), grigio (vertici raggiunti e che stanno sulla frontiera) e nero

(vertici raggiunti ma che non stanno più sulla frontiera).

Conseguenza: I vertici adiacenti ad un vertice nero possono essere

soltanto nero o grigi mentre quelli adiacenti ad un vertice grigio

possono essere anche bianchi.

L’algoritmo costruisce un albero che all’inizio contiene soltanto la

radice s.

Quando viene scoperto un vertice bianco v a causa di un arco (u, v)

che lo connette ad un vertice u scoperto precedentemente, il vertice v

e l’arco (u,v) vengono aggiunti all’albero. Il vertice u viene detto padre

di v.

Valutiamo la complessità di BFS in funzione del numero n di vertici e

del numero m di archi.

L’inizializzazione richiede tempo O(n) dovendo percorrere tutti i vertici

del grafo.

Dopo l’inizializzazione nessun vertice viene più colorato di bianco e

questo ci assicura che ogni vertice verrà inserito nella coda al più una

sola volta. Quindi il ciclo while di inizializzazione viene eseguito al più

n volte.

Il tempo richiesto per il ciclo while è dunque O(n) più il tempo

richiesto per eseguire i cicli for interni. I cicli for interni percorrono una

sola volta le liste delle adiacenze di ciascun vertice visitato. Siccome

la somma delle lunghezze di tutte le liste è O(m) possiamo

concludere che la complessità è O(n + m). Dove n numero di vertici e

m numero di archi. Complessità lineare.

Quando l’algoritmo termina sappiamo che il “grado” maturato dal

nodo v, rappresenta il cammino minimo da s a v per ogni vertice v del

grafo.

Vedere altre proprietà e dimostrazioni (da pagina 39 a 59).

- RICERCA IN PROFONDITA (DFS):

La strategia della ricerca in profondità è quella di avanzare in

profondità nella ricerca finché è possibile. Si esplorano quindi sempre

gli archi uscenti dal vertice u raggiunto per ultimo. Se viene scoperto

un nuovo vertice v, ci si sposta su tale vertice. Se tutti gli archi uscenti

da u portano a vertici già scoperti, si torna indietro e si riprende

esplorando archi uscenti dal vertice da cui u è stato scoperto.

A differenza della ricerca in ampiezza in cui i puntatori al padre

definiscono un albero, nella ricerca in profondità essi definiscono un

insieme di alberi, la foreste di ricerca in profondità. Anche in questo

caso utilizziamo la notazione {bianco – grigio – nero}.

La ricerca in profondità pone due time-stamp su ogni vertice u. Un

primo time-stamp d[u] viene posto quando il vertice viene scoperto e

colorato grigio e un secondo time-stamp f[u] quando il vertice è finito

e viene colorato nero.

Valutiamo la complessità di DFS in funzione del numero n di vertici e

del numero m di archi.

Senza le chiamate a DFS_ricorsivo i due cicli for di DFS richiedono

tempo O(n). La funzione DFS_ricorsivo viene richiamata solo su

vertici bianchi che vengono subito colorati di grigio. Essa viene quindi

richiamata al più una volta per ogni vertice. Il ciclo interno percorre la

lista delle adiacenze del vertice di invocazione. Siccome la somma

delle lunghezze di tutte le liste di adiacenza è O(m), l’intero algoritmo

ha complessità O(n + m).

Proprietà (si dimostra, vederla): Se si rappresenta la scoperta di ogni

vertice u con una parentesi aperta (u e la finitura con una parentesi

chiusa u), si ottiene una sequenza bilanciata di parentesi. Ossia per

ogni coppia di vertici u e v ci sono quattro possibilità:

(u u) … (v v);

 (v v) … (u u);

 (u (v v) u);

 (v (u u) v);



Proprietà (si dimostra, vederla): il vertice v è discendente del vertice u

in un albero della foresta di ricerca in profondità se e solo se: (u (v v)

u);

Proprietà (si dimostra, vederla): il vertice v è discendente del vertice u

in un albero della foresta di ricerca in profondità se e solo se

nell’istante in cui u viene scoperto esiste un cammino da u a v i cui

vertici sono tutti bianchi (cammino bianco).

Con la ricerca in profondità gli archi si possono classificare in :

Archi d’albero: archi (u, v) con v scoperto visitando le

 adiacenze di u;

Archi all’indietro: archi (u, v) con u = v oppure v

 ascendente di u in un albero della foresta di ricerca in

profondità;

Archi in avanti: archi (u, v) con v discendente di u in un

 albero della foresta;

Archi trasversali: archi (u, v) in cui v ed u appartengono a

 rami o alberi distinti della foresta.

N.B: se un arco soddisfa le condizioni per appartenere a più di una

categoria, esso viene classificato in quella che compare per prima

nell’ordine in cui le abbiamo elencate.

ORDINAMENTO TOPOLOGICO:

La ricerca in profondità si può usare per ordinare topologicamente un grafo orientato

aciclico (detto anche DAG: Directed Acyclic Graph).

Un ordinamento topologico di un grafo orientato aciclico G = (V,E) è un ordinamento

dei suoi vertici tale che per ogni arco (u, v) € E il vertice u precede il vertice v.

L’ordinamento topologico si usa per determinare un ordine in cui eseguire un

insieme di attività in presenza di vincoli di propedeuticità (es. vestirsi, ordine degli

esami).

L’algoritmo è lo stesso del DFS con le relative varianti del caso e la complessità è la

stessa O(n + m).

N.B: Un grafo orientato è aciclico se e solo se nella ricerca in profondità non si trova

nessun arco all’indietro.

COMPONENTI FORTEMENTE CONNESSE.

Un grafo orientato G si dice fortemente connesso se, per ogni coppia di nodi u,v €

V(G), esiste un cammino da u a v e uno da v a u (simbolo  ondulato strano).

Tale relazione è una relazione di equivalenza:

- Riflessiva: per ogni u € V(G), u  u; (cammino di lunghezza sempre zero,

anche di lunghezza 1 se esiste un cappio);

- Simmetrica: per ogni u, v € V(G),