Flusso Massimo Flashcards
Quali dati offre un problema di flusso massimo?
Capacità superiori degli archi, un nodo origine e un nodo destinazione.
In cosa consiste il problema del flusso massimo?
Consiste nel determinare la massima quantità di flusso che si può inviare da s a t attraverso G.
Cos’è il valore del flusso x?
E’ il bilanciamento del nodo sorgente, ovvero il flusso che va dal nodo sorgente al nodo pozzo.
Nel problema del flusso massimo, il vettore dei bilanci è…
nullo
Un flusso ammissibile non è ottimo se…
E’ possibile inviare altro flusso dall’origine alla destinazione.
La capacità di un cammino, theta, rappresenta …
la massima quantità di flusso che è possibile inviare lungo questo cammino.
Se la capacità di un cammino è maggiore del suo flusso
è detto un cammino aumentante.
Come trovare cammini aumentanti?
Con un grafo residuo.
In un grafo residuo…
Ogni arco del grafo originale può essere rappresentato in due modi:
nel suo verso originale se non è saturo,
e nel verso opposto se non è vuoto.
Per ogni cammino aumentante nel grafo originale…
esiste uno ed un solo cammino orientato nel grafo residuo.
Come si verifica l’esistenza di un cammino aumentante nel PFM?
Con una visita del grafo residuo.
Il flusso di un taglio è…
la quantità di flusso che attraversa il taglio.
Possiamo sfruttare i tagli in un problema di flusso massimo per dimostrare:
che x è un flusso massimo se determiniamo un taglio la cui capacità è uguale a v.
Nel problema del flusso massimo, il massimo valore dei flussi ammissibili su G…
E’ uguale alla minima capacità dei tagli di G che separano s da t.
Algoritmo per cammini aumentanti, ford-folkerson
- Parte da un flusso ammissibile
- ricerca un cammino aumentante
- aumenta il flusso lungo il cammino di una quantità theta.
- itera
Se le capacità degli archi sono numeri interi…
Allora esiste almeno un flusso massimo intero.
