Capitolo 8

Flussi massimi

8.1 Definizioni fondamentali

Problemi di flusso intervengono ogni volta che si intenda inviare quantita di un bene da un puntodetto origine o sorgente a un altro punto detto destinazione o pozzo. Il bene puo passare ancheper punti intermedi (senza stazionarvi) prima di raggiungere la sua destinazione: dunque tuttocio che arriva in un punto intermedio dovra anche ripartire. Esempi del problema sono i flussidi beni materiali o di pacchetti di dati sulla rete internet. I problemi di flusso possono essereagevolmente modellati e manipolati mediante la teoria dei grafi.

Dato un grafo orientato G(N,A), un vettore di capacita c|A| associate agli archi, un nodosorgente s e un nodo pozzo t di G, si definisce flusso s-t un vettore x ∈ IR|A| che soddisfa ivincoli (8.1), (8.2), (8.3), (8.4) descritti dettagliatamente pi avanti.

Di seguito, la componente xuv del vettore di flusso corrispondente all’arco uv verra indicatacome flusso sull’arco uv.

La prossima figura descrive una comoda rappresentazione del flusso su un arco e della ca-pacita dell’arco stesso; in particolare, la coppia (x, c) rappresentata accanto all’arco esprime,nell’ordine, il flusso sull’arco e la sua capacita.

vu(1,2)(xuv,cuv)

Figura 8.1: Rappresentazione del flusso e della capacita su un arco

Il primo vincolo (8.1) esprime il fatto che il flusso su ogni arco e positivo o nullo.

0 ≤ xuv per ogni uv ∈ A (8.1)

78

Il prossimo vincolo di capacita esprime invece che il flusso su ogni arco non eccede la capacitadell’arco stesso:

xuv ≤ cuv per ogni uv ∈ A (8.2)

Il vincolo (8.3) e il cosiddetto vincolo di conservazione del flusso ed esprime il fatto che, neinodi intermedi, il flusso entrante e uguale al flusso uscente.

uv∈δ−G(v)xuv −

vu∈δ+G(v)xvu = 0 (8.3)

L’ultimo vincolo (8.4) forza i flussi entranti in s e i flussi uscenti da t a essere nulli (nullaentra in s e nulla esce da t):

us∈δ−G (s)xus =

tu∈δ+G(t)xtu = 0 per ogni v ∈ N − {s, t} (8.4)

Dunque, un vettore x ∈ IR|A| che soddisfa i vincoli 8.1,8.2, 8.3, 8.4 e detto flusso s-t. Ungrafo capacitato e un suo flusso s-t sono mostrati in Figura 8.2.

3

1

33

2

2

1s

1

2 3

4

t

1(2,3)

(1,1)

(1,1)

(2,3)(3,3)

(2,2)

(2,2)

(1,1)s

1

2 3

4

t

Figura 8.2: Un grafo con capacita e un flusso s-t

Dato F ⊆ A, si indica con x(F ) = uv∈F xuv. Con questa posizione, i vincoli (8.3), (8.4)possono essere riscritti:

x(δ−G(v))− x(δ+G(v)) = 0 per ogni v ∈ N − {s, t}x(δ−G(t))− x(δ+G(t)) = x(δ−G(t)) = ft(x) flusso entrante in tx(δ−G(s))− x(δ+G(s)) = −x(δ+G(s)) = −fs(x) flusso uscente da s

(8.5)

Si osservi che ogni arco uv ∈ A appartiene a una e una sola stella entrante (in particolare,uv ∈ δ−G(v)). Questo implica che, presi comunque due nodi u e v e le loro stelle entranti δ

−G(u)

e δ−G(v) si ha x(δ−G(u)) + x(δ

−G(v)) = x(δ−G(u) ∪ δ−G(v)) (gli archi sono tutti distinti); inoltre,

se consideriamo contemporaneamente tutte le stelle entranti, la loro unione e pari all’insiemedegli archi A, e quindi v∈N x(δ

−G(v)) = x(A). Analogamente si ottiene, per le stelle uscenti,

v∈N x(δ+G(v)) = x(A). Da cio segue che sommando le equazioni del sistema (8.5) si ottiene:

0 = ft(x)− fs(x) → ft(x) = fs(x) = f(x). (8.6)

E’ verificato quindi il seguente

79

Lemma 8.1.1 Il flusso fs(x) uscente da s eguaglia il flusso ft(x) entrante in t

Il flusso uscente da s (o entrante in t) e chiamato valore del flusso s-t o flusso inviato da sa t e viene indicato con f(x). In Figura 8.3 e mostrato un grafo capacitato e due flussi distinti.Per il primo flusso, il valore del flusso e f1s (x) = f1t (x) = f1(x) = 2; per il secondo flusso, ilvalore del flusso risulta f2(x) = 4.

s

31

42

t

(1,2)

(1,3)

(0,1) (0,1)(1,3)(1,2)

(1,2)

(1,2) (1,2)

(1,2)

s

31

42

t

(2,2)

(2,3)

(0,1) (0,1)(1,3)(1,2)

(2,2)

(2,2) (2,2)

(2,2)

Figura 8.3: Un grafo capacitato e due flussi s-t ammissibili, di valore 2 e 4 rispettivamente

Possiamo finalmente definire il problema del flusso massimo:

Definizione 8.1.2 Problema del massimo flusso: dato un grafo capacitato G(N,A, c|A|), unnodo sorgente s e un nodo pozzo t di G, trovare il flusso x che massimizza il valore del flussof(x).

Il problema del massimo flusso e un problema di programmazione lineare. Infatti, se intro-duciamo una nuova variabile f ∈ R che rappresenta il valore del flusso, il problema diventa:

(MF) max f(x)x(δ−G(v))− x(δ+G(v)) = 0 per ogni v ∈ N − {s, t}

x(δ−G(t)) = f−x(δ+G(s)) = −f0 ≤ xuv ≤ cuv per ogni uv ∈ A

(8.7)

Il problema di programmazione lineare (MF) puo essere riscritto in forma compatta utiliz-zando la matrice d’incidenza nodi-archi M di G:

(MF) max f(x)Mx− bf = 0 per ogni v ∈ N − {s, t}0 ≤ xuv ≤ cuv per ogni uv ∈ A

(8.8)

ove b e un vettore a |N | componenti b = (0, . . . , 0, 1,−1)T , con bu = 0 per u ∈ N − {s, t}, bt = 1e bs = −1

80

1

t

4

3

2

s

(1,2)

(2,3)

(1,1) (0,1)(1,3)

(1,2)

(1,2)

(1,2) (1,2)

(1,2)

W

(1,1)c(δ+(W))=5

Figura 8.4: Un taglio s-t

8.2 Il teorema del flusso netto

Sia ora dato un sottinsieme proprio dei nodi W ⊂ N , con s ∈ W e t /∈ W . Il taglio δ+(W ) edetto taglio s-t.

Definizione 8.2.1 Capacita, Flusso Netto Dato un taglio s-t W , si definisce capacita c(W ) deltaglio la somma delle capacita degli archi del taglio: c(W ) = c(δ+(W )). Dato inoltre un flussox, Si definisce Flusso Netto Fx(W ) attraverso il taglio la differenza fra la somma dei flussi degliarchi di δ+(W ) e la somma dei flussi degli archi di δ−(W ): Fx(W ) = x(δ+(W ))− x(δ−(W ).

Il flusso x(δ+(W )) e detto flusso uscente dal taglio, mentre x(δ−(W )) e detto flusso entrantenel taglio. IL flusso netto e dunque la differenza fra flusso uscente dal taglio e flusso entrantenel taglio. La capacita del taglio in Figura 8.4 e pari a 5, mentre il flusso netto e pari a 2.

Teorema 8.2.2 Teorema del flusso netto. Il flusso netto attraverso ogni taglio s-t e uguale alvalore del flusso f(x).

Dim. Consideriamo un qualunque taglio s-t δG(W ) ⊆ A. Sommando tutte le equazioni diconservazione del flusso per i nodi di W − {s} e l’equazione del flusso uscente da s:

+ x(δ−G(v))− x(δ+G(v)) = 0 per ogni v ∈W − {s}+ −x(δ+G(s)) = −f(x) (8.9)

otteniamo:

x(v∈W

δ−G(v)))− x(v∈W

δ+G(v))) = −f (x) (8.10)

Ogni arco uz ∈ A puo trovarsi in una delle seguenti quattro condizioni rispetto all’insiemeW :

1. Ambo gli estremi appartengono a W , i.e. u, z ∈ W . In questo caso l’arco uz apparirasia nella sommatoria x( v∈W δ−G(v)) (in quanto appartiene alla stella entrante in z) chenella sommatoria x( v∈W δ+G(v)) (in quanto appertiene alla stella uscente da u), e quindila variaibile xuz apparira due volte, una con segno positivo e l’altra con segno negativo.Quindi i due termini si cancellano.

81

z

W u

xuz

+

+

--

Figura 8.5: Costruzione del teorema del flusso netto

2. u ∈W , z ∈ N −W ; in questo caso uz e presente solo nella stella uscente da u e quindi lavariabile xuz apparira una sola volta con segno positivo.

3. u ∈ N −W , z ∈W ; in questo caso uz e presente solo nella stella entrante in z e quindi lavariabile xuz apparira una sola volta con negativo.

4. u ∈ N −W , z ∈ N −W ; in questo caso uz non e presente in nessuna delle stelle dei nodidi W e la variabile xuz non appare nella sommatoria.

Quindi, dopo aver cancellato tutti i flussi sugli archi con ambo gli estremi in W , resterannoi flussi degli archi uscenti da W con segno -, e i flussi degli archi entranti in W con segno +.Quindi otteniamo

x(v∈W

δ−G(v)))− x(v∈W

δ+G(v))) = x(δ−G(W )))− x(δ+G(W ))) = −f(x) (8.11)

e quindi Fx(W ) = x(δ+G(W )))− x(δ−G(W ))) = f(x).

Teorema 8.2.3 Teorema del flusso massimo. Per ogni flusso x di (G, c) il valore del flussof(x) e non superiore alla capacita del taglio s-t di capacita minima di (G,c).

Dim. Per ogni taglio s-t δ+G(W )) ⊆ A si ha, per il Teorema (8.4.2), f(x) = Fx(W ) =x(δ+G(W )))− x(δ−G(W )). Ora, essendo per il vincolo di capacita xuv ≤ cuv per ogni uv ∈ δ+G(W )si ha x(δ+G(W )) ≤ c(δ+G(W )) = c(W ). Conseguentemente, essendo per la non-negativita deiflussi, x(δ−G(W )) ≥ 0, si ha:

c(W ) = c(δ+G(W )) ≥ x(δ+G(W )) ≥ x(δ+G(W )))− x(δ−G(W )) = Fx(W ) = f(x).

Quindi, per qualunque taglio s-t δ+G(W ) e per qualunque x sara c(W ) ≥ f(x). In particolare,f(x) ≤ min{c(W ) : δ+G(W ) taglio s-t di G}. Se consideriamo quindi il taglio a capacita minimaδ+G(W

∗) sara c(W ∗) ≥ f (x).In Figura 8.6 sono mostrati un flusso x e tre distinti tagli W 1 = {s}, W 2 = {s, 1, 2} W 3 =

{s, 1, 2, 4}. Il flusso f(x) pari al flusso uscente s e xs1+xs2 = 2. La capacita c(W 1) = cs1+cs2 =4 ≥ f(x). La capacita c(W 2) = c1,3+c2,4 = 3 ≥ f (x). Infine c(W 3) = c1,3+c4,3+c4,t = 6 ≥ f(x).

Poiche ogni flusso ha un valore non superiore alla capacita di un qualunque taglio, abbiamola seguente semplice

82

1

t

4

3

2

s

(1,2)

(2,3)

(1,1)(0,1)

(1,3)

(1,2)

(1,2)

(1,2) (1,2)

(1,2)

(1,1)

w1

w2

w3

Figura 8.6: I tagli mostrati hanno tutti capacita strettamente maggiori del flusso f(x) = 2

Osservazione 8.2.4 Sia dato un flusso x. Se esiste un taglio δ+G(W ) tale che c(W ) = f(x)allora il flusso e ottimo.

La precedente osservazione fornisce una condizione sufficiente affinche un flusso sia massimo:ci possiamo porre la domanda se questa condizione e anche necessaria, e cioe se, dato un flussoottimo x∗, esiste un taglio di capacita minima δ+G(W

∗) tale che c(W ∗) = f(x∗). La risposta aquesta domanda e affermativa e sara l’oggetto dei prossimi capitoli.

8.3 Vettori Aumentanti

In questo paragrafo mostreremo come sia possibile incrementare il valore di un flusso x non mas-simo identificando particolari cammini sul grafo e modificando x sugli archi di questi cammini.

Definizione 8.3.1 Un vettore ξ ∈ R|A| e detto vettore aumentante rispetto a un flusso x ∈ R|A|,se e solo se

1. ξ(δ+G(s)) > 0.

2. x+ ξ e un flusso di (G, c).

Teorema 8.3.2 Teorema del vettore aumentante. Un flusso x∗ di valore f(x∗) e massimo se esolo se non esiste un vettore aumentante ξ rispetto a x∗.

Dim. Solo se. La necessita del teorema e implicata direttamente dalla definizione divettore aumentante. Infatti, supponiamo che esista un vettore aumentante ξ rispetto a x∗: perdefinizione x = x∗ + ξ e un flusso di (G, c) e si ha f(x ) = x (δ+G(s)) = x

∗(δ+G(s)) + ξ(δ+G(s)) >f(x∗), contaddicendo l’ipotesi che x∗ sia massimo.

Se. Supponiamo ora che x∗ non sia massimo, allora esiste un flusso x tale che f(x ) > f(x∗).Ponendo ξ = x − x∗ ∈ R|A| si ha f(x )− f(x∗) = x (δ+G(s))− x∗(δ+G(s)) = ξ(δ+G(s)) > 0.

Un esempio di vettore aumentante e mostrato in Figura 8.7. Il flusso iniziale e x = (xs,1 =1, xs,2 = 1, x1,2 = 1, x2,1 = 1, x1,t = 1, x2,t = 1). Il vettore aumentante e mostrato nella secondacopia del grafo, ed e pari a ξ = (ξs,1 = 1, ξs,2 = 0, ξ1,2 = 0, ξ2,1 = −1, ξ1,t = 0, ξ2,t = 1). Il flussofinale x+ ξ = x = (xs,1 = 2, xs,2 = 1, x1,2 = 1, x2,1 = 0, x1,t = 1, x2,t = 2).

83

Flusso x Vettore Aumentante ξ

1

s t

21

-10

0

1 0

Flusso x+ξ

1

s t

2(1,2)

(1,3)(1,2)

(1,2)

(1,2) (1,1)

f(x+ξ)=3

1

s t

2(1+1,2)

(1-1,3)(1+0,2)

(1+0,2)

(1+1,2)(1+0,1)

f(x)=2

Figura 8.7: Un esempio di vettore aumentante

Si osservi che il vettore aumentante puo anche avere componenti negative.Il teorema del vettore aumentante 8.3.2 suggerisce un possibile schema algoritmico per il

calcolo di un massimo flusso in un grafo:

• L’algoritmo costruisce una sequenza di flussi x(1), x(2), . . . relativi alla coppia (G, c). L’ultimoflusso sara il flusso ottimo.

• Il flusso iniziale viene posto uguale al flusso nullo x(1) := 0|A|: si osservi infatti che ilvettore nullo e un flusso (soddisfa tutti i vincoli). Poni i = 1.

• Fase i: se esiste un vettore aumentante ξ(i) rispetto al flusso x(i). Poni x(i+1) = ξ(i)+x(i).

• Se non esiste un vettore aumentante STOP. Il flusso e ottimo.

8.3.1 Il grafo residuo.

Vettori aumentanti rispetto a un flusso x possono essere identificati calcolando flussi di unparticolare grafo capacitato detto grafo residuo, associato al flusso x. Come si vedra, questografo e in realta un muiltigrafo in quanto puo contenere (copopie di) archi paralleli. Sia x ∈ IR|A|un flusso proprio di un grafo capacitato (G, c). Associato al flusso x e al vettore c definiamodue vettori r+, r− ∈ IR|A|, ponendo r+uv = cuv − xuv ≥ 0 per ogni uv ∈ A e r−uv = xuv ≥ 0 perogni uv ∈ A. Costruiamo quindi un nuovo grafo capacitato (H, r), con H = (N,A ), ove A sipartiziona in due insiemi di archi D e I (i.e. D ∩ I = ∅, D ∪ I = A ): D e detto l’insieme degliarchi diretti mentre I e l’insieme degli archi inversi.

Un arco uv+ (uscente da u ed entrante in v) appartiene a D se e solo se r+uv > 0. La capacitadi uv+ sara ruv+ = r+uv = cuv − xuv > 0. L’arco diretto uv+ e quindi un arco associato a unarco originale uv; in particolare uv+ esiste nel grafo residuo se e solo se xuv < cuv , cioe l’arcooriginale uv non e saturo (un arco uv si dice saturato da un flusso x se xuv = cuv).

Un arco uv− (uscente da u ed entrante in v) appartiene a I se e solo se r−vu > 0. La capacitadi uv− sara ruv− = r−vu = xvu > 0. L’arco inverso uv− e quindi un arco associato a un arcooriginale vu (uscente da v ed entrante in u); in particolare uv− esiste nel grafo residuo se e solose xvu > 0, cioe il flusso xvu sull’arco originale vu e non nullo. Il nome ”arco inverso” derivadal fatto che l’arco inverso uv− e generato da un arco originale vu cioe un arco incidente sullastessa coppia di nodi ma orientato in senso inverso.

84

Esempi di generazione degli archi inversi e diretti sono mostrati in Figura 8.8. A scopopuramente illustrativo, sono anche rappresentati a tratteggio gli archi ”mancanti”, cioe archiche non appartengono al grafo residuo perche le corrispondenti capacita residue sono nulle mache avrebbero potuto appartenere in corrispondenza a un vettore di flusso diverso da quellocorrente.

u

v(1,3)

u

v2

1

uv+

vu-

u

v(2,7)

(1,4)

u

v

5

3

u

v(3,3)

u

v

3

0 1

2vu-vu-

uv-

vu+

uv+

sd

Figura 8.8: Esempi di generazione di archi diretti e inversi nel grafo residuo

Un esempio completo di grafo residuo e mostrato in Figura 8.9. Ancora una volta abbiamorappresentato a tratteggio archi che in effetti non appartengono al grafo residuo.

(2,3)

(1,1)

(1,1)

(2,3) (3,4)

(2,2)

(2,2)

(1,1)s

1

2 3

4

t

(0,2)2 3

12

21

1

1

3

2

2(H,r)

s

1 4

t1

0

0

1

0

2

0 00

(G,c)

Figura 8.9: Flusso e grafo residuo

Osservazione. Diversamente da tutti i grafi incontrati finora, il grafo residuo puo contenerecoppie di archi paralleli; cioe fra una coppia di nodi u, v, orientati ambedue dal nodo u al nodo v,possono coesistere l’arco diretto uv+ (generato da un arco iniziale uv per cui cuv > xuv) e l’arcoinverso uv− (generato dall’arco iniziale vu con xvu > 0). Si parlera in questo caso di multigrafo.

Il prossimo teorema illustra come il grafo residuo H possa essere opportunamente utilizzatoper costruire un vettore aumentante rispetto a un flusso x nel grafo G.

Teorema 8.3.3 Teorema del grafo residuo. Se y ∈ IR|A | con f(y) > 0 e un flusso s-t dellacoppia (H, r) definita dal flusso x di (G, c) allora ξ ∈ IR|A| definito come

ξuv = yuv+ − yvu− se 0 < xuv < cuv (uv+ ∈ D,uv− ∈ I) (a)ξuv = yuv+ se xuv = 0 (uv+ ∈ D,uv− /∈ I) (b)ξuv = yvu− se xuv = cuv (uv+ /∈ D,uv− ∈ I) (c)

(8.12)

e un vettore aumentante rispetto a x.

85

Dim. Dobbiamo mostrare che ξ soddisfa le condizioni della Definizione 8.3.1 e cioe:

1. ξ(δ+G(s)) > 0.

2. z = x+ ξ e un flusso di (G, c).

Prima di cominciare si ricoirdi che, essendo y un flusso nel grafo residuo H(N,A ), r, sara0 ≤ yuv ≤ ruv per ogni uv ∈ A . Per mostrare che z e un flusso dobbiamo mostrare che zsoddisfa i vincoli di non-negativita, di capacita e di conservazione del flusso, che in s non entriflusso e che non esca flusso da t.

Il vettore z soddisfa i vincoli di non-negativita. Mostriamo innanzitutto che zuv =xuv + ξuv ≥ 0 per ogni uv ∈ A e cioe che il vettore z ∈ R|A| soddisfa in vincoli di non-negativita.

Se vu− /∈ I allora ξuv e calcolato secondo l’espressione 8.12.b: quindi ξuv = yuv+ . Essendoyuv+ ≥ 0, si ha ξuv ≥ 0; essendo xuv un flusso si ha xuv ≥ 0; quindi zuv ≥ 0.

Se vu− ∈ I allora ξuv e calcolato secondo l’espressione 8.12.a oppure 8.12.c. Essendo yuv+ ≥ 0e yvu− ≤ rvu− si avra in entrambi i casi ξuv ≤ rvu− = xuv, ovvero ξuv ≥ −xuv. Quindizuv = xuv + ξuv ≥ xuv − xuv = 0.

Il vettore z soddisfa i vincoli di capacita. Mostriamo ora che zuv = xuv + ξuv ≤ cuvper ogni uv ∈ A e cioe che il vettore z ∈ R|A| soddisfa in vincoli di capacita.

Se uv+ /∈ D allora ξuv e calcolato secondo l’espressione 8.12.c: quindi ξuv = −yvu− ≤ 0.Quindi zuv = xuv + ξuv ≥ xuv = cuv (l’ultima uguaglianza discende dal fatto che ci troviamo nelcaso 8.12.c).

Se uv+ ∈ D allora ξuv e calcolato secondo l’espressione 8.12.a oppure 8.12.b: in entrambi icasi ξuv ≤ yuv+ ≤ ruv+ = cuv − xuv. Quindi zuv = xuv + ξuv ≤ xuv + (cuv − xuv) ≤ cuv.

Il vettore z soddisfa i vincoli di conservazione del flusso. Mostriamo ora chez(δ−G(v))−z(δ+G(v)) = 0 per ogni nodo v ∈ N−{s, t}, cioe z soddisfa i vincoli di conservazione delflusso ai nodi intermedi. Per far cio dimostreremo che il vettore aumentante soddisfa ξ(δ−G(v))−ξ(δ+G(v)) = 0 per ogni nodo v ∈ N − {s, t}. Sara utile a tal scopo classificare gli archi diA in tre classi disgiunte in relazione al valore del flusso sugli archi stessi. Specificamente,partizioniamo gli archi di A in tre insiemi A1, A2,A3. L’insieme A1 = {uv ∈ A : 0 < xuv < cuv}e l’insieme di archi i cui corrispondenti flussi soddisfano la condizione 8.12.a. AnalogamenteA2 = {uv ∈ A : xuv = 0} e l’insieme di archi i cui corrispondenti flussi soddisfano la condizione8.12.b. Infine, A3 = {uv ∈ A : xuv = cuv} e l’insieme di archi i cui corrispondenti flussisoddisfano la condizione 8.12.c.

Ora, la quantita ξ(δ−G(v))−ξ(δ+G(v)) puo essere riscritta come uv∈A ξuv− vu∈A ξvu. Usandola partizione {A1, A2, A3} di A, quest’ultima espressione diventa

uv∈A1ξuv −

vu∈A1ξvu +

uv∈A2ξuv −

vu∈A2ξvu +

uv∈A3ξuv −

vu∈A3ξvu. (8.13)

Usando l’espressione 8.12.a, il termine uv∈A1 ξuv − vu∈A1 ξvu diventa,

86

uv∈A1ξuv −

vu∈A1ξvu =

uv∈A1(yuv+ − yvu−)−

vu∈A1(yvu+ − yuv−)

.Analogamente, usando l’espressione 8.12.b, il termine uv∈A2 ξuv − vu∈A2 ξvu diventa,

uv∈A2ξuv −

vu∈A2ξvu =

uv∈A2yuv+ −

uv∈A2yvu−

.Infine, usando l’espressione 8.12.c, il termine uv∈A3 ξuv − vu∈A3 ξvu diventa,

uv∈A3ξuv −

vu∈A3ξvu = −

uv∈A3yvu− +

uv∈A3yuv−

.Ricomponendo queste espressioni, si ha che la 8.13 puo essere riscritta come:

[uv∈A1

(yuv+−yvu−)−vu∈A1

(yvu+−yuv−)]+[uv∈A2

yuv+−uv∈A2

yvu+ ]+[−uv∈A3

yvu−+uv∈A3

yuv− ]

Quest’ultima espressione puo essere riscritta, riarrangiando i termini, come:

uv+∈Dyuv+ +

uv−∈Iyuv− −

vu+∈Dyvu+ −

vu−∈Iyvu−

Ma questa e proprio l’espressione del vincolo termine variabile y(δ−H(v))−y(δ+H(v)) del vincolodi conservazione del flusso y relativo al nodo v nel grafo residuo; quindi, abbiamo mostrato che

ξ(δ−G(v))− ξ(δ+G(v)) = y(δ−H(v))− y(δ+H(v))

Essendo y un flusso, sara y(δ−H(v))− y(δ+H(v)) = 0 e quindi,

ξ(δ−G(v))− ξ(δ+G(v)) = 0;

essendo x un flusso sara x(δ−G(v))− x(δ+G(v)) = 0 e quindi, finalmente

z(δ−G(v))− z(δ+G(v)) = x(δ−G(v)) + ξ(δ−G(v))− x(δ+G(v))− ξ(δ+G(v)) = 0.

Il vettore z soddisfa il vincolo z(δ−G(s)) = 0 (no flusso entrante in s). Essendo xflusso, si ha che x(δ−G(s)) = 0 e quindi z(δ

−G(s)) = ξ(δ−G(s)). Riscriviamo ξ(δ

−G(s)) scomponendo

i contributi degli insiemi A1, A2, A3:

ξ(δ−G(s)) =vs∈A

ξvs =vs∈A1

ξvs +vs∈A2

ξvs +vs∈A3

ξvs

Esseno x un flusso, xvs = 0 per ogni vs ∈ A; e quindi gli insiemi A1 e A3, che prevedonoxuv > 0 (condizioni 8.12.a e 8.12.c) , sono vuoti. Quindi ξ(δ

−G(s)) = vs∈A2 ξvs. Ma, utilizzando

87

l’espressione 8.12.b, si ha che ξ(δ−G(s)) = vs∈A2 ξvs = vs∈A2 yvs+ . Ma y e un flusso, quindiyvs = 0 per ogni vs ∈ A . Ne consegue che z(δ−G(s)) = ξ(δ−G(s)) = vs∈A2 yvs+ = 0.

Analogamente si puo mostrare che il vettore z soddisfa il vincolo z(δ+G(t)) = 0 (noflusso uscente da t).

Abbiamo quindi mostrato che z = x+ ξ e un flusso di (G, c). Resta solo da dimostrare cheξ(δ+G(s)) > 0.

Riscriviamo ξ(δ+G(s)) scomponendo i contributi degli insiemi A1, A2, A3:

ξ(δ+G(s)) =sv∈A

ξsv =sv∈A1

ξsv+sv∈A2

ξsv+sv∈A3

ξsv =sv∈A1

(ysv+−yvs−)+sv∈A2

ysv+−sv∈A3

yvs−

e, raggruppando come piu sopra, si ottiene

ξ(δ+G(s)) =sv+∈D

ysv+ −vs−∈I

yvs−

Poiche y e un flusso vs−∈I yvs− = 0. Quindi ξ(δ+G(s)) = sv+∈D ysv+ . Inoltre, essendo x

un flusso, si ha xvs = 0 per ogni vs ∈ A, e quindi vs− /∈ I per ogni v ∈ N (ovvero non esistonoarchi inversi generati da archi originali entranti in s). Quindi nel grafo H(N,A ) l’insieme degliarchi entranti in s contiene solo archi diretti. Quindi

ξ(δ+G(s)) =sv+∈D

ysv+ =sv∈A

ysv

.Ma sv∈A ysv e pari al valore del flusso f(y) che per ipotesi e f(y) > 0. Quindi ξ(δ

+G(s)) > 0.

Per intuire il ruolo svolto dagli archi diretti e inversi nella definizione del vettore aumentanteξ e quindi del nuovo flusso, svolgiamo alcune semplici osservazioni. Un arco originario uv ∈ Apuo generare due archi nel grafo residuo, l’arco uv+ e l’arco vu−. Un flusso positivo yuv+ > 0sull’arco diretto uv+ nel grafo residuo fara crescere la componente ξuv di una quantita parial flusso. Al contrario, un flusso positivo yvu− > 0 sull’arco inverso vu− fara diminuire lacomponente ξuv di una quantita pari al flusso. Quindi, flussi sugli archi diretti aumenterannoil flusso iniziale sugli archi originali che li hanno generati, mentre flussi sugli archi inversi lofaranno diminuire (sugli archi generatori).

8.4 Taglio minimo e flusso massimo.

In questa sezione verra illustrata una delle proprieta fondamentali, ovvero l’uguaglianza delvalore di un flusso massimo e della capacita di un taglio a capacita minima nel grafo (G, c) (ininglese mincut-maxflow property). Si ricordi che il Teorema del flusso massimo 8.2.3 enunciavache la capacita del taglio a capacita minima e non inferiore al valore del flusso massimo. Oradimostreremo che le due grandezze coincidono. Si osservi che in generale, preso un qualunquetaglio s-t definito da un insieme W , e preso un qualunque s-t flusso x il Teorema del flussomassimo ci premette di concludere che f (x) ≤ c(W ), cioe il valore del flusso e non superiore

88

alla capacita del taglio. Ora, se per una data una coppia (x, W ) accade che f (x) = c(W ),allora posso concludere che x e un flusso di valore massimo e W e un taglio di capacita minima.Infatti, se x non fosse un flusso massimo, esisterebbe un flusso x∗ con f(x∗) > f (x) = c(W )e la coppia (x∗, W ) violerebbe il Teorema del flusso massimo. Analogamente, se esistesse uninsieme W ∗ tale che c(W ∗) < c(W ) = f (x), allora la coppia (x,W ∗) violerebbe il Teorema delflusso massimo. Questa proprieta verra utilizzata nella dimostrazione del teorema fondamentaledi questa sezione.

Innanzitutto enunciamo un semplice lemma di cui omettiamo la dimostrazione.

Lemma 8.4.1 Sia (G, c) un grafo capacitato, sia P un cammino orientato dal nodo s ∈ N alnodo t ∈ N e sia cmin la capacita minima degli archi di P , i.e. cmin = minuv∈P cuv. Allora ilvettore y ∈ R|A| con yuv = cmin per uv ∈ P e yuv = 0 per uv ∈ A − P e un flusso s-t di valorecmin.

1

2

ts

2 3

2

3

1 1

t

2

s

(2,3)

(0,3)

(2,2)

(0,2) (0,1)

Figura 8.10: Flusso su un cammino

Ad esempio, nel grafo di Figura 8.10, e possibile inviare un flusso lungo il cammino s-t,P = {s, (s, 1),1, (1, t), t}. Essendo cmin = 2, il flusso inviato ha valore 2.

Un’altra semplice osservazione e la seguente. Sia x un flusso di (G, c), e sia uv un arcodi G(N,A). Allora uv+ appartiene al grafo ridotto H se e solo se cuv > xuv: rovesciandol’enunciato, possiamo concludere che uv+ non appartiene ad H se e solo se cuv = xuv, cioel’arco originale e saturo.

Analogamente, sia vu un arco di G(N,A). L’arco inverso uv− appartiene al grafo ridotto Hse e solo se xvu > 0; rovesciando l’enunciato, possiamo dire che uv

− non appartiene ad H see solo se xvu = 0, cioe sull’arco originale il flusso e nullo.

Teorema 8.4.2 Teorema del taglio minimo. Se non esiste un s-t flusso y ∈ IR|A | con f (y) > 0nel grafo residuo H con capacita residua r (rispetto a un flusso proprio x) allora esiste un s-ttaglio di G (δ+G(W ) ⊆ A) con f(x) = c(W ) (valore del flusso uguale alla capacita del taglio).

Dim. Supponiamo quindi che non esista un flusso y con f(y) > 0. Sia W l’insieme dei nodidi H raggiungibili da s, ovvero i nodi u ∈ N per cui esiste un cammino s-u in H. Chiaramentes ∈ W . Inoltre t /∈ W , altrimenti, per il lemma 8.4.1, esisterebbe un flusso y con f(y) > 0.Quindi W definisce un taglio s-t.

Inoltre si ha che δ+H(W ) = ∅. Infatti, supponiamo per assurdo che esista uv ∈ δ+H(W ), conu ∈ W e v ∈ N −W . Poiche u ∈ W , esiste un cammino orientato P da s a u in H . Ma allora,

89

Su

tv

W N-W

H(N,A’)

Figura 8.11: Nodi raggiungibili nel grafo residuo

concatenando P all’arco uv si ottiene un cammino orientato da s a v, contraddicendo il fattoche v ∈ N −W e quindi non e raggiungibile da s in H.

Quindi, se non esiste un flusso di valore positivo nel grafo residuo H esite in H un tagliovuoto δ+H(W ) = ∅. Vediamo adesso le caratteristiche del taglio definito da W nel grafo originaleG. Studieremo cioe l’andamento dei flussi sugli archi che attraversano il taglio in G.

Sia quindi uv un arco di G con u ∈W e v ∈ N−W e capacita cuv > 0. Essendo δ+H(W ) = ∅,

l’arco uv+ non appartiene a H . Questo implica che l’arco uv di G e saturo, cioe xuv = cuv.Quindi possiamo concludere che ogni arco uv ∈ δ+G(W ) e un arco saturo. Quindi, ricordandoche la capacita del taglio c(W ) e pari a c(δ+G(W )) = u∈W,v∈N−W cuv, essendo cuv = xuv per

ogni arco in δ+G(W )) si ha

c(W ) = c(δ+G(W )) = x(δ+G(W )) =

u∈W,v∈N−Wxuv. (8.14)

Sia ora vu un arco di G con v ∈ N −W e u ∈ W . Poiche l’arco inverso uv− non appartienead H, deve essere xvu = 0. Quindi possiamo concludere che ogni arco vu ∈ δ−G(W ) e tale chexvu = 0. Quindi, ricordando l’espressione del flusso netto F (W ) attraverso il taglio definitoda W , ovvero F (W ) = x(δ+G(W )) − x(δ−G(W )), si ha che x(δ−G(W )) = v∈N−W,u∈W xvu = 0 equindi

F ((W )) = x(δ+G(W )) (8.15)

uv+

u v

uv-

W 0

0H

u v

xuv=cuv

xvu = 0G

W

Figura 8.12: Archi attraverso il taglio definito da W in H e in G

90

Ora ricordando che il flusso netto attraverso un qualunque taglio s-t e pari al valore delflusso f(x) (Teorema del flusso netto 8.2.2), abbiamo (utilizzando 8.14 e 8.15) che:

f (x) = F (W ) = c(W )

Quindi abbiamo esibito un taglio s-t la cui capacita e pari al valore del flusso x. Possiamodunque concludere che il taglio e un taglio a capacita minima e il flusso e un flusso massimo.

Teorema 8.4.3 Teorema del massimo flusso e del minimo taglio. Un flusso proprio s-t x∗ ∈IR|A| nel grafo G con capacita c ha valore massimo f(x∗) se e solo se esiste un taglio s-t δG(W ))di G, con f(x∗) = c(W ∗) (taglio s-t di capacita minima).

Dim. Dal Teorema del flusso massimo (8.2.3) abbiamo che f(x) ≤ min{c(W ) :W taglio s-tdi G} = c(W ∗). Se f (x∗) = c(W ∗) allora f (x∗) ha valore massimo.

Viceversa, se f(x∗) ha valore massimo, allora dal Teorema del vettore aumentante (8.3.2)non esiste un vettore aumentante rispetto a x∗. Quindi, dal Teorema del grafo residuo (8.3.3)non esiste un s-t flusso y di H(, r) con f(y) > 0. In conseguenza, dal Teorema del taglio minimo(8.4.2) esiste un s-t taglio δG(W

∗) di G con c(W ∗) = f(x∗).

8.5 L’algoritmo di Ford e Fulkerson

I teoremi precedenti suggeriscono immediatamente una naturale strategia per il calcolo del flussomassimo in un grafo con capacita (G, c). L’algoritmo costruisce una sequenza di flussi proprix(1), x(2), . . . di (G, c).

Inizial. Il primo flusso della sequenza e (tipicamente) il flusso nullo x(1) = 0: questo perche ilflusso nullo e un flusso proprio di immediata costruzione. Si pone quindi i := 1.

Fase i. Trova un flusso y(i) con f(y(i)) > 0 nel grafo residuo H(i) di x(i) con capacita residue r(i).

Se tale flusso esiste, definisci il vettore aumentante ξ(i)

ξ(i)uv = y

(i)uv+ − y

(i)vu− se 0 < x

(i)uv < cuv

ξ(i)uv = y

(i)uv+

se x(i)uv = 0

ξ(i)uv = y

(i)vu− se x

(i)uv = cuv

(8.16)

Poni x(i+1) = ξ(i) + x(i)

Poni i := i+ 1 e va’ alla Fase i

Se non esiste un flusso y(i) relativo a H(i), r(i) allora x(i) e il flusso massimo (e l’insieme Wdei nodi raggiungibili definisce un taglio minimo).

Dobbiamo ancora illustrare delle metodologie per calcolare un flusso nel grafo residuo e per(eventualmente) minimizzare il numero delle fasi. Vediamo comunque con un esempio comel’algoritmo evolva.

91

1

t

2

s

(0,2)

(0,3)(0,2)

(0,2)

(0,2) (0,1)

x(1)1

t

2

s

(H(1),r(1))

2 2

2

2

3

1

Figura 8.13: Flusso nullo iniziale e grafo residuo

2

1

ts

y(1)

(2,2) (2,2)

(0,2)

(1,2)

(0,3)

(1,1)1

t

2

s

2

00

2

1 1ξ(1)

Figura 8.14: Flusso nel grafo residuo e vettore aumentante

Il flusso iniziale e il flusso nullo, mentre il grafo residuo corrispondente coincide col grafocapacitato iniziale. La prossima figura illustra invece un possibile flusso nel grafo residuo e ilcorrispondente vettore aumentante.

Il flusso x(2) ottenuto sommando il vettore aumentante al flusso iniziale, e il corrispondentegrafo residuo H(2) sono mostrati in Figura 8.15.

1

t

2

s

(0+2,2)

(0,3)(0,2)

(0+2,2)

(0+1,2) (0+1,1) 1

t

2

s

2 2

2

1

3

1

1

x(2):=x(1)+ξ(1) (H(2),r(2))

Figura 8.15: Secondo flusso e corrispondente grafo residuo

E’ facile vedere che non esiste un flusso nel grafo residuo H(2), e quindi il flusso x(2) e ottimo.Il taglio a capacita minima e mostrato in Figura 8.16.

Per ottenere questo taglio possiamo utilizzare l’algoritmo implicitamente mostrato nelladimostrazione (costruttiva) del Teorema del taglio minimo 8.4.2. In particolare, costruiamol’insieme W dei nodi raggiungibili da s nel grafo ridotto H2. Quindi W = {s, 1, 2}. Per quanto

92

1

t

2

s

(2,2)

(0,3)(0,2)

(2,2)

(1,2) (1,1)

Figura 8.16: Taglio a capacita minima

dimostrato, si ha che c(W ) = f(x) = 3.

8.6 Flussi nel grafo residuo: i cammini aumentanti.

L’idea di Ford e Fulkerson, risalente al 1960, e quella di cercare dei semplici flussi nel graforesiduo, specificamente flussi corrispondenti a cammini s-t. Infatti, il Lemma del flusso sulcammino 8.4.1 ci assicura che, se esiste un cammino P da s a t nel grafo residuo (H, r), epossibile costruire un flusso di valore pari a rmin, ove rmin e la capacita dell’arco a capacitaminima sul cammino P . Se esiste, il cammino P e detto cammino aumentante. Inoltre, se talecammino non esiste, allora grazie al Teorema del taglio minimo 8.4.2 possiamo concludere cheil flusso e massimo.

Riassumento, sia P un cammino s-t nel grafo residuo H(N,A ); allora un flusso y ∈ R|A | di(H, r) puo essere ottenuto ponendo

yuv = rmin se uv ∈ Pyuv = 0 se uv /∈ P (8.17)

ove rmin = minuv∈P ruv. Associamo ora a y un vettore aumentante secondo l’espressione 8.12.A tal scopo si osservi che, essendo P un cammino, non potra accadere che in P appaianocontemporaneamente l’arco (u, v) e l’arco (v, u). Come conseguenza si ha che l’espressione 8.12si riscrive, in questo caso, come

ξuv = 0 se uv ∈ A uv+, vu− /∈ P (a)ξuv = yuv+ = rmin se uv ∈ A uv+ ∈ P (b)ξuv = −yvu− = −rmin se uv ∈ A vy− ∈ P (b)

(8.18)

A questo punto possiamo finalmente descrivere l’algoritmo di Ford e Fulkerson per il calcolodel massimo flusso in un grafo capacitato.

L’algoritmo costruisce una sequenza di flussi propri x(1), x(2), . . . di (G, c).

Inizial. Poni x(1) = 0|A| (flusso nullo). Poni i := 1.

Fase i. Definisci il grafo residuo H(i) di x(i) con capacita residue r(i).

Trova un cammino aumentante P (i) nel grafo (H(i), r(i)).

93

Se tale cammino esiste, definisci il vettore aumentante ξ(i)ξ(i)uv = 0 se uv ∈ A uv+, vu− /∈ P (i) (a)

ξ(i)uv = y

(i)uv+ = r

(i)min se uv ∈ A uv+ ∈ P (i) (b)

ξ(i)uv = −y(i)vu− = −r

(i)min se uv ∈ A vy− ∈ P (i) (b)

(8.19)

Poni x(i+1) = ξ(i) + x(i)

Poni i := i+ 1 e va’ alla Fase i

Se non esiste un cammino aumentante x(i) e un flusso massimo. STOP.

Complessita dell’algoritmo di Ford e Fulkerson. Ogni fase richiede la ricerca di uncammino da s a t in un grafo H : come sappiamo, il numero di operazioni elementari sara O(m).Si puo far vedere che anche la costruzione del grafo residuo richiede O(m) operazione elementari.Per calcolare la complessita di tutto l’algoritmo dobbiamo calcolare il numero massimo di fasi iche l’algoritmo potrebbe essere costretto a eseguire. Se facciamo l’ipotesi che le capacita inizialic siano numeri interi, allora possiamo anche facilmente mostrare che il flusso x(i) calcolato allafase i e un vettore intero, per ogni i. Quindi, a ogni iterazione il valore del flusso aumenta dialmeno un’unita. Ora, il calore del flusso massimo e limitato dalla capacita del taglio a capacitaminima. Quest’ultima e a sua volta limitata dalla somma delle capacita di tutti gli archi delgrafo. Ponendo quindi C = uv∈A cuv, il valore del flusso massimo f(x∗) sara ≤ C. Il numerodi fasi sara dunque limitato da C e la complessita e O(Cm).

La figura 8.17 mostra come effettivamente, scegliendo ”maldestramente” i cammini au-mentanti, questa complessita teorica possa essere effettivamente raggiunta in un’esecuzionedell’algoritmo.

(1,1)

(0,B)

s

1

2

t

(0,B)

(0,1)

(0,B)(0,B)

(0,B)s

2

t

(1,B)

(0,B) (1,B)

1G,c H(1),r(1)

s

1

2

t

(0,B)

(1,1)

(1,B)(0,B)

(1,B)

G,c

Figura 8.17: Esempio di esecuzione degenere dell’algoritmo di Ford e Fulkerson

Alla prima iterazione 1 viene identificato inH(1) il cammino P (1) = {s, (s2+), 2, (21+), 1, (1t+), t}.La capacita residua minima e pari a r

(1)min = min(r

(1)s2+, r(1)21+, r(1)1t+) = 1. Viene quindi costruito

il flusso y(1)

s2+= y

(1)

21+= y

(1)1t+

= 1, e y(1)

s1+= y

(1)

2t+= 0. A tale flusso corrisponde un vettore

aumentante ξ(1)s2 = ξ

(1)21 = ξ

(1)1t = 1, e ξ

(1)s1 = ξ

(1)2t = 0. Il nuovo flusso e mostrato in Figura 8.17.

A questo flusso corrisponde il grafo residuo H(2), r(2) mostrato in Figura 8.18.

1Si osservi che, essendo il flusso iniziale un flusso nullo, il grafo residuo (H, r) e il grafo iniziale (G, c)coincidono

94

(0,1)

s

1

2

t

(1,B)

(0,1)

(1,B)(1,B)

(1,B)

G,cH(2),r(2)

(0,B)

(0,B)

(1,1)

(1,B)

s

2

t

(1,B)1

(0,1)

(0,1)

H(3),r(3)

(1,B)

(1,B)

(1,1)

(0,B)

s

2

t

(0,B)1

(0,1)

(0,1)(0,1)

Figura 8.18: Continua l’esempio di Figura 8.17

Un cammino aumentante in H(2), r(2) e il cammino P (2) = {s, (s1+), 1, (12−), 2, (2t+), t}. Lacapacita residua minima e pari a r

(2)min = r

(2)12− = 1. Viene quindi costruito il flusso y

(2)s1+

= y(2)

12− =

y(2)2t+

= 1, e y(2)

s2+= y

(2)

2s− = y(2)

1t+= y

(2)

t1− = 0. A tale flusso corrisponde un vettore aumentante

ξ(2)s1 = ξ

(2)2t = 1, ξ

(2)21 = −1 e ξ(2)s2 = ξ

(2)1t = 0. Il nuovo flusso e mostrato ancora in Figura 8.18.

A questo flusso corrisponde il grafo residuo H(3), r(3) mostrato in Figura 8.18. Di nuovo inquesto grafo possiamo costruire un cammino aumentante con capacita minima unitaria. Risultaovvio come sia possibile costruire una sequenza di 2B flussi prima di arrivare al flusso ottimo divalore 2B. Si osservi come il flusso massimo poteva essere ottenuto con appena due iterazionidell’algoritmo di Ford e Fulkerson, come mostrato in Figura 8.19 e in Figura 8.20.

s

1

2

t

(0,B)

(0,1)

(0,B)(0,B)

(0,B)

G,c

(0,B)

(0,1)

(B,B)

s

2

t

(B,B)

(0,B)

1H(1),r(1)

s

1

2

t

(B,B)

(0,1)

(1,B)(0,B)

(B,B)

G,c

Figura 8.19: Prima iterazione dell’esecuzione veloce

s

1

2

t

(B,B)

(0,1)

(B,B)(B,B)

(B,B)

G,c

(0,B)

(B,B)

(0,1)

(0,B)

s

2

t

(B,B)

1H(2),r(2)

(0,B)

(0,B)

(0,1)

(0,B)

s

2

t

(0,B)

1H(3),r(3)

Figura 8.20: Seconda iterazione dell’esecuzione veloce

95