1

Esercizio Supponiamo che il grafo G abbia più alberi di connessione minimi. Mostrare che due alberi di connessione minimiT e T' non solo hanno lo stesso peso totale ma anche i pesi dei singoli archi sono a due a due gli stessi. In altre parole se w1 w2 ... wn è la lista ordinata dei pesi degli archi di T e w'1 w'2 ... w'n è la lista ordinata dei pesi degli archi di T' allora wi = w'i per ogni i.

Esercizio 46

2

Soluzione w1 ≤ w2 ≤ ... wi ≤ ... wn

E(T) : a1 a2 ... ai ... an w’1 ≤ w’2 ≤ ... w’i ≤ ... w’n

E(T’) : a1 a2 ... ai ... an

Se ai=a’i per ogni i abbiamo finito.Altrimenti, sia i il primo indice per cui ai≠a’iMostriamo che wi=w’i.Supponiamo w’i>wiai T’∉ non puo’ stare prima di a’i perche sono tutti uguali non puo stare dopo a’i perche wi<w’iAllora T’ {ai} contiene un ciclo∪Questo ciclo contiene almeno un arco a’j non TNon puo’ essere w’j>wi altrimenti w(T’-a’j+ai)<w(T’)Quindi w’j≤wi a’j T. Assurdo∈

Esercizio 46

Simmetricamente non puo essere w’i<wi. Quindi wi=w’i

Costruiamo MST T” con

E(T”): a”1 a”2 ... a”i ... a”n tale che

w”j=w’j per ogni j e a”j=aj per ogni j=1..i

Due casi

1) wi=w’i e esiste a’j, con j>i, a’j=ai. Allora scambio a’i e a’j

2) wi=w’i e ai ∉ T’quindi se aggiungo ai a T’ ottengo un ciclo

tale ciclo ha un arck a’j che non e’ in T’

tale arco non puo avere peso <wi perche’ tutti gli archi di peso <wi sono in comune

Non puo’ avere peso >wi altrimenti scambiandoli otterrei un labero di peso inferiore

deve essere w’j=wi=w’i

scambio a’i e a’j e poi rimpiazzo a’i con ai

3

4

Cammini minimi

Sia G = (V,E) un grafo orientato ai cui archi è associato un peso w(uv).

Cammini minimi

k

i ii vvwpw1 1 )()(

Il peso di un cammino p = v0,v1,...,vk è la somma dei pesi degli archi che lo costituiscono.

5

altrimenti

da ileraggiungib se:)(min),(

uvvupwvu

p

Il peso di un cammino minimo da un vertice u ad un vertice v è definito nel seguente modo:

Un cammino minimo da u a v è un cammino p da u a v di peso w(p) = (u,v).

Nel problema dei cammini minimi viene appunto richiesto di calcolare i cammini minimi.

6

1) Cammini minimi da un’unica sorgente a tutti gli altri vertici.

2) Cammini minimi da ogni vertice ad un’unica destinazione.

3) Cammini minimi da un’unica sorgente ad un’unica destinazione.

4) Cammini minimi da ogni vertice ad ogni altro vertice.

Vi sono quattro versioni del problema:

7

Noi risolveremo la prima istanza.

La seconda istanza si risolve simmetricamente.

La terza si può risolvere usando la soluzione della prima (non si conosce a tuttora alcun algoritmo che risolva la terza istanza in tempo asintoticamente migliore della prima).

La quarta si può risolvere usando la soluzione della prima per ogni vertice del grafo ma in genere si può fare di meglio.

8

Archi di peso negativo. In alcuni casi il peso degli archi può anche essere negativo.

Questo non crea problemi nella ricerca dei cammini minimi da una sorgente s a meno che non ci siano cicli di peso negativo raggiungibili da s.

Se u è raggiungibile da s con un cammino che passa per un vertice v di un ciclo negativo allora esistono cammini da s a u di pesi sempre minori e il peso di un cammino minimo (s,u) non è definito.

In questo caso poniamo (s,u) = - .

9

5s

3

-

-

11

-1

0

-

-8

3

2

-6

3

-3

6

-4

2

53

10

Sottostruttura ottima dei cammini minimi.

Se il cammino p1k = v1,...,vk è minimo sono minimi anche tutti i sottocammini pij = vi,...,vj , 1≤ i ≤ j ≤ k.

Dimostrazione. Se esistesse un cammino qij di peso minore di pij sostituendo in p1k il sottocammino pij con qij si otterrebbe un cammino q1k da v1 a vk di peso minore di p1k. Impossibile se p1k è minimo.

Sottostruttura ottima

11

Cicli.

Abbiamo visto che un cammino minimo non può contenere un ciclo negativo.

Non può contenere neppure un ciclo positivo, altrimenti rimuovendo il ciclo otterremmo un cammino di peso inferiore.

Può contenere un ciclo di peso zero ma rimuovendo tale ciclo otteniamo ancora un cammino minimo.Possiamo quindi limitarci a considerare cammini minimi semplici. Quindi lunghezza n-1.

12

Rappresentazione dei cammini minimi.

In genere ci interessa calcolare non solo i pesi dei cammini minimi ma anche i cammini minimi stessi.

Siccome i cammini minimi hanno sottostruttura ottima possiamo rappresentarli con un albero dei cammini minimi G' = (V',E') che è un albero radicato in s con V' insieme dei vertici raggiungibili da s e tale che per ogni v V' l’unico cammino da s a v in G' è un cammino minimo in G.

13

Grafo dei predecessori.

Gli algoritmi per cammini minimi mantengono un campo π[v] che punta al vertice precedente in un cammino minimo da s a v.

I campi π[v] definiscono il sottografo dei predecessori:

uvEuvE

nilvVvsV

EVG

:

:

),(

alla fine dell’algoritmo Gπ deve essere un albero di cammini minimi.

14

Tecnica del rilassamento.

Gli algoritmi che studieremo usano la tecnica del rilassamento.

Aggiungiamo ad ogni vertice v del grafo un campo d[v] che durante tutta l’esecuzione dell’algoritmo è un limite superiore per (s,v) mentre alla fine è uguale a (s,v).

Tecnica del rilassamento

15

L’inizializzazione dei campi π[v] e d[v] è la stessa per tutti gli algoritmi.

Inizializza(G, s) G grafo pesato sugli archi

for “ogni v V[G]” do π[v] nil d[v] d[s] 0

17

Il rilassamento rispetto ad un arco uv consiste nel controllare se allungando il cammino da s a u con l’arco uv è possibile trovare un cammino da s a v migliore di quello trovato finora.

Rilassa(uv) if d[v] > d[u] + w(uv) then d[v] d[u] + w(uv) π[v] u

18

Disuguaglianza triangolare. Per ogni arco uv

Proprietà dei cammini minimi e del rilassamento

Inoltre, dopo l’inizializzazione ed un numero qualsiasi di rilassamenti valgono le seguenti:

)(),(),( uvwusvs

Vertici non raggiungibili. Se v non è raggiungibile da s allora d[v] = (s,v) = .

Limite superiore. d[v] (s,v) e non appena d[v] diventa uguale a (s,u) esso non cambia più.

19

Convergenza. Se u precede v in un cammino minimo e d[u] = (s,u) prima del rilassamento dell’arco uv, allora d[v] = (s,v) dopo tale rilassamento.

Rilassamento del cammino. Se p = v0,...,vk è un cammino minimo da s = v0 a vk e si esegue una sequenza di rilassamenti durante la quale vengono rilassati gli archi di p nell’ordine v0v1,...,vk-1vk allora d[vk] = (s,vk).Sottografo dei predecessori. Quando d[v] = (s,v) per ogni vertice v, l’albero dei predecessori è un albero dei cammini minimi.

20

Algoritmo di Bellman-Ford

Algoritmo di Bellman-Ford

CammMinimiBellmanFord(G, s) G grafo pesato sugli archi

Inizializza(G, s) for i 1 to n - 1 do for “ogni uv E[G]” do Rilassa(uv) for “ogni uv E[G]” do if d[v] > d[u] + w(uv) then return false return true

true sse non ci sono cicli di peso negativo

21

u/

2

5

6

s/0

y/x/

v/

7

8 7

-2

9

-3

-4

u/6

x/7

ordinearchi:

uvuxuyvuxvxyyvyssusx

v/11

y/2

v/4u/2

y/-2

22

Complessità. La complessità dell’algoritmo di Bellman-Ford è O(m n).

Correttezza. Supponiamo dapprima che non ci siano cicli negativi raggiungibili da s.

Se v non è raggiungibile da s sappiamo che d[v] = (s,v) = e questo rimane vero anche dopo tutti i rilassamenti effettuati nel primo ciclo for.

Se v è raggiungibile da s esiste un cammino minimo da s a v di lunghezza minore o uguale ad n-1.

23

Il primo ciclo for rilassa tutti gli archi per n-1 volte. Quindi la sequenza dei rilassamenti contiene come sottosequenza i rilassamenti degli archi del cammino minimo nell’ordine dal primo all’ultimo. Pertanto alla fine vale d[v] = (s,v).

)()(),(),( uvwuduvwusvsvd per ogni vertive v e quindi il secondo ciclo for termina e l’algoritmo ritorna true.

Per la disuguaglianza triangolare

24

Supponiamo ci sia un ciclo negativo v0,...,vk con vk = v0 raggiungibile da s e supponiamo per assurdo che l’algoritmo ritorni true.

Questo è possibile soltanto se per ogni i = 1,…,k )( 11 iiii vvwvdvd

Sommando su tutti gli i si ottiene

k

iii

k

ii

k

ii vvwvdvd

11

11

1

)(

Le prime due sommatorie sono uguali e la terza è il peso del ciclo che è negativo. Assurdo.

25

Esercizio Modificare l’algoritmo di Bellman e Ford in modo che esso ponga d[v] = - per ogni vertice v che è raggiungibile da s con un cammino che contiene un ciclo negativo.

esercizio 49

CammMinimiBellmanFord(G, s) G grafo pesato sugli archi

Inizializza(G, s) for i 1 to n - 1 do for “ogni uv E[G]” do Rilassa(uv) for “ogni uv E[G]” do if d[v] > d[u] + w(uv) then d[v]-∞ return true

26Cammini minimi in DAG

Cammini minimi in grafi aciclici.

Rilassando gli archi di un grafo aciclico in ordine topologico possiamo calcolare i cammini minimi in tempo O(n + m).L’algoritmo è il seguente:

CammMinimiDAG(G, s) G grafo diretto aciclico pesato sugli archi OrdinamentoTopologico(G, OrdTop) Inizializza(G, s) for i 1 to n - 1 do u OrdTop[i] for “ogni v Adj[u]” do Rilassa(uv)

27

r/ 25

3

s/0

4

-2

16

2

-1t/ u/ v/ x/t/2 u/6 v/6 x/4v/5 x/3

28

Complessità.

La complessità dell’algoritmo è O(n + m).

Correttezza.

Sia v un vertice qualsiasi raggiungibile da s e sia

s = u0, u1, ..., uk = v

un cammino minimo da s a v.

L’algoritmo rilassa gli archi del cammino nell’ordine u0u1, u1u2, ..., uk-1uk e quindi alla fine d[v] = (s,v).

29

Algoritmo di Dijkstra

Grafo orientato pesato con pesi non negativi

L’algoritmo di Dijkstra mette i vertici in una coda con priorità Q ordinata rispetto a d[v].

Algoritmo di Dijkstra

CammMinimiDijkstra(G, s) G grafo pesato sugli archi

Inizializza(G, s) Q V[G] while not Empty(Q) do u ExtractMin(Q) for “ogni v Adj[u]” do Rilassa(uv)

30

Il rilassamento può diminuire d[v].

Siccome v è inserito in una coda con priorità per diminuire il valore di d[v] dobbiamo effettuare una chiamata a DecreaseKey.

La procedura Rilassa diventa quindi:

Rilassa(uv) if d[v] > d[u] + w(uv) then DecreaseKey(v, d[u]+w(uv) ) π[v] u

31

u/

7

1

10

s/0

y/x/

v/

5

2 6 4

2

93s/0

u/10

x/5x/5

u/8

y/7

v/14

y/7

v/13u/8 v/9v/9

32

Complessità. Escludendo le operazioni sulla coda Q l’algoritmo richiede tempo O(n + m).

Sulla coda vengono eseguite n operazioni Insert, n operazioni ExtractMin e al più m operazioni DecreaseKey.

Se implementiamo la coda Q con un mucchio binomiale le operazioni sulla coda richiedono tempo O((n + m) log n).

Se usiamo mucchi di Fibonacci richiedono tempo O(n log n + m).

33

Correttezza.

Dobbiamo mostrare che alla fine d[v] = (s,v) per ogni vertice v.

Per far questo ci basta mostrare che d[v] = (s,v) quando il vertice viene estratto dalla coda Q.

Infatti ogni vertice viene prima o poi estratto dalla coda e dal momento in cui d[v] = (s,v) il valore di d[v] non può più cambiare.

34

Assumiamo, per assurdo, che u sia il primo vertice estratto dalla coda per cui d[u] (s,u) e sia S l’insieme dei vertici estratti prima di u.

Siccome il primo vertice estratto dalla coda è la sorgente s e d[s] = 0 = (s,s) l’insieme S contiene s e quindi u s.

Per la proprietà del limite superiore d[u] (s,u) e quindi d[u] > (s,u).

Dunque (s,u) < ed esiste un cammino minimo p da s a u.

35

Sia y il primo vertice del cammino p che non appartiene ad S, sia x il vertice precedente e suddividiamo il cammino p in un cammino p1 da s a x, l’arco xy e il cammino p2 da y a u.

s

x y

uS

p1

p2

36

Quando il vertice x è stato estratto da Q avevamo che d[x] = (s,x) e siccome a quel punto è stato rilassato l’arco xy anche d[y] = (s,y).

Siccome y precede u nel cammino minimo p e non ci sono archi di peso negativo avremo che (s,u) (s,y) e quindi:

d[u] (s,u) (s,y) = d[y]

Ma u è il vertice estratto dalla coda e quindi

d[u] = (s,u) = (s,y) = d[y]

Assurdo.

37

Esercizio Descrivere un algoritmo che dato un grafo orientato aciclico pesato sugli archi ed un vertice s calcola i cammini massimi da s ad ogni altro vertice.

esercizio 50

38

Esercizio 51 Sono date n task a1,...,an con tempi di esecuzione t1,...,tn. Tali task si possono eseguire in parallelo utilizzando un numero sufficiente di processori.L’esecuzione deve però rispettare dei vincoli di propedeuticità rappresentati mediante coppie aiaj il cui significato è “ai deve essere finita prima di iniziare l’esecuzione di aj”.Descrivere un algoritmo efficiente che calcola il tempo minimo necessario per eseguire tutte le task.

esercizio 51*

39

Esercizio Una scatola rettangolare a d dimensioni è definita dalle dimensioni x1, x2, ..., xd dei suoi lati.La scatola X di lati x1, x2, ..., xd puo essere racchiusa nella scatola Y di lati y1, y2, ..., yd se esiste una permutazione degli indici 1,2,...,d tale che x(1) y1, x(2) y2,..., x(d) yd .

esercizio 52

40

a) verificare che la relazione “essere racchiudibile” è transitiva.

b) trovare un metodo efficiente per testare se una scatola è racchiudibile in un’altra scatola.

c) trovare un algoritmo efficiente che dato un insieme di n scatole S1, S2, ..., Sn a d dimensioni, calcola la più lunga sequenza Si1

, Si2, ..., Sik

di

scatole racchiudibili una nell’altra.