1 Problemi di percorso I ponti di Königsberg Grafi

(1)

Ugo de' Liguoro - Algoritmi e Seprimentazioni 03/04 Lez. 18

Grafi

Rappresentazione e visita Ordinamento topologico

I ponti di Königsberg

Non è possibile raggiungere A, B, C, D attraversando esattamente una volta

i 7 ponti sul fiume Pregel

L. Eulero (1736)

Problemi di percorso

(2)

Orari aerei e ferroviari

La struttura dei servizi

Telecomunicazioni

(3)

Reti di calcolatori

Architettura di un calcolatore

Che cos’è un grafo?

Archi = coppie di nodi Nodi

G = (N, A)

(4)

Grafi orientati

) , ( N A G =

N N

A ⊆ × L’ordine conta:

(a, b) ≠ (b, a)

Grafi orientati

) , ( N A G =

k i A a a a a

a , , ,

k

t.c. (

i

,

i₊

) ∈ per 1 ≤ <

:

cammino

1 2

K

1

Grafi orientati

k i A a a a a

a , , ,

_k

t.c. (

_i

,

_i₊

) ∈ per 1 ≤ <

:

cammino

₁ ₂

K

₁

k i a a a a

a a a

i i k

k

<

≠

= , ma

₊

se 1 t.c.

, , , cammino : ciclo

1 1

2

1

K

Questo non è

un ciclo

Questo è un ciclo

(5)

Grafi non orientati

} , : } ,

{{ a b a b N

A ⊆ ∈

Gli archi non hanno un verso

Grafi non orientati

distinti tutti sono archi gli

1 per } , {

t.c.

, , , : catena

1 2 1

k i A a a

a a a

i i

k

<

≤

+

∈ Questa è una K

catena

Grafi non orientati

k k

a a a a a

1

=

2 1

salvo ripetuti nodi sono ci non

t.c.

, , , catena una :

circuito K

Se questo ha la forma {a,b}, {b,a}

dunque non è un ciclo (e neppure un catena)

Questo è un

circuito (anche

detto “cricca”)

(6)

Rappresentazioni dei grafi

1 2

3 4

N = {1,2,3,4}

A = (1,2), (1,3), (3,2), (2,4)



 









 







0 0 0 0

0 0 1 0

1 0 0 0

0 1 1 0

 

 ∈

= 0 altrimenti ) , ( se ) 1 ,

( a a A

j i

M

ⁱ ^j

1 2 3 4

Questa è una matrice di adiacenza

Come si rappresenta un grafo in memoria?

Rappresentazioni dei grafi

1 2

3 4

N = {1,2,3,4}

A = (1,2), (1,3), (3,2), (2,4)



 









 







0 0 0 0

0 0 1 0

1 0 0 0

0 1 1 0 1 2 3 4

1 2 3 4

2 3

4 2 1 2 3

4 Liste di

adiacenza Non sono altro che

una matrice di adiacenza sparsa

Rappresentazioni dei grafi

Esistono altre rappresentazioni, tra cui le “matrici di incidenza

nodi-archi”

Un po’ complicate, richiedono spazio O(nm) (n vertici ed m archi) e sono utili

solo per particolari problemi

(7)

Visita di un grafo

1 2

3 4

1 3 2

4

1

3

2 4 Una visita di un grafo G = (N, A) è un insieme di cammini in G con origine in uno stesso stesso vertice.

Una visita è dunque un albero, i cui vertici sono contenuti in N ed i cui archi sono contenuti in A (è un sottografo di G), la cui radice è l’origine dei cammini.

Una visita di un grafo G = (N, A) è un insieme di cammini in G con origine in uno stesso stesso vertice.

Una visita è dunque un albero, i cui vertici sono contenuti in N ed i cui archi sono contenuti in A (è un sottografo di G), la cui radice è l’origine dei cammini.

Visita di un grafo

Come fare per visitare un grafo?

Possiamo adottare le stesse tecniche già usate per gli alberi: partiamo da un nodo e

procediamo in ampiezza/profondità

Un problema: e i cicli?

Se la ricerca entra nel ciclo dei nodi blu non troverà mai

il nodo rosso!!

Conviene ricordare quali nodi abbiamo

visitato

(8)

Schema di una visita

Visit (G, r) // Pre: r ∈ N[G] (i nodi di G) F ← {r}, V ← {r} // V = visitati

root(T) ← r while F ≠ ∅ do

scegli v ∈ F, F ← F – {v}

foreach u ∈ N[G] – V and (v, u) ∈ A[G] do V ← V ∪ {u}, F ← F ∪ {u}, T ← T ∪ {(u, v)}

return T

Partizioni per una visita

G v

Interno = V – F Frontiera = F Esterno = N – V

BFS o DFS?

Visit (G, r) // Pre: r ∈ N[G] (i nodi di G) F ← {r}, V ← {r} // V = visitati

root(T) ← r while F ≠ ∅ do

// Invariante?

… return T

BFS: La frontiera contiene vertici la cui “distanza” da r differisce al più di 1

DFS: la sequenza dei vertici inseriti

in V costituisce una visita in

profondità in ordine anticipato di T

(9)

BFS o DFS?

Visit (G, r) // Pre: r ∈ N[G] (i nodi di G) F ← {r}, V ← {r} // V = visitati

root(T) ← r while F ≠ ∅ do

scegli v ∈ F, F ← F – {v}

foreach u ∈ N[G] – V and (v, u) ∈ A[G] do V ← V ∪ {u}, F ← F ∪ {u}, T ← T ∪ {(u, v)}

return T

Tutto dipende da come si sceglie v ∈ F

BFS o DFS?

scegli v ∈ F, F ← F – {v}

BFS: si sceglie il vertice rimasto in F il più a lungo

Allora F è una coda

DFS: si sceglie il vertice posto in F per ultimo

Allora F è una pila

BFS e BFS

BFS (G, r)

F ← NewQueue(), Enqueue(r, F) V ← {r}, root(T) ← r while not IsEmptyQueue(F) do

v ← Dequeue(F) foreach u ∈ N[G] – V and

(v, u) ∈ A[G] do Enqueue(u, F) V ← V ∪ {u}, T ← T ∪ {(u, v)}

return T

DFS (G, r)

F ← NewStack(), Push(r, F) V ← {r}, root(T) ← r while not IsEmptyStack(F) do

v ← Top(F), Pop(F) foreach u ∈ N[G] – V and

(v, u) ∈ A[G] do Push(u, F) V ← V ∪ {u}, T ← T ∪ {(u, v)}

return T

(10)

Visita in ampiezza esempio.

1 2

4 5 6

3 Frontiera = ¹ Albero = ¹

Visita in ampiezza esempio.

1

2 4 5 6

3 Frontiera = ^{2 4} ¹

4 2

Albero =

Visita in ampiezza esempio.

1 2

4

5 6

3 Frontiera = ⁵ ¹

4 2

Albero =

5

(11)

Visita in ampiezza esempio.

1 2

4 5

6

3 Frontiera = ^{3 6} ¹

4 2

Albero =

5 3 6

Visita in ampiezza esempio.

1 2

4 5 6

3

Frontiera = ∅ ¹

4 2

Albero =

5 3 6

Visita in profondità esempio.

1 2

4 5 6

3 Frontiera = ¹ Albero = ¹

(12)

Visita in profondità esempio.

1 2

4 5 6

3 Frontiera = ^{2 1} Albero = ¹

2

Visita in profondità esempio.

1 2

4 5 6

3 Frontiera = 5 2 1 Albero = 1

2 5

Visita in profondità esempio.

1 2

4 5 6

3 Frontiera = 3 5 2 1 Albero = 1 2

5

(13)

Visita in profondità esempio.

1 2

4 5 6

3

Frontiera = 5 2 1 Albero = 1

2 5 3

Visita in profondità esempio.

1 2

4 5 6

3

Frontiera = 6 5 2 1 Albero = 1 2

5 3 6

Visita in profondità esempio.

1 2

4 5

6

3

Frontiera = 5 2 1 Albero = 1

2 5

3 6

(14)

Visita in profondità esempio.

1 2

4

5 6

3

Frontiera = ^{2 1} Albero = ¹

2 5

3 6

Visita in profondità esempio.

1

2

4

5 6

3

Frontiera = ¹ Albero = ¹

2 5

3 6

Visita in profondità esempio.

1

2

4

5 6

3

Frontiera = ^{4 1} Albero = ¹

2

5

4

(15)

Visita in profondità esempio.

1

2

4 5 6

3

Frontiera = ¹ Albero = ¹

2 5

3 6

4

Visita in profondità esempio.

1 2

4 5 6

3

Frontiera = ^∅ Albero = ¹

2 5

3 6

4

Ordinamento topologico

(16)

Ordinamento topologico

1 2

3 4

1, 3, 2, 4 è un ordinamento topologico di G;

1, 2, 4, 3 non lo è perché (3,2) ∈ A mentre 3 segue 2 in questa permutazione.

G

Dato un grafo finito orientato G = (N, A), un ordinamento topologico di G consiste in una permutazione v

1

,…,v

n

di N tale che:

(v

_i

, v

_j

) ∈ A ⇒ i ≤ j.

Dato un grafo finito orientato G = (N, A), un ordinamento topologico di G consiste in una permutazione v

₁

,…,v

_n

di N tale che:

(v

i

, v

j

) ∈ A ⇒ i ≤ j.

Allora G non deve contenere cicli

Visita in profondità rivista

DFS (G)

foreach v ∈ N[G] // inizializza i colori Colore[v] ← Bianco; Tempo[v] ← indef tempo ← 0; // variabile globale

foreach u ∈ N[G] // itera la visita in prof.

if Colore[u] = Bianco then DFS-Visit(u)

DFS-Visit (u)

Colore[u] ← Grigio; tempo ← tempo + 1 foreach (u,v) ∈ A[G]

if Colore[v] = Bianco then DFS-Visit(v);

Colore[u] ← Nero

Tempo[u] ← tempo, tempo ← tempo + 1

Tempi e precedenze

Teorema. Sia G = (N, A) un grafo orientato aciclico:

se (u, v) ∈ A, con u ≠ v, allora dopo DFS(G) Tempo[u] > Tempo[v].

Teorema. Sia G = (N, A) un grafo orientato aciclico:

se (u, v) ∈ A, con u ≠ v, allora dopo DFS(G) Tempo[u] > Tempo[v].

Per assurdo sia (u, v) ∈ A, ma Tempo[u] < Tempo[v]:

Al tempo t = Tempo[u] si aveva Colore[u] = Nero,

Colore[v] = Bianco oppure Grigio

(17)

Tempi e precedenze

Teorema. Sia G = (N, A) un grafo orientato aciclico:

se (u, v) ∈ A, con u ≠ v, allora dopo DFS(G) Tempo[u] > Tempo[v].

Teorema. Sia G = (N, A) un grafo orientato aciclico:

se (u, v) ∈ A, con u ≠ v, allora dopo DFS(G) Tempo[u] > Tempo[v].

Bianco: (u, v) ∈ A implica che le adiacnze di u non sono tutte esplorate Grigio: esiste un cammino da v