Problem maksimalnog toka

U teoriji optimizacije Problem maksimalnog protoka uključuje nalaženje podesnog protoka kroz jedno-izvornu jedno-završnu transportnu mrežu koja je maksimalna.

Primer Transportne mreže sa maksimalnim protokom izvor je s, a zabršni čvor je t, brojevi označavaju protok i kapacitet

Problem maksimalnog protoka se može posmatrati kao specijalni slučaj kompleksnijih problema transportnih mreža kao što je problem kruženja. Maksimalna vrednost s-t toka(odnosno toka od izvora ka završnom toku je jednak minimalnom kapacitetu s-t preseka(odnsno preseka od s do t) u mreži, kao što je navedeno u maksimalni-protok minimalni-presek teoremi. _TOC_

Istorija

Problem Maksimalnog toka je prvi put formulisan 1954 od strane T. E Harris kao pojednostavljen model toka sovjetske železnice. U 1955. godini Lester R. Ford. Jr i Delbert R. Fulkerson napravili su prvi poznati algoritam Ford-Fulkerson algoritam.

Tokom vremena otkrivena su razna poboljšana rešenjaProblema maksimalnog protoka, posebno algoritam najraće promene puta od Edmondsa i Karpa i nezavisno Dinitz-a. Algoritam blokiaranja toka od Dinitz-a. Algoritam guranja-oznake od Goldberg-a i Tarjan-a. Binarno blokiranje toka Goldberg-a i Rao-a. Algoritam električnog toka Kristiano, Kelner, Madri i Spielman-a nalazi otprilike optimalan maksimalni tok , ali radi samo sa neusmerenim grafovima.

Definicija

Transportna mreža ca izvorom s , i ponorom t. Brojevi pored čvorova su kapaciteti

Neka je N=(V, E) mreža sa s, t∈V čvorovima koji su izvor i ponor od N respektivno Kapacitet čvora je slikanje c:E→R⁺ gde je C_uv ili C(u, v). Predstavlja makcimalan protok kroz čvor. Protok je slikanje f:E'→R⁺ gde je f_{u, v} ili f(u, v) pod utiskom ograničenja:

1.f_uv≤c_uv za svako (u, v)∈V(Ograničenje kapaciteta:protok kroz čvor ne može da nadmaši njegov kapacitet)

2.Σ_{u:(u, v)∈E}f(u, v)=Σ_{u:(u, v)∈E}f_sv za svako v∈B\{s, t}(Konzervacija protoka:suma protoka koja ulazi u čvor mora da bude jednaka sumi protoka koja izlazi iz čvora , osim izvora i ponora).

Vrednost protoka je deFinisana jednakošću |f|=Σ_{v:(s, v)∈E}f_sv gde s je izvor od N. Predstavlja količinu protoka koja prolazi od izvora do ponora.

u Problemu maksimalnog protoka treba maksimizovati |f| , tako da postoji što više protoka od s do t.

Rešenja

Mozemo da definišemo rezidualni graf koja daje sistematični način za traženje unapred-unazad operacije. da bi mogao da se nađe maksimalni protok.

Sa zadatom transportnom mrežom G , i protokom f u g , možemo da deFinišemo rezidualni graf G_f od G sa respektom po f kao što sledi:

1. Skup čvorova od G_f je isti kao i G.

2. Svaki čvor e=(u, v) od G_f je sa kapacitetom od C_e-F(e).

3. Svaki čvor e'=(v, u) G_f je sa kapacitetom od f(e).

Sledeća tabela prikazuje algoritme za rešavanje problema maksimalnog protoka.

Metoda	Kompleksnost	Opis
Linearno programiranje		Ograničenja su zadata sa definicijom legalnog protoka.
ford-fulkerson algoritam	O(maks f)	Sve dok postoji putanja kroz Rezidualni graf, poslati minimum preostalih kapaciteta kroz putanju. Algoritam radi camo ako su sve težine celi brojevi. Inače je moguće da ford-fulkersonov algoritam neće konvergirati ka maksimalnoj vrednosti.
Edmonds-Karp algoritam	O(VE2)	Specijalizacija ford-fulkerson algoritma , nalaženje uveličavajuće putanje sa pretragom grafa u širinu.
Dinitcovo blokiranje protoka algoritma	O(V2E)	U svakoj Fazi algoritma gradi se slojevit graf sa pretragom u širinu u rezidualnom grafu. Maksimalni protok u slojevitom grafu može biti izračunat u O(VE) vremenu, a maksimalni broj Faza je n-1. U mrežama sa jediničhim kapacitetima , Dinitcov algoritam se završava u O(Ekoren(V))
Generalni puš-relabel algoritam maksimalnog protoka	O(V2E)	Puš-relabel algoritam održava predtok takođe tok funkcije sa mogućnošću viška u čvorovima. Algoritam se izvršava dok postoji čvor sa viškom takođe aktivnim čvorom u grafu. Puš operacija povećava protok na rezidualnim granama , a visina na kontrolama grafa čije se rezidualne grane mogu "gurnuti“. Visina funkcije je promenjena sa relabel operacijom. Korektna definicija ovih operacija garantuje da je rezultujući protok funkcije je maksimalni protok
Puš-relabel algoritam sa fIfO pravilom selekcije čvora	O(V3)	puš-relabel algoritam varijanta koja uvek bira najskorije korišćen aktivni čvor i izvodi puš operacije dok ostatak nije pozitivan ili dok ne postoji prihvatljiv ostatak grana od ovog čvora
Dinitcovo blokiranje protoka algoritma sa dinamičkim drvetom	O(VElog(V))	Strustura podataka dinamičkog drveća ubrzava izračunavanje maksimalnog protoka u slojevitom grafu do O(E log(B))
Puš-relabel algoritam sa dinamičkim drvetom	O(BElog(B2/E))	Algoritam gradi drveća ograničehe veličine na rezidualnom grafu s obzirom na visinu funkcije. Ova drveća daju više-nivoa puš operacije
Binarno blokiranje protoka sa dinamičkim drvetom	O(Emin(V2/3/sup>, koren(E))log(V2/E)log U)	Vrednost U odgovara maksimumu kapaciteta mreže.
MPM(Malhotra, Pramodh-Kumar i Maheshvari) Algoritam	O(B3)
Džim Orlinov + KRT(King, Rao, Tarjan) Algoritam	O(VE)	Orlinov algoritam rešava problem maksimalnog protoka u O(VE) vremenu za m≤O(h(16/15)-e) dok ga KRT rešava u O(VE) za m>n1+e

Teorema integralnog toka

Po teoremi integralnog toka:

Ako svaki čvor u transortnoj mreži ima integralni kapacitet , onda postoji integralni maksimum protoka.

Upotreba

Transformacija više-izvornog , više-ponornog problema maksimalnog protoka u jedno-izvorni , jedno-ponorni problem maksimalnog protoka (figura4.1.1)

Transformacija problema maksimalnog bipartitivnog uparivanja u problem maksimalnog protoka (figura4.3.1)

Trasformacija problema maksimalnog protoka sa ograničenjima kapacitetima čvorova u originalni problem maksimalnog protoka razdvajanjem čvorova (figura4.4.1)

Više-izvorni više-ponorni problem maksimalnog protoka

sa zadatom mrežom N=(V, E) sa skupom izvora S={s₁, ..., s_n} i skup ponora T = {t₁, ..., t_n} umesto samo jednog izvora i ponora Treba da nađemo maksimalni protok preko n. Možemo da transformišemo više-izvorni, više-ponorni problem u problem maksimalnog protoka dodavanjem integrisanog izvora koji se povezuje za svaki čvor u S i integrisani ponor za koji su svi čvorovi iz T povezani(Takođe poznati kao super-izvor i super-ponor)Sa beskonačnim kapacitetom na svakoj grani(videti figuru 4.1.1).

Pokrivač minimalne putanje u direktnom acikličnom grafu

Sa zadatim grafom G=(V, E) treba da nađemo minimalni broj putanja da pokrijemo svaki čvor u V. Možemo da konstruišemo bipartitivni graf G=(V_izlazno∪V_ulazno, E) od G gde:

1. V_izlazno={v∈V: v ima pozitivan izlazni stepen}.

2. V_ulazno={v∈V: v ima pozitivan ulazni stepen}.

3. E = {(u, v)∈(V_izlazno, V_ulazno): (u, v)∈E}.

Onda može biti prikazano preko Konigove teoreme G ima usaglašenu veličinu od m samo ako postoji n-m putanja koji pokrivaju svaki čvor u grafu G gde je n broj čvorova u G. Dakle problem se može rešiti nalaženjem maksimalnog broja uparivanja u G.

Maksimalna brojnost bipartitivnog uparivanja

Sa zadatim bipartitivnom grafom G=(Z∪Dž, E) Treba da nađemo maksimalni broj povezivanja u G , to je povezivanje koje sadrža maksimalni mogući broj grana. Ovaj problem se može trasformisati u problem maksimalnog protoka konstruisanjem mreže N = (Z∪Dž∪{s, t}, E' } gde:

1. E sadrži grane u G usmerene od Dž do Z

2.(s, dž)∈E' za svako dž∈Dž i (z, t)∈E' za svako z∈Z

3.c(e)=1 za svako e∈E'

Onda Maksimalna vrednost Protoka u N je jednaka veličini maksimalnog uparivanja u G.

Problem Maksimalnog protoka sa kapacitetom čvorova

U zadatoj mreži N=(V, E) gde posotji kapacitet za svaki čvor , kao i za svaku granu postoji preslikavanje c:V→R⁺ obeleženo sa c(v) tako da protok f mora da ispunjava uslove ograničenja kapaciteta kao i konzervacije protoka i takođe ograničenje kapaciteta čvorova.

Σ_i∈V f_iv≤c(v) za svako v∈V\{s, t}

drugim rečima količina protoka koja prolazi kroz čvor ne može da nadmašuje njegov kapacitet.

Da bi se našao maksimalni protok kroz N Mo+emo da trnsformišemo problem u prvobitni problem maksimalnog protoka tako što ćemo da proširimo N. Prvo svaki v∈V zamenimo sa v_ulazno i v_izlazno , gde je v_ulazno povezano granama koje ulaze u v , a v_izlazno je povezano granama koje izlaze iz v, onda pridodati kapacitet c(v) grani koja povezuje v_ulazno i v_izlazno(videti figuru 4.4.1 ali opaziti da su v_ulazno i v_izlazno pogrešno zamenjeni). U ovoj proširenoj mreži ograničenje kapaciteta čvorava je uklonjeno pa se problem može tretirati kao prvobitni problem maksimalnog protoka.

Maksimalna nezavisna putanja

Sa zadatim usmerenim grafom G=(V, E) i dva čvora s i t , treba da nađemo maksimalni broj nezavisnih putanja od s do t. Dve putanje su nezavisne ako nemaju zajednički čvor osim s i t. Možemo da konstruišemo mrežu N=(V, E) od grafa g sa kapacitetima čvorova gde:

1.s i t su izvor i ponor od N u tom redosledu.

2.c(v)=1 za svako v∈V

3.c(e)=1 za svako e∈E

Onda je vrednost maksimalnog protoka jednaka Maksimalnom broju putanja od s do t.

Maksimalna putanja disjunktnih grana

Sa zadatim usmerenim grafom G=(V, E) i dva čvora s i t treba da nađemo maksimalni broj putanja sa disjunktnim granama od s do t. Ovaj problem možemo da transformišemo u problem maksimalnog protoka konstruisanjem mreže N=(V, E) iz G gde su s i t izvor i ponor (u tom redosledu) i svakoj grani pridružimo jedinični kapacitet.

Vidi još

Problemi minimalne cene protoka