Flux si Cuplaj

(Categoria Algoritmi, autor Mircea Dima)

1. Retele de transport
2. Algoritmiii Ford Fulkerson si Edmonds-Karp
   • UVA 10735
   • PKU 2391
3. Algoritmul lui Dinic si algoritmul lui Karzanov
   • Tero
4. Taietura minima in graf / conexiune de muchii
   • Hardware Store
   • SPOJ Optmark
   • ZJU 2429
5. Flux cu capacitati inferioare si superioare
   • SGU 176
   • Drumuri2
   • Joc (finala .campion 2006)
6. Cuplaj in graf bipartit
7. Algoritm de flux maxim pentru cuplaj
   • CEOI 2002 Guards
   • PKU 2226
8. Cuplaj folosind lanturi alternante (cunoscut si ca PairUp)
   • Dicing/KOS polonezi
   • PKU 3189
9. Algoritmul Hopcroft-Karp
   • Java
10. Suport in graf bipartit
    • Felinare
    • SGU 234
    • Knights - BalticOI 2001
11. Cuplaj maxim de cost minim (cu Bellman-Ford cu si fara coada)
    • Traseu
    • Trafic
    • SGU 252
    • UVA 10806
    • Problema chinezi
12. Cuplaj maxim de cost minim folosind Dijkstra
    • CC

1. Retele de transport

O retea de transport G=(V, E) este un graf orientat in care fiecarui arc (u, v) ∈ E ii este asociata o capacitate nenegativa c(u,v) >=0.
Vom distinge 2 varfuri importante in retea: varful sursa S si varful destinatie D.
Un flux in reteaua de mai sus este o functie f: V x V -> R care satisface urmatoarele conditii:

1. Restrictie de capacitate: pentru orice u, v ∈ V avem f(u, v)<=c(u, v)
2. Antisimetrie: pentru orice u, v ∈ V avem f(u, v)=-f(v, u)
3. Conservarea fluxului: pentru orice u ∈ V - {S, D} avem ∑ v ∈ V din f(u, v) = 0

Prima restrictie impune pur si simplu ca fluxul de la un varf la altul sa nu depaseasca valoarea capacitatii.
Antisimetria impune ca fluxul de la un varf u la un varf v sa fie egal cu opusul fluxului de la varful v la u. Astfel, fluxul de la un varf la el insusi este 0.
Conservarea fluxului impune ca "ceea ce intra intr-un nod sa fie egal cu ceea ce iese din nod"

Mai pe intelesul tuturor putem sa ne imaginam ca fiecare arc este o conducta pentru material. Fiecare conducta are o capacitate data, care este defapt ritmul maxim cu care lichidul se poate deplasa in conducta. De exemplu, printr-o teava pot curge cel mult 2000 litri de apa pe ora, sau pe un fir conductor un curent electric de maximum 20 amperi. Varfurile sunt jonctiunile conductelor si in afara varfului sursa si destinatie, materialul nu se poate acumula in nici un varf. Aceasta proprietate se numeste conservarea fluxului si este identica cu legea lui Kirchoff in cazul curentului electric.

2. Algoritmiii Ford Fulkerson si Edmonds-Karp

Ford-Fulkerson(c, f)
      f[i][j]=0 pt i,j=1,n
      cat timp exista un drum de ameliorare p executa
          mareste fluxul f de-a lungul drumului p
      returneaza f