PROBLEMA FLUXULUI MAXIM ÎN REȚELE – ANALIZA ȘI SINTEZA ALGORITMILOR DE SOLUȚIONARE

Tatiana PAȘA Universitatea de Stat din Moldova

Rezumat

În lucrare se propune o prezentare generală a algoritmilor de soluționare a problemei fluxului maxim în rețele de transport. Sunt descrise tehnicile de bază utilizate de-a lungul timpului începând cu primul algoritm propus de L.R. Ford și D.R. Fulkerson [1]. Se aduc referințe la acei autori care cercetează această problemă pentru cazuri speciale, cum sunt grafuri neorientate, bipartite sau cu câteva destinații și surse. Cuvinte-cheie: rețea de transport, flux maxim, capacitatea arcului, capacitatea vârfului, graf rezidual, tăietură minimă, drum de creștere, sursă, destinație.