Grafi

giugno 2002 ASD - Grafi 2

Definizioni/1• Struttura dati per la rappresentazione di

relazioni binarie• G=(V,E), |V|=n, |E|=m• V: insieme di Vertici o Nodi• E={{vi, vj}: vi, vj V} : insieme di Spigoli

– {vi, vj} = {vj, vi} Grafo semplice o non orientato

• E={(vi, vj): vi, vj V} : insieme di Archi– (vi, vj) (vj, vi) Grafo diretto o orientato

• spesso i termini spigolo ed arco vengono usati come sinonimi


Esempi

• Relazioni di parentela – Alberi genealogici

• Relazioni tra classi nei linguaggi OO• Grafo del Web• Assetti societari• Reti di trasporto• ................


Definizioni/2

• Multigrafo: E è un multinsieme• Pseudografo: E contiene anche coppie

(vi, vi) cappi• Circuito in un grafo:

v1, v2,….., vk: (vi, vi+1) E, v1= vk (senza archi ripetuti)

• Ciclo in un grafo: Circuito con vi vj, per i j

• Grafo pesato: valore reale wk associato ad ogni arco ek


Definizioni/3

• Kn: Grafo semplice in cui sono presenti tutti gli archi.– numero di archi in Kn :

• G’=(V’,E’) sottografo di G=(V,E) se e solo se V’V ed E’ E

• grado(v): # di archi incidenti in v

• (vi, vj) E: vi adiacente a vj

1

1 2)1(

)(n

i

nnin


Esempi di grafi: (a-d) grafi semplici; (c) un grafo completo K4; (e) un multigrafo; (f) uno pseudografo; (g) un circuito in un grafo orientato; (h) un ciclo nel grafo orientato


Rappresentazioni

• Lista di adiacenza: ogni vertice è associato con la lista dei vertici adiacenti.

• Lista di adiacenza può essere una tabella o una lista concatenata

• Matrice di adiacenza: aih=1 se (vi, vh) E, aih=0 altrimenti

• Matrice di Incidenza: aih=1 se vi eh, aih=0 altrimenti


Rappresentazioni di grafi. Un grafo (a) rappresentato con una lista di adiacenze (b-c),


Rappresentazioni di grafi. Un grafo (a) rappresentato come una matrice di adiacenze (d) e come una matrice d’incidenza (e)


Vantaggi e Svantaggi• Lista di adiacenza: memoria O(m)

Vantaggi: permette di scorrere i nodi adiacenti a v in O(grado(v))Svantaggi: inserimenti e cancellazioni su liste concatenate in O(grado(v))

• Matrice di adiacenza: memoria O(n2)Vantaggi: Inserimenti e cancellazioni in O(1)Svantaggi: permette di scorrere i nodi adiacenti a v in O(n)

• D.: matrice di incidenza ?


Visita di un Grafo

• Obiettivo: visitare una sola volta tutti i nodi del grafo.

– Es.: visitare un porzione del grafo del Web

• Difficoltà: – Presenza di cicli: marcare i nodi visitati – Presenza di nodi isolati: la visita

termina quando sono state considerate tutte le componenti isolate del grafo


Visita in profondità - DFS

• La visita procede da tutti gli archi uscenti da un nodo.

• Se tutti i nodi adiacenti sono stati visitati allora si torna al nodo “predecessore”.

• Una volta tornati al nodo di partenza si prosegue da un nodo qualsiasi non visitato.

• I nodi vengono rinumerati secondo l’ordine di visita.


Esempio di applicazione dell’algoritmo depthFirstSearch ad un grafo


L’algoritmo depthFirstSearch applicato ad un grafo orientato


Implementazione della DFS/1

• I nodi sono inizialmente marcati con 0, i=1.• Assumi la visita sia arrivata ad un nodo v.• La visita prosegue da un nodo u adiacente a v

se marcato 0.• Se nessun nodo adiacente marcato 0 è

disponibile torna al nodo da cui si è raggiunto v oppure termina se v è il nodo iniziale.

• Ogni volta che un nodo mai visitato è raggiunto, questo viene marcato con i++

• Viene marcato sia l’nizio che la fine della visita di un nodo v, risp. num(v) e fin(v)



depthFirstSearch() {for (tutti i vertici v)num(v)=fin(v)=0; // Vedi slide succ.

edges = null;i=j=1; // per aggiornare num(v) e fin(v)while (<esiste v tale che num(v)==0>)//main

loop DFS(v);

<visualizza edges>}



DFS(v) {num(v)=i++; //prima visita di vfor (<tutti i vertici u adiacenti a v>)

if (num(u) == 0) {<inserisci lato (v,u) in edges>DFS(u);

}fin(v)=j++; // ultima visita di v

}


implementazione della DFS/4

• l’implementazione iterativa della DFS utilizza una pila per memorizzare gli archi uscenti da un nodo visitato

• ad ogni passo si estrae l’arco sulla cima della pila

• la visita prosegue dal nodo adiacente se marcato 0


Proprietà della DFS• l’algoritmo DFS visita l’intera componente del

grafo raggiungibile dal nodo di partenza• se collezioniamo gli archi (edges) che portano alla

scoperta di nuovi nodi, otteniamo una collezione di alberi che coprono l’intero grafo– dipende dal fatto che un arco viene seguito solo se il nodo

adiacente non è mai stato raggiunto.

• gli archi seguiti connettono un nodo con marca inferiore ad un nodo con marca superiore (forward edges)

• gli archi che non vengono seguiti al contrario connettono nodi con marca superiore a nodi con marca inferiore (back edges)


Complessità della DFS

• O(n) per inizializzare marcatura dei nodi• Test degli archi uscenti da un nodo v:

– O(grado(v)) nella rappresentazione con lista di adiacenza.

– O(n) nella rappresentazione con matrice di adiacenza.

• Ogni arco viene testato al più due volte, una volta per ogni estremo

• Complessivamente O(n + m), O(n2) (grafo denso)


Visita in ampiezza - BFS

• La visita in ampiezza fa uso di una coda per memorizzare tutti gli archi incidenti nel nodo v visitato che portano ad un nodo marcato 0

• I nodi raggiungibili marcati 0 vengono quindi marcati

• La visita procede dall’arco (v,u) in testa alla coda


implementazione della BFSbreadthFirstSearch() {

for (tutti i vertici v) num(v)=0;edges = null; i = 1;while (<esiste v tale che num(v)==0>) {num(v) = i++;enqueue(v);while (<la coda non è vuota>) {v = dequeue();


implementazione della BFS/2

for(<tutti i vertici u adiacenti a v>)if (num(u) == 0) {num(u) = i++;enqueue(u); <inserisci arco (v,u) in edges>

}}

}<visualizza edges>

}


Un esempio di applicazione dell’algoritmo breadthFirstSearch ad un grafo


Applicazione dell’algoritmo breadthFirstSearch ad un grafo orientato


Ordinamento Topologico/1• Grafi diretti aciclici (DAG) possono

rappresentare ordinamenti parziali.• Ordinamento parziale:

• Ogni elemento i è rappresentato da un nodo vi

• i<j sse esiste un cammino diretto da vi a vj.• Se esiste un ciclo non è possibile

rappresentare un ordine parziale. Perché?

kikjjii,j,k allora e se ,


Ordinamento parziale

• Possono esistere coppie tra le quali non è definito alcun ordine– Es.: classi sorelle in linuaggi OO

• Modellano molte situazioni di interesse pratico– Ereditarietà tra classi Java– Vincoli di precedenza in progetti

complessi


Ordinamento Topologico/2

• Determinare un ordinamento dei vertici vp(1), vp(2),….., vp(n) tale che se esiste un cammino da vp(i) a vp(j) allora p(i)>p(j).

• L’ordinamento topologico secondo la relazione < è ottenuto considerando la sequenza in ordine inverso

• Per determinare l’ordinamento topologico occorre che ogni nodo nell’ordine sia seguito da tutti i suoi predecessori.

• Un vertice pozzo è un vertice che non ha archi uscenti. In un DAG esiste sempre tale vertice. Perché?



TopologicalSort() {for i = 1 to n {

<trova un vertice pozzo v>num(v)=i;<elimina dal DAG tutti gli

archi incidenti in v>}

}


Ordinamento topologico:

g,e,b,f,d,c,a


Ordinamento Topologico/4• In pratica un ordinamento topologico si

ottiene se nella sequenza ogni nodo è seguito dai suoi predecessori.

• Si esegue una DFS e si ordinano i vertici secondo il valore fin(v).

• Il valore fin(v) è inferiore a quello dei suoi predecessori.

• L’ordinamento topologico si ottiene dalla sequenza ordinata secondo fin(v) scandita in ordine inverso. Come si dimostra?


Ordinamento Topologico/5TS(v)num(v)=i++;per tutti i vertici u adiacenti a v if (num(u) == 0)TS(u);

else if (fin(u)==0)errore; // identificato un ciclo

/* dopo avere esaminato tutti i predecessori, assegna a v un numero maggiore di quelli assegnati a qualsiasi predecessore */

fin(v) = j++;



topologicalSorting(digraph)per tutti i vertici vnum(v)= fin(v) = 0;

i = j = 1;while (esiste v tale che num(v) == 0) TS (v);

Visualizza vertici in ordine inverso secondo fin(v);


Connettività in Grafi diretti

• Due nodi u,v sono connessi in un grafo orientato se esiste un cammino diretto che collega u a v.

• Un grafo diretto è fortemente connesso se per ogni coppia u,v, esiste un cammino da u a v e da v ad u.

• Un grafo è debolmente connesso se ogni coppia di nodi è connessa da un cammino quando gli archi orientati si sostituiscono con gli archi non orientati.


Componenti fortemente connesse - SCC/1

• Un grafo diretto può essere decomposto in componenti fortemente connesse, V1 , V2 ,… , Vk, tale che

– – u connesso a v e v connesso ad

u

– Vj è un insieme massimale

• GT=(V, ET) ET :

kVVVV ....21

jVvu ,

TEuvEvu ),(),( se


SCC / 2

Strongly ConnectedComponent(G)

Esegui DFS(G) per calcolare fin(v) per ogni vertice v;

Calcola GT ;

Calcola DFS(GT) considerando i nodi nel Main Loop in ordine decrescente di fin(v) ;

Output ogni albero di DFS(GT ) come una componente fortemente connessa separata

• Complessità: O(m+nlog n). DFS più ordinamento in ordine decrescente rispetto a fin.


Esempio di esecuzione dell’algoritmo per SCC

num/fin

5/4

G

1/5

c

6/8

d

8/6

a b

4/22/3

g

3/1

h

7/7

e f

5

GT

4

c

1

d

2

a b

86

g

7

h

3

e f

SCC: {a,b,e} {c,d} {f,g} {h}

num

Radici Alberi DFS: b, c, g, h


Il Problema dei Cammini Minimi

• G=(V,E) è un grafo pesato sugli archi• d(u,v), (u,v) E: peso sull’arco (u,v)• Cammino dal nodo s al nodo t:

v1, v2,….., vk: (vi, vi+1) E, v1= s, vk=t

• Lunghezza del cammino:• Il cammino di lunghezza minima non

contiene cicli ……se le distanze sugli archi sono positive. Come si dimostra?

),( 1

1

1

i

k

ii vvd


Il problema dei Cammini Minimi/2

• Determinare il cammino di lunghezza minima – dal nodo s al nodo t– dal nodo s a tutti gli altri nodi V (SSSP)– tra tutte le coppie di nodi del grafo (APSP)

• Numerose applicazioni: reti stradali, reti di comunicazione, scheduling di progetti, progetto di circuiti,….


Single Source Shortest Paths/1

• Consideriamo un grafo pesato con pesi non negativi.

• Determinare il cammino minimo da un nodo s a tutti i nodi V del grafo

• Ogni sottocammino di un cammino minimo è esso stesso un cammino minimo.

• Ex: s,…,i,…j,…,v: cammino minimo da s a v i,…,j è un cammino minimo da i a j.

Come si dimostra?


Single Source Shortest Paths/2

• La collezione dei cammini minimi da s a tutti i nodi V può essere sempre posta nella forma di un albero. Come si dimostra?

• Algoritmi per SSSP mantengono ad ogni istante delle etichette sui nodi.

• Etichette rappresentano delle approssimazioni delle distanze dalla sorgente.

• Vi sono algoritmi che ad ogni passo fissano alcune etichette ai loro valori finali, ex Dijkstra.

• Altri algoritmi, ex: Bellmann & Ford, possono modificare tutte le etichette lungo l’intera esecuzione dell’algoritmo.


Dijkstra/1

1. Due insiemi di nodi Q ed R. 2. Inizialmente Q= {}, R={1,..,n}3. 4. Ad ogni passo estrai il nodo v in R con min

dist(v) ed inserisci v in Q5. Per ogni u adiacente a v aggiorna la distanza

da s ad u attraverso nodi in Q:

0)(,)(,, sdistvdistsvRv

vpred(u)

uvdvdistudist

uvdvdistudistif

),()()(

),()()(


Un’esecuzione diDijkstraAlgorithm


Dijkstra/2

• Ad ogni passo si determina la distanza minima di un nodo v in R. Il nodo viene inserito in Q.

• Dijkstra termina in n passi. • Ad ogni passo occorre determinare il nodo v in

R con minimo valore dist(v), O(log n) usando un heap per la coda di priorità.

• Occorre poi eseguire il rilassamento per ogni adiacente u di v, O(grado(u)) vertici, ed eventualmente aggiornare la priorità. Complessivamente O(m log n)

• Complessità di Dijkstra O((n + m )log n).


Dijkstra/3• Correttezza: Dimostrare che dist(v) è la distanza

minima d(v) da s a v quando v è incluso in Q.• Per assurdo, considera il primo nodo v inserito in

Q per cui dist(v) > d(v)• Esiste un cammino da s a v alternativo più breve

che contiene almeno un nodo in R.• Sia v’ il primo nodo in R sul cammino da s a v. • v’ è connesso ad s con un cammino formato di

soli nodi in Q, con dist(v’) < dist(v).• Una contraddizione poiché v’ sarebbe stato

selezionato in luogo di v.


Dijkstra/4DijkstraAlg(grafo digraph, vertice source)for tutti i vertici v dist(v)= ;

dist(source)=0;R = tutti i vertici; while (R!=0)v = vertice in R con minimo dist(v);for tutti i vertici u in R adiacenti a vif dist(u) > dist(v) + d(v,u)dist(u) = dist(v) + d(v,u);

pred(u) = v;


Dijkstra/5

• La collezione dei pred(u) forma l’albero dei cammini minimi con sorgente s.

• Si può risolvere il problema APSP eseguento n volte Dijkstra a partire da n sorgenti. Complessità:O(n (m +n) log n).


Minimo Albero Ricoprente – MST

• Si desidera selezionare un sottografo di un grafo che mantenga la connettività tra tutti i nodi al minore costo possibile.

• Ex: selezionare un sottoinsieme di tratte aeree che permettono di raggiungere tutte le destinazioni con costo minimo.

• Assumiamo un grafo semplice e pesi non negativi d(u,v) sugli archi.

• La rete ottima è un albero. Perché?


a

b

h

c d

g

e

f

i

8 7

9

1021

8

4

11 144

2

67

A Graph and its MST


MST / 2

• Strategie Greedy: procedi attraverso una sequenza di scelte ottime locali. – in generale portano alla soluzione ottima solo in

casi particolari.

• Per il MST, consideriamo algoritmi che mantengono la seguente proprietà:P1. Ad ogni passo l’insieme degli archi selezionati è un sottoinsieme del MST finale.

• Ad ogni passo un nuovo arco viene aggiunto alla soluzione mantenendo P1


MST / 3• Definiamo un arco “safe” se può essere

aggiunto ad un MST mantenendo P1• Il generico algoritmo Greedy:

Algorithm_MST(G,d)

A={}while A non è uno Spanning Tree

trova un arco (u,v) safe per A;Inserisci (u,v) in A;

return A

• Diversi algoritmi differiscono per la strategia di ricerca di un arco safe.

• Questo algoritmo ha n-1 iterazioni


archi “safe”• un taglio (S, V\S) è una partizione dei

vertici negli insiemi S e V\S• un arco (u,v) attraversa il taglio se uS e

v V\S (o viceversa)• un taglio rispetta un insieme di archi A se

nessun arco di A attraversa il taglio• l’arco (u,v) di peso minimo che

attraversa il taglio è safe per A– è ok un qualsiasi taglio che rispetti A

• dimostrazione?


Algoritmo di Boruvka

• L’insieme A forma un insieme di componenti connesse

• Safe: Determina l’arco di costo minimo che connette due componenti connesse in A.

• I pesi degli archi vengono memorizzati in una coda di priorità.

• Ad ogni passo si estrae il minimo e si eliminano anche tutti gli archi tra due componenti che vengono unite.

• Complessità?


a

b

h

c d

g

e

f

i

8 7

9

1021

8

4

11 1442

67

a

b

h

c d

g

e

f

i

1 2

34

6

5

7

9

Esecuzione dell’Algoritmo

di Boruvka

La numerazione indica l’ordine di selezione degli archi del MST


Algoritmo di Kruskal

• Ordina gli archi secondo peso crescente• Safe: Determina l’arco di peso minimo che

non determina cicli in A.• Complessità:

– Ordinamento degli archi in O(m log m). – Verifica m volte se si ha un ciclo. Determinare

l’esistenza di un ciclo può essere svolto in O(log n)

– In totale O(m log m) = O(m log n)

• L’esecuzione è identica all’algoritmo di Boruvska


Algoritmo di Prim / 1

• L’insieme A forma ad ogni passo una singola componente connessa

• Inizialmente A contiene {u,v} tale che (u,v) è l’arco di costo minimo.

• Ad ogni passo si inserisce in A l’arco di costo minimo che attraversa il taglio indotto da A.


Algoritmo di Prim /2• L’implementazione di Prim è simile a Dijkstra

con Q=A. Un Heap R memorizza il peso minimo di un arco che connette un nodo di R ad un nodo di A.

• Ad ogni passo un nodo v di minima priorità è inserito in A (e rimosso dall’Heap R)

• Per tutti i nodi u in R adiacenti a v si aggiorna la priorità di u se d(v,u) è minore della priorità corrente di u.

• Complessità: O(m log n) per l’aggiornamento della priorità che può essere svolto m volte.


Algoritmo di Prim / 3PrimAlg(grafo graph, vertice s)

A = {s};R = tutti i vertici/s;for tutti i vertici v rank(v)=min{d(s,v), };while R!=0 estrai vertice v in R con minimo rank(v)=d(r,v) ; A = A v; pred(u) = v;

for tutti i vertici u in R adiacenti ad v if rank(u)>d(v,u) rank(u) = d(v,u);

Ar


a

b

h

c d

g

e

f

i

8 7

9

1021

8

4

11 1442

67

a

b

h

c d

g

e

f

i

1 2

47

5

3

6

8

Esecuzione dell’Algoritmo

di Prim

La numerazione indica l’ordine di selezione degli archi del MST

Grafi

Documents

Transcript of Grafi