Max Flow - Min Cut

Max Flow - Min Cut

F. Pugliese January 14, 2015

Abstract

Esponiamo nei dettagli il teorema del massimo flusso, sia nella versione con capacit`a sui lati che in quella con capacit`a sui vertici.

1 Flussi nelle reti

1.1 Promemoria di teoria algebrica dei grafi

Sia G = (V, E) un grafo finito e semplice. A G sono associati gli spazi vettoriali reali

F = F G def

= {f : V → R}

H = H G def

= {h : E → R}

Se |V | = n, |E| = m, allora F ' R ⁿ e H ' R ^m . Sia F che H sono spazi euclidei, col prodotto scalare

f · g ^def = X

v∈V

f (v)g(v), ∀f, g ∈ F

e analoga definizione per H.

Se assegnamo un’orientazione a G, che indicheremo in questo caso con ~ G = (V, ~ E), allora `e ben definito l’operatore d’incidenza orientata D ∈ Hom(H, F) tramite la formula

D(h)(v) ^def = X

e∈E

(−1) ^e,v h(e) = X

e

=v

h(e) − X

e

=v

h(e); (1)

tale operatore ha rango n − c, dove c `e il numero di componenti connesse di G; in particolare, se G `e connesso, allora D ha rango n − 1. Ricordiamo che l’operatore aggiunto D ^∗ ∈ Hom(F, H) soddisfa

D ^∗ (f )(e) = f (e ⁰ ) − f (e ⁰⁰ ), (2)

sicch`e, se G `e connesso, il nucleo di D ^∗ `e l’insieme delle funzioni costanti su V e quindi (per le note propriet`a dell’aggiunto)

Im D = (KerD ^∗ ) ^⊥ = h1i ^⊥ = (

f ∈ F

¯ ¯

¯ ¯

¯ X

v∈V

f (v) = 0 )

(3)

(qui e nel seguito 1 = (1, . . . , 1)).

1.2 Reti e flussi

Cominciamo dalla definizione formale di rete e di flusso.

Una rete `e un grafo orientato ~ G = (V, ~ E) con due vertici speciali s, t ∈ V non adiacenti, detti rispettivamente sorgente e pozzo della rete, e una funzione capacit`a c : E → R ⁺ ₀ . Un flusso (ammissibile) in G `e una funzione h ∈ H G tale che:

F1)

0 ≤ h(e) ≤ c(e), (4)

per ogni e ∈ E;

F2)

D(h)(v) = 0, (5)

per ogni v 6= s, t

Il valore del flusso `e la quantit`a

V (h) ^def = D(h)(s) ∈ [0, +∞[ (6)

Commentiamo le definizioni. Conviene immaginare ~ G come una rete fisica in cui scorre un ”fluido” (corrente elettrica, acqua, traffico automobilistico, dati,...). La funzione h(e) esprime allora l’intensit`a del flusso, cio`e la quan- tit`a di fluido che scorre nell’unit`a di tempo attraverso il ramo e della rete.

Notiamo che h non dipende dal tempo, cio`e ci limitiamo a considerare flussi stazionari; in altri termini, la quantit`a di fluido che entra ad ogni istante in qualsiasi nodo della rete diverso da s, t `e esattamente uguale alla quantit`a di flusso uscente: questa legge di conservazione `e espressa, in virt` u della (1), dalla propriet`a F2). La propriet`a F1) esprime invece il fatto che ogni ramo e della rete ha una portata limitata, e c(e) `e tale limite. Quanto al significato di V (h), esso `e la quantit`a di fluido che passa nell’unit`a di tempo dalla sorgente s al pozzo t. Infatti, osserviamo innanzitutto che, per la (3) e la (5), vale

0 = D(h) · 1 = X

v∈V

D(h)(v) = D(h)(s) + D(h)(t),

cio`e

D(h)(t) = −D(h)(s) = −V (h);

in altre parole, il flusso che entra nel pozzo `e uguale al flusso che esce dalla sorgente, cio`e V (h) `e esattamente il flusso che passa da s a t. Tale interpretazione di V (h) `e confermata dalla seguente costruzione. Sia

s ∈ S ⊂ V \{t}

e sia ¯ S = V \S; allora l’insieme K S ⊂ E dei lati incidenti simultaneamente con S e con ¯ S `e un taglio (”edge cut”) di G che separa s da t (cio`e G\K S `e sconnesso ed s e t appartengono a componenti connesse diverse). E’ naturale definire il flusso associato a questo taglio come la differenza fra il flusso uscente da S e quello entrante:

h(S, ¯ S) ^def = X

e

∈S,e

∈ ¯ S

h(e) − X

e

∈S,e

∈ ¯ S

h(e);

ebbene, questa quantit`a coincide, qualunque sia S, col valore totale V (h) del flusso da s a t; infatti, detta χ S ∈ F la funzione caratteristica di S e tenendo conto di (2) e (5), vale:

V (h) = D(h)(s) = X

v∈S

D(h)(v) = D(h) · χ S

= h · D ^∗ (χ S ) = X

e∈E

h(e) [χ S (e ⁰ ) − χ S (e ⁰⁰ )]

= X

e∈K

h(e) [χ S (e ⁰ ) − χ S (e ⁰⁰ )] = h(S, ¯ S)

1.3 Teorema del ”max flow - min cut”

Oltre al flusso h(S, ¯ S), al taglio (S, ¯ S) `e associata anche la capacit`a c(S, ¯ S) ^def = X

e

∈S,e

∈ ¯ S

c(e),

cio`e la massima quantit`a ammissibile di ”fluido” attraverso il taglio nella di- rezione dalla sorgente s al pozzo t. Evidentemente, per la propriet`a (4) vale

V (h) = h(S, ¯ S) ≤ c(S, ¯ S)

per ogni flusso ammissibile h e per ogni taglio (S, ¯ S); ci`o implica, in particolare, che

sup

h

V (h) ≤ min

S c(S, ¯ S); (7)

il punto principale del famoso teorema del ”max flow - min cut” consiste nella dimostrazione che tale diseguaglianza `e in realt`a un’eguaglianza.

Prima di enunciare il teorema facciamo alcune considerazioni preliminari sul dominio e sul range della funzione h 7→ V (h). Innanzitutto, dalla diseguaglianza (7) segue banalmente che il sup di V `e finito; in realt`a, tale sup `e un max, perch`e il dominio b H ⊂ H ' R ^m dei flussi ammissibili `e un compatto; infatti, dalle condizioni (4), (5) segue che

H = Q(c) ∩ P b con

Q(c) = [0, c(e 1 )] × · · · × [0, c(e m )]

parallelepipedo chiuso e limitato di R ^m e

P = {h ∈ R ^m | D(h)(v) = 0 ∀v ∈ V \{s, t}}

`e un sottospazio vettoriale (e quindi un chiuso) di R <sup>m</sup> ; dunque b H `e compatto e V : b H → R ⁺ ₀ , che `e (lineare e quindi) continua, ammette un massimo (il minimo `e V (0) = 0). Quanto al secondo membro di (7), l’esistenza del minimo

`e la banale conseguenza del fatto che la famiglia dei sottoinsiemi S ⊂ V su cui calcoliamo la capacit`a c(S, ¯ S) `e finita.

Theorem 1 (Max Flow- Min Cut) Vale l’uguaglianza max

h∈ b H V (h) = min

S c(S, ¯ S) (8)

Proof. Sia ¯h ∈ b H un flusso massimale per V e sia S = S ¯ h ⊂ V costruito per ricorrenza secondo le seguenti regole:

a) s ∈ S;

b) se S contiene il primo vertice e ⁰ di un lato e tale che ¯h(e) < c(e), allora e ⁰⁰ ∈ S;

c) se S contiene il secondo vertice e ⁰⁰ di un lato e tale che ¯h(e) > 0, allora e ⁰ ∈ S.

Al termine della costruzione, o S `e tutto V oppure S 6= V `e tale che sui lati uscenti il flusso `e uguale alla capacit`a, mentre su quelli entranti il flusso `e nullo.

Mostriamo che, nell’ipotesi di massimalit`a di ¯h, S non contiene t. Infatti, se per assurdo t appartenesse ad S, allora, per il modo in cui S `e costruito a partire da s, esisterebbe nel sottografo indotto G[S] un cammino:

P = (x ₀ = s, x ₁ , x ₂ , . . . , x _l = t)

tale che le quantit`a δ 0 , . . . , δ l−1 definite da

δ i =

 



c(x i x i+1 ) − ¯h(x i x i+1 ) se −−−−→ x i x i+1 ∈ ~ E

¯h(x i x i+1 ) se −−−−→ x i+1 x i ∈ ~ E sarebbero tutte positive. Detto δ = min δ i , sia h ^∗ ∈ H definito da

h ^∗ (e) ^def =

 

 

 

 

 



¯h(e) se e / ∈ P

¯h(e) + δ se ~e = −−−−→ x i+1 x i ∈ ~ P

¯h(e) − δ se ~e = −−−−→ x i+1 x i ∈ − ~ P

(dove con ~ P indichiamo il cammino orientato sP t). E’ facile vedere che h ^∗ ∈ b H;

infatti, essendo δ il minimo degli ”scarti” δ i , la condizione (4) `e verificata anche da h <sup>∗</sup> ; quanto alla (5), essa `e evidentemente vera per ogni vertice v / ∈ P (in quanto h ^∗ e ¯h coincidono su tutti i lati incidenti con v), resta da verificarla per v ∈ P \{s, t}. In effetti, per ogni i = 1, . . . , l − 1 vale

D(h ^∗ )(x i ) = X

x

∼e / ∈P

(−1) ^e,x

¯h(e)+(−1) ^x

^x

^,x

h ^∗ (x i−1 x i )+(−1) ^x

^x

h ^∗ (x i x i+1 );

per gli ultimi due termini ci sono quattro possibili casi, dipendenti dall’orientazione dei lati corrispondenti; per esempio, se −−−−→ x i x i−1 e −−−−→ x i x i+1 appartengono a ~ E, cio`e entrambi i lati escono da x i , allora

D(h ^∗ )(x i ) = X

x

∼e / ∈P

(−1) ^e,x

¯h(e) + h ^∗ (x i−1 x i ) + h ^∗ (x i x i+1 )

= X

x

∼e / ∈P

(−1) ^e,x

¯h(e) + ¯h(x i−1 x i ) − δ + ¯h(x i x i+1 ) + δ

= D(¯h)(x _i ) = 0;

allo stesso risultato si perviene negli altri tre casi (lasciamo la verifica al lettore).

Dunque, anche h ^∗ `e un flusso ammissibile per la rete. D’altra parte, V (h ^∗ ) = D(h ^∗ )(s) = X

x

x

6=e∼s

(−1) ^e,s h ^∗ (e) + (−1) ^x

^x

^,s h ^∗ (x 0 x 1 )

= X

x

x

6=e∼s

(−1) ^e,s ¯h(e) + (−1) ^x

^x

^,s h ^∗ (x 0 x 1 );

ora, se (−1) ^x

^x

^,s = 1, cio`e −−→ x 0 x 1 ∈ ~ E, allora h ^∗ (x 0 x 1 ) = ¯h(x 0 x 1 ) + δ; se invece

(−1) ^x

^x

^,s = −1, cio`e −−→ x 1 x 0 ∈ ~ E, allora h ^∗ (x 0 x 1 ) = ¯h(x 0 x 1 ) − δ; in entrambi i

casi, si ha che

V (h ^∗ ) = X

x

x

6=e∼s

(−1) ^e,s ¯h(e) + (−1) ^x

^x

^,s ¯h(x 0 x 1 ) + δ

= V (¯h) + δ > V (¯h),

contro l’ipotesi di massimalit`a di ¯h: dunque, t / ∈ S e quindi `e ben definito l’(s, t)- taglio (S, ¯ S), calcoliamone la capacit`a; per costruzione, su tutti i lati uscenti da S la capacit`a `e uguale al flusso ¯h, mentre su tutti quelli entranti ¯h = 0, sicch`e:

c(S, ¯ S) = X

~ e∈ ~ K

c(e) = X

~ e∈ ~ K

¯h(e) − X

−~ e∈ ~ K

¯h(e)

= ¯h(S, ¯ S) = V (¯h) = max

h∈ b H V (h), il che, per la diseguaglianza (7), implica l’asserto.

Remark 2 Osserviamo che il teorema 1 rimane valido, con esattamente la stessa dimostrazione, anche se per alcuni lati la capacit`a `e infinita, purch`e il valore del flusso sia limitato superiormente. In altre parole, se la rete ~ G = (V, ~ E; s, t; c) `e tale che il range di c sia [0, +∞[∪{+∞} ma la funzione V (h) sia limitata superiormente sull’insieme b H ⊂ H ' R ^m dei flussi ammissibili, allora possiamo ripetere il ragionamento precedente parola per parola (verificatelo!) e ottenere ancora l’uguaglianza (8): vedremo un esempio di questa situazione nella dimostrazione del teorema 4.

Una conseguenza importante del metodo di dimostrazione del teorema 1 `e la seguente.

Theorem 3 (Teorema d’integralit`a) Se nella rete ~ G=(V, ~ E; s, t; c) la capacit`a c

`e a valori interi, allora esiste un flusso massimale intero (cio`e, a valori interi su tutti i lati).

Proof. Il flusso massimale dell’enunciato `e l’ultimo termine di una sequenza

finita di flussi interi, costruita per ricorrenza (algoritmo di Ford-Fulkerson). Il

primo flusso `e quello identicamente nullo, h 0 = 0; il procedimento ricorsivo `e

il seguente. Sia h i ∈ b H l’i + 1-mo termine della sequenza e sia S i = S h

⊂ V

costruito come nella dimostrazione del teorema 1. Se t / ∈ S i allora, esattamente

come nella dimostrazione del teorema 1, h i `e un flusso massimale. Se invece t ∈

S i , allora possiamo ripetere il ragionamento fatto per il teorema 1, sostituendo

¯h con h i , costruendo in G[S] un (s, t)-cammino P e un flusso h i+1 = h ^∗ che differisce da h i solo su P e ha un valore

V (h i+1 ) = V (h i ) + ε i , (9) dove ε i , corrispondente al δ della dimostrazione del teorema 1, `e un intero pos- itivo; poich`e su ogni lato h i+1 differisce da h i per quantit`a intere, anche h i+1

`e intero. Otteniamo cos`ı una successione h 0 , h 1 , . . . che deve necessariamente stabilizzarsi dopo un numero finito di passi, in quanto la corrispondente suc- cessione di interi {V i = V (h i )} `e strettamente crescente (per la (9)) e limitata superiormente, ad esempio, dalla quantit`a P

e∈E c(e); evidentemente, l’ultimo termine h r `e il flusso massimale intero richiesto.

Del teorema ”max flow - min cut” esistono diverse varianti, tra le quali `e importante quella in cui le capacit`a sono assegnate sui vertici, invece che sui lati. Precisamente, data la solita rete ~ G con sorgente s e pozzo t, `e assegnata una funzione capacit`a sui vertici:

c : V \{s, t} → R ⁺ ₀ ; l’insieme dei flussi ammissibili, in questo caso, `e

H c = (

h ∈ H : 1) h ≥ 0; 2) X

e

=v

h(e) = X

e

=v

h(e) ≤ c(v), ∀v 6= s, t )

; (10)

notiamo che la prima uguaglianza della condizione 2) equivale alla condizione (5). Anche in questo caso, il valore del flusso h `e la quantit`a V (h) definita da (6).

Per quanto riguarda il taglio su cui calcolare la capacit`a, stavolta si tratta di un ”vertex cut”, cio`e di un sottoinsieme S ⊂ V \{s, t} tale che G\S `e sconnesso ed s e t appartengono a componenti connesse diverse. La capacit`a corrispon- dente `e

c(S) ^def = X

v∈S

c(v)

L’analogo del teorema 1 e del teorema 3 per le reti con capacit`a sui vertici

`e il seguente.

Theorem 4 (”max flow” per le capacit`a sui vertici). Sia ~ G = (V, ~ E, s, t, c) la rete con restrizioni di capacit`a sui vertici descritta sopra; allora la funzione h 7→ V (h) `e dotata di massimo, e vale

max h V (h) = min c(S)

Inoltre, se c `e a valori interi, esiste un flusso massimale a valori interi.

Proof. Come si vede, l’enunciato `e praticamente identico a quello del teo- rema 1 e del teorema 3; in effetti, come ora vedremo, la dimostrazione consiste nel ridursi, tramite una rete ausiliaria, al teorema 1. La rete ausiliaria ~ G <sup>±</sup> `e costruita a partire da ~ G come segue:

1. ogni vertice v ∈ V G \{s, t} viene sostituito da un lato orientato −−−→ v − v + , cui viene assegnata la capacit`a c ^± (v − v + ) = c(v); per convenzione, poniamo inltre s − = s + = s, t − = t + = t;

2. ogni lato − uv ∈ ~ → E viene sostituito dal lato −−−→ u + v − , a cui viene assegnata capacit`a c ^± (−−−→ u + v − ) = +∞.

In altri termini, i vertici diversi da s, t vengono ”sdoppiati” in lati con la stessa capacit`a, e tutti i lati di ~ G che entravano in (risp. uscivano da) v adesso entrano in v − (risp. escono da v + ), e su questi lati non ci sono limiti di capacit`a.

E’ facile vedere che il dominio b H ^± ⊂ H ^± ' R ^m+n−2 dei flussi ammissibili in G ^± `e compatto. Infatti, b H <sup>±</sup> `e descritto dalle condizioni (4), (5) e dalle condizioni 2) in (10), ciascuna delle quali descrive un sottoinsieme chiuso, per cui b H ^± `e chiuso. Inoltre, b H <sup>±</sup> `e limitato. Infatti, ogni lato di ~ E ^± `e: a) del tipo −−−→ v − v + , per v ∈ V \{s, t}, oppure b) del tipo w + z − , con w, z ∈ V ma {w, z} 6= {s, t}. Nel caso a), vale

k(v − v + ) ≤ c(v),

per ogni k ∈ b H ^± ; nel caso b), supponendo, ad esempio, w 6= s, t, e ricordando le (10) ₂₎ e la non negativit`a di h, vale

k(w + z − ) ≤ X

e∈E

e

=w

k(e) = k(w − w + ) ≤ c(w),

(e analoga maggiorazione per il caso z / ∈ {s, t}). Dunque, in definitiva, b H ^± `e compatto e quindi la funzione V ^± : b H ^± → R ⁺ ₀ definita da

V ^± (k) ^def = D ^± (k)(s)

ammette massimo su tale insieme. In virt` u di quanto osservato nel remark 2, `e allora possibile applicare a ~ G ^± il teorema 1 e dedurne che

max

k∈ b H

V ^± (k) = min

T c ^± (T ) (11)

dove, evidentemente, a secondo membro possiamo limitarci far variare T ⊂ E ^± fra gli (s, t)-tagli a capacit`a finita; ma essendo questi ultimi interamente composti da lati del tipo v − v + , si stabilisce un’ovvia corrispondenza biunivoca fra essi e i ”vertex cut” in G, quella che al taglio S ⊂ V G \{s, t} associa l’edge cut S ^± = {v − v + | v ∈ S}; dunque,

min T c ^± (T ) = min

S c ^± (S ^± ) = min

S c(S) (12)

Quanto al primo membro di (11), osserviamo che esiste una corrispondenza biunivoca fra i flussi ammissibili nelle due reti ~ G e ~ G ^± , quella che al flusso h ∈ H c associa il flusso h ^± ∈ b H ^± definito da

h ^± (v − v + ) ^def = X

− → wv∈ ~ E

h(wv), h ^± (w + v − ) ^def = h(wv),

ma allora

V ^± (h ^± ) = D ^± (h ^± )(s) = X

− → sv∈ ~ E

h ^± (sv − ) − X

−

→ vs∈ ~ E

h ^± (sv + )

= X

−

→ sv∈ ~ E

h(sv) − X

−

→ vs∈ ~ E

h(sv) = V (h),

da cui

max

k∈ b H

V ^± (k) = max

h∈H

V ^± (h ^± ) = max

h∈H

V (h), (13)

uguaglianza che, combinata con (12) e con (11), dimostra la prima parte dell’asserto;

lasciamo la ormai facile dimostrazione della seconda parte (quella sull’integralit`a

del flusso) al lettore.