Algoritmo di Ford-Fulkerson

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. Il nome deriva dai suoi due ideatori, Lester Randolph Ford e Delbert Ray Fulkerson.

Definizione formale del problema

Lo stesso argomento in dettaglio: Problema del flusso massimo.

Dati un grafo

${\displaystyle G=(V,E)}$, con V insieme dei nodi e E insieme degli archi,

e una capacità c

${\displaystyle c(u,v)\geq 0}$ con ${\displaystyle (u,v)\in E}$

Si può definire flusso in G una funzione

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

con le seguenti proprietà:

• ${\displaystyle \forall u,v\in V,\;f(u,v)\leq c(u,v)}$
• ${\displaystyle \forall u,v\in V,\;f(u,v)=-f(v,u)}$
• ${\displaystyle \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 ${\displaystyle f(s,d)}$ dato un grafo G.

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

Esempio risolto

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

In questo caso

• indicano i nodi della rete (ovvero le ramificazioni della rete elettrica)
• indicano i punti di partenza e arrivo(ovvero la centrale elettrica e l'Hotel)
• 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:

• 

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.

• 

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

• 

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.

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.

Elenco degli archi ABCG 3

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

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.

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.

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

• Nel primo passo era ${\displaystyle 5+0=5}$
• Nel secondo passo era ${\displaystyle 2+3=5}$
• Nel terzo passo era ${\displaystyle 1+4=5}$
• Nel quarto passo era uguale al precedente quindi ${\displaystyle 1+4=5}$

Bibliografia

• Cormen, Leiserson, Rivest Introduction to algorithms MIT Press

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Algoritmo di Ford-Fulkerson

Portale Informatica

Portale Matematica