Apri il menu principale

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]

Definizioni e formulazioneModifica

Sia   una rete di flusso, con s e t rispettivamente sorgente e pozzo di N.

Flusso massimoModifica

 Lo stesso argomento in dettaglio: Problema del flusso massimo.

Definizione. Un flusso è una funzione   che assegna ad ogni arco   un valore denotato con   o  . Il flusso è soggetto a due vincoli:

  1. Vincolo di capacità:
     
  2. Conservazione del flusso:
     

Definizione. La capacità è una funzione   che assegna ad ogni arco   un valore denotato con   o  . Rappresenta il massimo flusso che può passare attraverso un arco.

Definizione. Il valore di flusso è costituito da:

 

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

Taglio minimoModifica

Definizione. Un taglio s-t   è la partizione di V tale che   e  . L'insieme di taglio di C è:

 

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

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

 

dove   se   e  , 0 altrimenti.

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

Formulazione del teoremaModifica

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

DimostrazioneModifica

ApplicazioniModifica

NoteModifica

  1. ^ P. Elias, A. Feinstein, and C. E. Shannon, A note on the maximum flow through a network, IRE. Transactions on Information Theory, 2, 4 (1956), 117–119

BibliografiaModifica

Voci correlateModifica