Uni.A-MetodiFF-EK History
Show minor edits - Show changes to output
Added lines 1-72:
(:title Metodi di Ford-Fulkerson e di Edmonds-Karp:)
[[Torna alla pagina di Algoritmi e strutture dati->Uni.Algoritmi]]
----
>>evvai<<
Questa pagina è stata aggiornata GRAZIE agli appunti che AVETE INVIATO nel periodo di chiusura della sezione UniCrema!! '''''È SERVITA A QUALCOSA, NO?!''''' [++;)++]
>><<
%titolo%''':: 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.
%center%Attach:A-esReteFlusso.gif
!!!!!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
%center%Attach:A-esReteResidua.gif
%center%Attach:A-esTaglio.gif
->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'^2^' 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->Uni.Algoritmi]]
|
