Teorema del flusso massimo e taglio minimo

Il teorema del flusso massimo e taglio minimo (conosciuto anche come max-flow min-cut) dice che, in una rete di flusso, il massimo flusso passante dalla sorgente (il nodo iniziale) al pozzo (il nodo finale) è uguale alla somma dei pesi degli archi nel taglio minimo.

Si tratta di una generalizzazione del problema primale standard, tipico della programmazione lineare.

Il teorema fu dimostrato da P. Elias, A. Feinstein, e C.E. Shannon nel 1956, e indipendentemente anche da L.R. Ford Jr. e D.R. Fulkerson nello stesso anno.^[1]

Sia ${\displaystyle N=(V,E)}$ una rete di flusso, con s e t rispettivamente sorgente e pozzo di N.

Lo stesso argomento in dettaglio: Problema del flusso massimo.

Definizione. Un flusso è una funzione ${\displaystyle f:E\to R^{+}}$ che assegna ad ogni arco ${\displaystyle (u,v)\in E}$ un valore denotato con ${\displaystyle f_{uv}}$ o ${\displaystyle f(u,v)}$. Il flusso è soggetto a due vincoli:

1. Vincolo di capacità:

   ${\displaystyle \forall (u,v)\in E:\qquad f_{uv}\leq c_{uv}}$

2. Conservazione del flusso:

   ${\displaystyle \forall v\in V\setminus \{s,t\}:\qquad \sum \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\sum \nolimits _{\{u:(v,u)\in E\}}f_{vu}.}$

Definizione. La capacità è una funzione ${\displaystyle c:E\to R^{+}}$ che assegna ad ogni arco ${\displaystyle (u,v)\in E}$ un valore denotato con ${\displaystyle c_{uv}}$ o ${\displaystyle c(u,v)}$. Rappresenta il massimo flusso che può passare attraverso un arco.

Definizione. Il valore di flusso è costituito da:

${\displaystyle |f|=\sum \nolimits _{v\in V}f_{sv},}$

e rappresenta l'ammontare di flusso che parte dalla sorgente per arrivare al pozzo.

Definizione. Un taglio s-t ${\displaystyle C=(S,T)}$ è la partizione di V tale che ${\displaystyle s\in S}$ e ${\displaystyle t\in T}$. L'insieme di taglio di C è:

${\displaystyle \{(u,v)\in E\ :\ u\in S,v\in T\}.}$

Nota che se gli archi di C venissero rimossi, | f | = 0.

Definizione. La capacità di un taglio s-t è definita come

${\displaystyle c(S,T)=\sum \nolimits _{(u,v)\in S\times T}c_{uv}=\sum \nolimits _{(i,j)\in E}c_{ij}d_{ij},}$

dove ${\displaystyle d_{ij}=1}$ se ${\displaystyle i\in S}$ e ${\displaystyle j\in T}$, 0 altrimenti.

Minimum s-t Cut Problem. Determinare S e T tali che la capacità del taglio s-t sia minima.

Il valore massimo di un flusso s-t è uguale alla capacità minima fra tutti i tagli s-t.

Si introducono due teoremi fondamentali, chiamati teorema 1 e teorema 2, per semplificare la dimostrazione.

sia ${\displaystyle <V_{s},V_{t}>}$ un taglio della rete di flusso N con singola sorgente s e singolo pozzo t. Si ipotizzi un flusso ${\displaystyle f}$ tale che ${\displaystyle f(e)=c(e)}$ se ${\displaystyle e\in <V_{s},V_{t}>}$ e ${\displaystyle f(e)=0}$ altrimenti. Dove ${\displaystyle c(e)}$ è il valore della capacità dell'arco ${\displaystyle e}$.

Allora ${\displaystyle f}$ è il flusso di valore massimo in ${\displaystyle N}$ e ${\displaystyle <V_{s},V_{t}>}$ è il taglio di N di capacità minima.

Dimostrazione valore massimo:

Il valore di un flusso ${\displaystyle <V_{s},V_{t}>}$ è calcolato come ${\displaystyle \sum _{e\in <V_{s},V_{t}>}{f(e)}-\sum _{e\in <V_{t},V_{s}>}{f(e)}}$

Per un flusso ammissibile questo valore è uguale per ogni taglio ${\displaystyle <V_{s},V_{t}>}$ della rete N. Se consideriamo il flusso ${\displaystyle f}$ definito nelle ipotesi abbiamo che il valore del flusso diventa ${\displaystyle val(f)=\sum _{e\in <V_{s},V_{t}>}{f(e)}}$ siccome ogni arco entrate in ${\displaystyle V_{s}}$ ha flusso azzerato.

Ipotizziamo, per assurdo, che esista un flusso di valore superiore e chiamiamolo ${\displaystyle f^{*}}$. Ora consideriamo il taglio ${\displaystyle <V_{s},V_{t}>}$ su cui è stata costruita l'ipotesi.

${\displaystyle val(f^{*})=\sum _{e\in <V_{s},V_{t}>}{f(e)}-\sum _{e\in <V_{t},V_{s}>}{f(e)}>val(f)}$. Ma questo è chiaramente impossibile poiché la prima sommatoria ha valore massimo in ${\displaystyle f}$ (e quindi anche in ${\displaystyle f^{*}}$) e la seconda sommatoria può soltanto peggiorare il valore del flusso. Quindi otteniamo ${\displaystyle val(f^{*})=val(f)}$.

Dimostrazione taglio di capacità minima:

Per definizione di valore di un flusso abbiamo ${\displaystyle val(f)\leq cap(T)}$ dove ${\displaystyle cap(T)}$ è la capacità di qualsiasi taglio ${\displaystyle T}$ in una rete di flusso.

Per ipotesi il valore del flusso ${\displaystyle f}$ è ${\displaystyle val(f)=\sum _{e\in <V_{s},V_{t}>}{f(e)}=cap(<V_{s},V_{k}>)}$.

Per ogni altro taglio ${\displaystyle <V_{s}',V_{t}'>}$ di capacità diversa il valore del flusso è ${\displaystyle \sum _{e\in <V_{s}',V_{t}'>}{f(e)}-\sum _{e\in <V_{t}',V_{s}'>}{f(e)}}$.

Ma ${\displaystyle f}$ è un flusso ammissibile ${\displaystyle \sum _{e\in <V_{s}',V_{t}'>}{f(e)}-\sum _{e\in <V_{t}',V_{s}'>}{f(e)}=\sum _{e\in <V_{s},V_{t}>}{f(e)}\implies \sum _{e\in <V_{s}',V_{t}'>}{f(e)}>\sum _{e\in <V_{s},V_{t}>}{f(e)}\implies \sum _{e\in <V_{s}',V_{t}'>}{f(e)}>cap(<V_{s},V_{t}>)}$

sia ${\displaystyle f}$ un flusso in una rete di flusso s-t ${\displaystyle N}$, allora ${\displaystyle f}$ è il flusso di valore massimo se e solo^[2] se il grafo residuo ${\displaystyle N'}$ relativo al flusso ${\displaystyle f}$ non contiene un percorso da s a t e quindi non contiene un cammino aumentante.

Dimostrazione

Dimostrazione ${\displaystyle \Leftarrow }$:

Consideriamo ogni percorso in ${\displaystyle N'}$ che inizia da ${\displaystyle s}$ e creiamo un insieme ${\displaystyle V_{s}}$ composto da tutti i vertici che appartengono a questi percorsi.

Siccome non esiste cammino aumentante: ${\displaystyle t\notin V_{s}}$. Quindi consideriamo il taglio ${\displaystyle <V_{s},V_{t}>\;V_{t}=V\setminus V_{s}}$.

Ogni arco ${\displaystyle (w,j)\in <V_{s},V_{t}>}$ ha come valore di flusso ${\displaystyle f(w,j)=cap(w,j)}$ oppure ${\displaystyle f(w,j)=0}$ per costruzione del grafo residuo.

Quindi il taglio ${\displaystyle <V_{s},V_{t}>}$ soddisfa le ipotesi del teorema 1 e quindi ${\displaystyle f}$ è il flusso di massimo valore.

Il valore massimo di un flusso s-t è uguale alla capacità minima fra tutti i tagli s-t.

Dimostrazione

Il taglio elaborato nella dimostrazione del teorema 2 ha capacità pari al flusso di massimo valore.

Questa sezione sull'argomento matematica è ancora vuota. Aiutaci a scriverla!

• (EN) Jon Kleinberg, Éva Tardos, Algorithm Design, Addison-Wesley, 2005, ISBN 978-0-321-29535-4.

• Algoritmo di Ford-Fulkerson
• Problema del flusso massimo
• Programmazione lineare
• Quadratic pseudo-Boolean optimisation
• Rete di flusso
• Taglio (teoria dei grafi)

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica