Dati :

un grafo diretto G = (V, E) con pesi (capacità) wij associati agli archi

● un nodo s V, detto sorgente ● un nodo t V, detto pozzo

Problema : trovare la massima quantità di flusso che può essere

inviata da s a t rispettando ● le capacità degli archi

● il vincolo che nei nodi intermedi il flusso entrante deve essere uguale al flusso uscente

Problema del Massimo Flusso

1

2 4

6

53

7

8

5

4 5

4

1

9

Sorgente : s = 1

Pozzo : t = 6

Grafo G

i jwij

Si dice flusso una funzione x: E R|E|, tale che per ogni nodo intermedio i V {s, t}

iOutj

ijiInj

ji xx

● Si dice valore del flusso, denotato con v(x) R, la quantità di flusso immessa in rete del nodo sorgente s

● Ossia nei nodi intermedi flusso entrante = flusso uscenteQueste relazioni sono dette “vincoli di conservazione del flusso”

v (x)= ∑j∈Out (s)

xsj− ∑j∈ In (s)

x js

● Valendo i vincoli di conservazione del flusso ai nodi intermedi, il flusso immesso in rete nel nodo sorgente s equivale al flusso prelevato dalla rete nel nodo pozzo t

● Il flusso x si dice ammissibile se per ogni arco (i, j) E

0 xij wij , (i, j) V (vincolo di non negatività)

Problema del Massimo Flusso :

determinare il flusso x ammissibile tale che per ogni altro flusso ammissibile x', si ha v(x') ≤ v(x)

v (x)= ∑j∈In (t )

x jt− ∑j∈Out(t )

x tj

1

2 4

6

53

6, 7

2, 8

0, 5

4, 4 1, 5

4, 4

1, 1

5, 9

Esempio di flusso ammissibile

i j

xij , wij

Il vettore x

1) è un flusso : soddisfa i vincoli di conservazione del flusso ai nodi 2) è ammissibile : soddisfa i vincoli di non negatività e di capacità

● Valore del flusso : v = 6

quantità immessa nella sorgente s e prelevata nel pozzo t

● L’arco (i, j) è detto

- vuoto se il flusso xij è nullo (coincide con il lower bound)

- saturo se il flusso xij è pari alla capacità wij (xij coincide con l’upper bound)

Nell’esempio:l’arco (1, 3) è vuotogli archi (2, 3), (3, 5) e (4, 6) sono saturi.

Flussi e tagli

Taglio s - t del grafo G :

partizione dell’insieme V dei nodi in due sottoinsiemi (Vs , Vt) con

s Vs e t Vt = V \ Vs

Gli archi che attraversano il taglio (che hanno un estremo in Vs

e l’altro in Vt ) sono a loro volta distinti in due sottoinsiemi:

• l’insieme E+(Vs, Vt) degli archi diretti del taglio (uscenti da un nodo di Vs ed entranti in un nodo di Vt)

E+(Vs, Vt) = {(i, j) E : i Vs , j Vt }

• l’insieme E

–(Vs, Vt) degli archi inversi del taglio (uscenti da un nodo di Vt ed entranti in un nodo di Vs)

E–(Vs, Vt) = {(i, j) E : i Vt , j Vs }

● Dato un flusso x, ad ogni taglio s-t è associato il flusso del taglio x(Vs, Vt ), dato dalla quantità di flusso che percorre gli archi diretti meno la quantità di flusso che percorre gli archi inversi

tsts VVEji

ijVVEjiijts xxVVx

,,,,

,

(valore netto tra quanto fluisce verso t e quanto ritorna verso s)

Flussi e tagli

●Ad ogni taglio s-t del grafo G è associata la capacità del taglio data dalla somma delle capacità degli archi diretti e denotata col simbolo w(Vs, Vt) :

ts VVEji

ijts wVVw,,

,

Teorema 1

Sia x flusso ammissibile di valore v(x). (Vs, Vt) taglio s - t del grafo G si ha:

a) v(x(Vs, Vt)) = v(x)

b) v(x) = v(x(Vs, Vt )) w(Vs, Vt)

ossia, il valore del flusso x(Vs, Vt) del taglio (Vs, Vt) • coincide con il valore del flusso v(x) • non supera mai la capacità w(Vs, Vt) del taglio

Pertanto, massimizzare il flusso equivale a trovare il taglio s-tdi capacità minima → Max flow = Min Cut

Flussi e tagli

Cammini aumentanti

● Siano

x : flusso ammissibile v(x) : valore del flusso x

● Il flusso ammissibile x si dice non ottimo se

● Riusciamo ad inviare altro flusso dalla sorgente s alla destinazione t.

● Tale flusso aggiuntivo è “instradato” lungo un cammino P da s a t.

1

2 4

6

53

6, 7

2, 8

0, 5

4, 4 1, 5

4, 4

1, 1

5, 9

Esempio 1 :

- cammino P su cui inviare nuovo flusso da s a t

P = { (1, 2), (2, 4), (4, 5), (5, 6) }

- capacità residua F del cammino P dato il flusso x :

F (P, x) = min { 7 6, 8 2, 5 1, 9 5 } = 1

s t

1

2 4

6

53

7, 7

3, 8

0, 5

4, 4 2, 5

4, 4

1, 1

6, 9

v = 7

Aumentando di 1 il flusso sul cammino P, si ottiene un nuovo flusso ammissibile di valore 7

● Un cammino P su cui sia possibile inviare nuovo flusso è detto cammino aumentante.

● I cammini aumentanti non sono necessariamente orientati

● possono essere composti sia da archi che vengono attraversati nel verso del loro orientamento (archi in avanti), sia da archi che vengono attraversati nel verso opposto (archi all'indietro)

P+ : insieme degli archi in avanti del cammino P

P– : insieme degli archi all'indietro del cammino P

● Consideriamo anche gli archi all'indietro per garantire i vincoli di conservazione del flusso quando serve ridurre il flusso esistente su un arco

Cammini aumentanti

Capacità residua F (P, x) del cammino aumentante P rispetto al flusso x :

F (P, x) = min { min{wij – xij : (i, j) P+}, min{xij : (i, j) P–}}

● È la massima quantità di flusso che - aggiunta agli archi in avanti di P non produce flussi maggiori delle capacità - sottratta agli archi all'indietro di P non produce flussi negativi

F (P, x) = 0, se almeno uno degli archi in avanti è saturo (xij = wij)

o almeno uno degli archi all'indietro è vuoto (xij = 0)

SE F (P, x) > 0 : il cammino è detto AUMENTANTE

Cammini aumentanti

● Se x è un flusso, per ogni scalare reale , il vettore x = x + è definito come segue

altrimenti

, se

, se

ij

ij

ij

ij

x

Pjix

Pjix

x

Che è un flusso quando ● F(P, x) ● Infatti, x soddisfa anche i vincoli di non negatività, di capacitàe di conservazione del flusso

Il cui valore è v(x) = v(x) + ,

0,,:,,,:, ijijij xEjiijwxEjijiE x

● Dato un flusso x per il grafo G, come determinare un cammino

aumentante P?- si introduce il grafo residuo Gx = ( V, Ex ) rispetto al flusso x, dove

Ossia

un arco (i, j) non saturo e non vuoto in G (0 < xij < wij)

è rappresentato in Gx da una coppia di archi

• un arco (i, j) di capacità wij – xij

• un arco (j, i) di capacità xij

un arco (i, j) vuoto (xij = 0) [ saturo (xij = wij) ] in G

è rappresentato in Gx da un arco (i, j) [(j, i)] di capacità wij [0]

Determinazione di un cammino aumentante

1

2 4

6

53

1

6

50 4

0

0

4

Esempio di grafo residuo

0

6

1

2 4

6

53

6, 7

2, 8

0, 5

4, 4 1, 5

4, 4

1, 1

5, 9

4

4 1

5

1

2

i j

xij , wij

● Un cammino aumentante può essere determinato

mediante una visita BFS del grafo residuo Gx a partire da s

Possono presentarsi 2 casi:

1) la visita raggiunge t :

risulta individuato un cammino aumentante che permette di

costruire un nuovo flusso x’ di valore strettamente maggiore

al valore di x

2) la visita non raggiunge t :

su V, insieme dei nodi di G, si definisce la partizione ( Vs, Vt ) :

Vs : sottoinsieme dei nodi raggiunti dalla visita (contiene s)

Vt : sottoinsieme dei nodi non raggiunti dalla visita (contiene t)

Determinazione di un cammino aumentante

● Quando la visita del grafo residuo Gx non raggiunge il nodo t,

il taglio s - t definito dalla partizione (Vs, Vt) è tale che

v(x(Vs, Vt )) = w(Vs, Vt)

● In tale taglio s-t, infatti

• tutti gli archi di E+ (Vs, Vt) sono saturi

• tutti gli archi di E– (Vs, Vt) sono vuoti

- altrimenti l’algoritmo avrebbe potuto visitare un ulteriore nodo

● Si prova che tale taglio ha capacità minima tra tutti i tagli s – t● Quindi per l'equivalenza tra massimo flusso e taglio minimo nella rete residua, abbiamo anche trovato il flusso massimo

Determinazione di un cammino aumentante

Algoritmo di Ford-Fulkerson (o dei cammini aumentanti)

Procedure [ x, Vs , Vt ] = FF (G, s, t,) :

1. Inizializzazione : x = 0; // vettore nullo

dj = NULL per ogni j // dj : capacità del cammino da s a j

2. do

3. Calcola Gx

4. [P , F ] = Trova_cammino_aumentante(Gx, s, t, x)

4. Aumenta_Flusso(G, s, t, x, P, F )

5. while

6. end

P≠∅

Procedura Trova_cammino_aumentante (G, s, t, x ) : ➢ cerca di determinare un cammino aumentante P da s a t, dato il flusso x :

➢ è una visita del grafo residuo Gx a partire dall’origine s➢ insieme a P determina la capacità F = F (P, x) di P,

come minimo delle capacità dj del cammino da s a j sull’albero

Ts = (Vs, Es) determinato fino a quel momento

Quando si giunge al nodo j provenendo dal nodo i:

- se si è usato l’arco in avanti, allora si pone

dj = min { di , wij – xij }

- se si è usato l’arco all'indietro:

dj = min { di , xij }

confronto tra capacità del cammino s-i ecapacità residua dell’arco (i, j)

confronto tra capacità del cammino s-i e flusso dell’arco (i, j)

Procedura Trova_cammino_aumentante (G, s, t, x ) :

• se il cammino esiste:

la procedura Trova_cammino_aumentante

fornisce P e = (P, x))

• se il cammino non esiste:

la procedura restituisce un taglio s-t

di capacità minima, che certifica l’ottimalità del flusso

➢ Procedura Aumenta_Flusso(G, s, t, x, P, )

• Aggiorna il flusso x inviando sul cammino P la quantità di flusso F

• Ciò è fatto percorrendo il cammino in senso inverso da t a s, per mezzo della funzione predecessore, e modificando il flusso

altrimenti

, se

, se

ij

ij

ij

ij

x

Pjix

Pjix

x

Per individuare il verso di percorrenza, porre:

- pj = i : se j viene visitato a partire da i mediante l’arco in avanti

- pj = – i : se j viene visitato mediante l’arco all'indietro.

Dati• un insieme S di nodi sorgente • un insieme T di nodi pozzo

Per individuare il massimo flusso che può essere inviato dai nodi sorgente ai nodi pozzo si :

● amplia il grafo G = (V, E) aggiungendo una super-sorgente s e un super-pozzo t ottenendo G’ = (V’, E’)

V’ = V {s, t} E’ = E { (s, j) : j S} {(i, t) : i T }

● gli archi che collegano la “super-sorgente” a tutti i nodi in S ed il “super-pozzo” a tutti i nodi in T hanno capacità infinita

Flusso massimo con più sorgenti/pozzi

Esercizio

1) Scrivere una funzione MATLAB che preso in input un oggetto grafo diretto pesato G, un flusso x, restituisce il grafo residuo Gx

2) Usando il codice al punto 1) e quello per realizzare una visita BFS di un grafo diretto, scrivere una funzione MATLAB che dato un grafo diretto pesato, una sorgente s, un pozzo t e un flusso x, calcoli un cammino aumentante per il flusso x

3) Usando gli esercizi 1 e 2, implementare in MATLAB l'algoritmo di Ford-Fulkerson