• Non ci sono risultati.

Max Flow - Min Cut

N/A
N/A
Protected

Academic year: 2021

Condividi "Max Flow - Min Cut"

Copied!
9
0
0

Testo completo

(1)

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 n 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

0

=v

h(e) − X

e

00

=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 0 ) − f (e 00 ), (2)

(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 + 0 . 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);

(3)

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

0

∈S,e

00

∈ ¯ S

h(e) − X

e

00

∈S,e

0

∈ ¯ 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 0 ) − χ S (e 00 )]

= X

e∈K

S

h(e) [χ S (e 0 ) − χ S (e 00 )] = 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

0

∈S,e

00

∈ ¯ 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)

(4)

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 m ; dunque b H `e compatto e V : b H → R + 0 , 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 0 di un lato e tale che ¯h(e) < c(e), allora e 00 ∈ S;

c) se S contiene il secondo vertice e 00 di un lato e tale che ¯h(e) > 0, allora e 0 ∈ 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 0 = s, x 1 , x 2 , . . . , x l = t)

(5)

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 ; 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

i

∼e / ∈P

(−1) e,x

i

¯h(e)+(−1) x

i−1

x

i

,x

i

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

i

x

i+1

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

i

∼e / ∈P

(−1) e,x

i

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

= X

x

i

∼e / ∈P

(−1) e,x

i

¯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

0

x

1

6=e∼s

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

0

x

1

,s h (x 0 x 1 )

= X

x

0

x

1

6=e∼s

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

0

x

1

,s h (x 0 x 1 );

ora, se (−1) x

0

x

1

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

(−1) x

0

x

1

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

(6)

casi, si ha che

V (h ) = X

x

0

x

1

6=e∼s

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

0

x

1

,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

S

c(e) = X

~ e∈ ~ K

S

¯h(e) − X

−~ e∈ ~ K

S

¯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

i

⊂ 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

(7)

¯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 + 0 ; l’insieme dei flussi ammissibili, in questo caso, `e

H c = (

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

e

0

=v

h(e) = X

e

00

=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.

(8)

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 ± `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 ± `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 ± `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) 2) e la non negativit`a di h, vale

k(w + z ) ≤ X

e∈E

±

e

0

=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 + 0 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)

(9)

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

c

V ± (h ± ) = max

h∈H

c

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.

Riferimenti

Documenti correlati

Rinfusa - il prezzo massimo della farina di pesce si riferisce a merce di produzione cilena; per Igrassi franco arrivo. farina di pesce

Le quotazioni delle singole province si riferiscono ai diversi contratti conclusi nella settimana di riferimento e sono calcolate come media ponderata dei prezzi sulle

di produzione esclusivamente nazionale resa sul luogo di produzione, a pronta consegna e pagamento - I.V.A.. XL grandissime da 73 gr.. limitrofe con garanzie -.. Aflatossina B1

Le quotazioni delle singole province si riferiscono ai diversi contratti conclusi nella settimana di riferimento e sono calcolate come media ponderata dei prezzi sulle

CEREALI E COLTIVAZIONI INDUSTRIALI Modalità Regione Prezzo U.M.(p) Quantità U.M.(q) Grano duro. Frumento

avena Euro n.q.. orzo vestito naz. arrivo alla rinfusa) Euro n.q... Tritello di

di produzione esclusivamente nazionale resa sul luogo di produzione, a pronta consegna e pagamento - I.V.A.. XL grandissime da 73 gr.. limitrofe con garanzie - Aflatossina B1 max..

Le quotazioni delle singole regioni si riferiscono ai diversi contratti conclusi nella settimana di riferimento e sono calcolate come media ponderata dei prezzi sulle quantità