Algoritmo di Ford-Fulkerson

Da Wikipedia, l'enciclopedia libera.

In informatica, l'algoritmo di Ford-Fulkerson permette di trovare il flusso massimo che attraversa un grafo da un punto ad un altro di questo.

Definizione formale del problema[modifica | modifica wikitesto]

Dati un grafo

G = (V, E), con V insieme dei nodi e E insieme degli archi,

e una capacità c

c(u,v) \geq 0 con (u, v) \in E

Si può definire flusso in G una funzione

f : V \times V \rightarrow \mathbb{R}

con le seguenti proprietà:

  • \forall u, v \in V,\; f(u,v) \leq c(u,v)
  • \forall u, v \in V,\; f(u,v) = -f(v,u)
  • \forall u \in V \setminus \{s,d\},\; \sum_{v \in V}f(u,v)=0 con s origine del flusso e d destinazione.

Il problema da risolvere è quindi trovare il massimo di f(s, d) dato un grafo G.

La complessità dell'algoritmo nel caso peggiore è O(|E| |f^*|), dove f^* denota il flusso massimo nella rete residua. La complessità dipende quindi dalla cardinalità degli archi e dal flusso massimo.

Esempio risolto[modifica | modifica wikitesto]

Risolvere un problema di flusso massimo significa calcolare la quantità massima di flusso (sia questo di informazione, elettricità, materiale, ecc.) che può passare da un punto definito della rete ad un altro (anch'esso definito).

Un esempio di un problema di flusso massimo è il seguente: "Calcolare quanta elettricità può arrivare all'Hotel Roma attraverso la seguente rete elettrica".

Ricerca operativa flusso massimo 01.png

In questo caso

  • Ricerca operativa flusso massimo 02.pngindicano i nodi della rete (ovvero le ramificazioni della rete elettrica)
  • Ricerca operativa flusso massimo 03.pngindicano i punti di partenza e arrivo(ovvero la centrale elettrica e l'Hotel)
  • Ricerca operativa flusso massimo 04.png indicano gli archi (ovvero i cavi elettrici e la loro relativa capacità massima)

Per risolvere i problemi di flusso massimo dobbiamo calcolare tutti i percorsi che il flusso può fare dal nodo di partenza a quello di arrivo (quindi all'aumentare del numero di nodi la difficoltà del problema aumenta notevolmente). Per fare in modo di considerare tutti i cammini possibili è conveniente seguire un determinato ordine; convenzionalmente si usa considerare sempre il cammino più alto disponibile. Un'altra importante regola in questi tipi di problemi è che nei nodi non si può accumulare, generare o cancellare materiale: ciò che entra deve anche uscire (eccezione fatta per il nodo di partenza e di arrivo).

Prima di continuare occorre introdurre una notazione:

  • Ricerca operativa flusso massimo 05.png

Da questa scrittura è facilmente intuibile che l'arco tra il nodo A e il nodo B è 4, cioè tra il nodo A e il nodo B possono passare al massimo 4 unità del flusso.

  • Ricerca operativa flusso massimo 06.png

Quest’altra notazione è equivalente: Dal nodo A al nodo B, in questo momento, possono passare solo 4 unità mentre tra il nodo B e il nodo A nessuna unità.

  • Ricerca operativa flusso massimo 07.png

Posso spostare 3 unità di materiale (o di flusso) dal nodo A al nodo B e me ne resta ancora 1 unità, mentre da B ad A ne posso rimandare indietro 3; questo secondo la regola per cui nei nodi non si genera né cancella materiale.

Consideriamo ora un esempio di problema di flusso massimo e vediamo in pratica come si risolve.

Ricerca operativa flusso massimo 08.png

Abbiamo la rete qui sopra descritta e dobbiamo calcolare il flusso massimo che può passare dal nodo “A - inizio” al nodo “G - arrivo”. Secondo quanto appena detto dobbiamo seguire tutti i cammini possibili seguendo uno specifico ordine: Consideriamo prima i cammini più alti.

Nel grafico il cammino più alto che collega “inizio” ad “arrivo” è ABCG ed il flusso massimo che può passare attraverso questo cammino è 3 (ovvero la minima tra le capacità degli archi). Elenchiamo il cammino seguito (e la relativa capacità) e aggiorniamo il grafico.

Ricerca operativa flusso massimo 09.png
Elenco degli archi
  • ABCG 3

Il cammino più alto ora è ABDG che ha capacità 1. Come prima lo elenchiamo ed aggiorniamo il grafico.

Ricerca operativa flusso massimo 10.png
Elenco degli archi
  • ABCG 3
  • ABDG 1

Dal nodo B attualmente non può uscire nulla (sia verso C sia verso D ha capacità zero) quindi ci si sposta sul nodo E.

Ricerca operativa flusso massimo 11.png
Elenco degli archi
  • ABCG 3
  • ABDG 1
  • AEFG 6

Ora il problema è concluso. Per calcolare il flusso massimo tra A e G si fa semplicemente la somma dei cammini trovati: 3+1+6=10.

In una schematizzazione di questo tipo del problema va prestata attenzione a due cose: La prima è che la somma delle capacità dei cammini trovati deve essere uguale alla somma delle capacità in entrata del nodo di arrivo.

Ricerca operativa flusso massimo 12.png

La seconda è che la somma tra le capacità di un arco è costante. Consideriamo ad esempio l'arco AB:

  • Ricerca operativa flusso massimo 13.png Nel primo passo era 5+0=5
  • Ricerca operativa flusso massimo 14.pngNel secondo passo era 2+3=5
  • Ricerca operativa flusso massimo 15.pngNel terzo passo era 1+4=5
  • Ricerca operativa flusso massimo 15.pngNel quarto passo era uguale al precedente quindi 1+4=5

Bibliografia[modifica | modifica wikitesto]

  • Cormen, Leiserson, Rivest Introduction to algorithms MIT Press

Altri progetti[modifica | modifica wikitesto]