Swappa : Uni / Metodi di Ford-Fulkerson e di Edmonds-Karp

Torna alla pagina di Algoritmi e strutture dati

Questa pagina è stata aggiornata GRAZIE agli appunti che AVETE INVIATO nel periodo di chiusura della sezione UniCrema!! È SERVITA A QUALCOSA, NO?! ;)

 :: Metodi di Ford-Fulkerson e di Edmonds-Karp ::

Problema del flusso massimo

Una rete di flusso è un grafo orientato in cui ogni arco ha una capacità positiva quindi maggiore o uguale di zero.
La rete di flusso ha due vertici significativi:

s: la sorgente;
t: il pozzo, vertice di destinazione.

Per ogni vertice c'è un cammino da s a t.

Il flusso è una funzione a valori reali che deve soddisfare delle proprietà:

vincolo di capacità: il flusso non può superare la capacità dell'arco, flusso <= capacità;
antisimmetria: il flusso da u a v posso vederlo come un flusso negativo da v a u;
conservazione del flusso: il flusso non può perdersi lungo il tragitto.

Il flusso può non essere sempre una quantità positiva (posso avere più sorgenti e più pozzi).
Dato rete di flusso, una sorgente s e un pozzo t, si vuole trovare un flusso di valore massimo da s a t.
Il flusso totale netto è la differenza fra il flusso totale uscente e il flusso totale entrante ed è uguale a zero.

METODO DI FORD–FULKERSON

Si definisce un metodo e non un algoritmo perchè può avere diverse implementazioni eseguite in tempi diversi però tutte basate su tre concetti:

cammini aumentanti: cammino non saturo che posso utilizzare ancora per trasmettere;
rete residua: grafo con archi di capacità residua diversa da zero. Gli archi sdoppiano se non sono saturi;
taglio di una rete di flusso: partiziono l'insieme dei nodi in due insiemi; sorgente e pozzo devono stare in due sottoinsiemi diversi. La capacità del taglio è la capacità degli archi che stanno in tutti e due i sottoinsiemi.

Si parte con f(u,v) = 0 per ogni u e v e quindi si aumenta iterativamente il valore del flusso cercando un cammino dalla sorgente s al pozzo t lungo il quale sia possibile inviare ulteriore flusso. Il procedimento termina quando non vi sono più cammini aumentanti.

Ford-Fulkerson-Method(G, s, t)

for “ogni u,v ∈ V[G]” do

f(u,v) ← 0

while “esiste un cammino aumentante p” do

“aumenta il flusso lungo p”

return f

FordFulkerson(G, s, t)

for “ogni uv ∈ E[G]” do

f(u,v) ← f(v,u) ← 0

while “esiste un cammino P da s a t in Gf” do

“calcola c(P) = min{cf(u,v) : uv arco di P}”

for “ogni arco uv di P” do

f(u,v) ← f(u,v) + c(P)

f(v,u) ← - f(u,v)

return f

Complessità: O(E f) dove E è il numero di archi e f è il flusso massimo.
Se le capacità legate agli archi non sono numeri interi, l'algoritmo appena visto potrebbe non terminare.

ALGORITMO DI EDMONDS–KARP

Questo algoritmo utilizza la visita in ampiezza.
Complessità: O(E² V)

Abbinamento massimo nei grafi bipartiti

L'insieme dei vertici si può dividere in S e D. Gli archi stanno sia in S che in D.
Devo trovare in insieme massimo di coppie distinte.
Il grafo non è orientato, i vertici rappresentano stazioni di commutazione, gli archi linee di trasmissione ed ogni arco è associato ad un numero che indica la probabilità che la linea di trasmissione trasmetta correttamente un messaggio.
Devo determinare il cammino più affidabile tra una coppia di vertici dati.

Torna alla pagina di Algoritmi e strutture dati