Molnár-Szipai Richárd:
A maximális hálózati folyam feladat néhány polinomiális algoritmusa
<br><br>
A hálózati folyam feladat egy intuitívan egyszerű, mégis sok
alkalmazási területtel bíró matematikai modell. Az elmélet klasszikus
eredményeit Ford és Fulkerson dolgozták ki az 1950-es évek végén, majd
az általuk definiált javítóutak segítségével Edmonds és Karp, valamint
Dinic adtak polinomiális algoritmust maximális folyam keresésére
(1971). Ezen algoritmusok O(n^2 m) lépésben oldják meg a problémát,
ahol n a gráf csúcsainak, m pedig az éleinek száma.
<br><br>
Az előadás során a később kifejlesztett, talán kevésbé ismert
algoritmusokat fogjuk áttekinteni. Foglalkozunk először Karzanov
algoritmusával, mely Dinic algoritmusához hasonló struktúrát használva
egyszerűbb feladatok sorozatán keresztül jut el az optimális
megoldásig. Ezt az első úgynevezett előfolyamos algoritmusnak szokás
tekinteni, itt már csak a részfeladatok végén van "valódi" folyamunk,
közben csak előfolyamunk. Ezután áttekintjük Goldberg és Tarján
algoritmusát, mely a csúcsok egy cimkézésén alapul, és Karzanov
algoritmusához hasonlóan O(n^3) lépést igényel. Itt Azonban az
optimalizálás egy fázisban történik, az előfolyam csak az utolsó
lépésben válik valódi folyammá. Végül szó lesz a hálózati szimplex
algoritmusról, mely a lineáris programozás pivot algoritmusát ötvözi a
hálózati folyam gráfstruktúrájával. Itt Goldfarb és Hao algoritmusát
fogjuk bemutatni, akik szintén egy cimkézéses technikával biztosítják
az algoritmus polinomialitását.