ANDREJA URH

DIPLOMSKO DELO

ANDREJA URH

’tudijski program: Matematika in ra£unalni²tvo

Maksimalni pretoki na omreºjih

DIPLOMSKO DELO

Mentor: Kandidatka:

doc. dr. Primoº ’PARL Andreja URH

Ljubljana, junij 2015

strani. Zahvalila bi se tudi vsem prijateljem za spodbudne besede in pomo£.

Posebna zahvala gre mentorju doc. dr. Primoºu ’parlu za nasvete in strokovno po- mo£ pri nastajanju diplomskega dela.

algoritme za njegovo re²evanje. Natan£no analizirajte potek delovanja in £asovno zahtev- nost Edmonds - Karpovega in Goldberg - Tarjanovega algoritma.

V Ljubljani, maj 2013.

Mentor: doc. dr. Primoº ’parl

za problem, ki se v razli£nih oblikah pojavlja v raznih realnih situacijah. Nekatere tak²ne primere predstavimo tudi v diplomskem delu. Na za£etku diplomskega dela predstavimo problem maksimalnega pretoka in pokaºemo, da ima tak problem vedno optimalno re²itev.

Vpeljemo pojem minimalnega reza in obravnavamo njegovo povezavo s problemom maksi- malnega pretoka. V drugem delu diplomskega dela obravnavamo nekatere najbolj znane algoritme za iskanje maksimalnega pretoka. Najprej predstavimo Ford - Fulkersonov algo- ritem, nato pa se posvetimo predvsem Edmonds - Karpovemu in Goldberg - Tarjanovemu algoritmu. Pri vsakem izmed njiju analiziramo £asovno zahtevnost, pomembne lastnosti in s pomo£jo konkretnih primerov prikaºemo njuno delovanje.

Math. Subj. Class (2010): 05C21, 05C85

Klju£ne besede: maksimalen pretok, minimalen rez, Edmonds - Karpov algoritem, Goldberg - Tarjanov algoritem, £asovna zahtevnost

of this problem can in various practical situations. Some of these examples are presented in the thesis. The maximum ow problem is introduced and it is shown, that it always has an optimal solution. The concept of a minimal cut is dened and its connection to the maximum ow problem is investigated. In the second part of the diploma thesis some of the well known algorithms for searching the maximum ow are treated. First the Ford - Fulkerson algorithm is presented, than we concentrate mostly on the Edmonds - Karp algorithm and Goldberg - Tarjan algorithm. For each of these two algorithms the time complexity and the important characteristics are analyzed. Their operation is illustrated with a few concrete examples.

Key words: maximum ow, min cut,the Edmonds - Karp algorithm, the Goldberg - Tarjan Algorithm, time complexity

1 Uvod 1 1.1 Osnovni pojmi . . . 4 1.2 Linearno programiranje . . . 6

2 Problem maksimalnega pretoka 9

2.1 Problem maksimalnega pretoka . . . 10 2.2 Maksimalni pretok - minimalni rez . . . 16

3 Algoritmi 21

3.1 Ford - Fulkersonov algoritem . . . 22 3.2 Edmonds - Karpov algoritem . . . 34 3.3 Goldberg - Tarjanov algoritem . . . 43

4 Primerjava algoritmov in zaklju£ek 57

5 Izjava o avtorstvu 61

KAZALO

1.1 Primer usmerjenega grafa. . . 4

1.2 Primer digrafa na katerem imamo Eulerjev obhod. . . 5

2.1 Primer transporta izdelkov iz Ljubljane v Frankfurt. . . 10

2.2 Na prvi sliki vidimo primer digrafa s kapacitetami, na drugi sliki primer digrafa s pretokom in kapacitetami, ter na tretji sliki pridruºen digraf s pridruºenimi kapacitetami. . . 13

2.3 Primeri s-t rezov. . . 17

3.1 Primer preprostega grafa. . . 24

3.2 Prvo pove£anje pretoka vzdolº potis−a−b−t. . . 24

3.3 Drugo pove£anje toka vzdolº potis−b−a−t. . . 25

3.4 Maksimalen s-t pretok in pripadajo£i pridruºeni digraf. . . 26

3.5 Na levi je primer digrafa z ozna£enimi tremi povezavami, na desni pa digraf s kapacitetami. . . 26

3.6 Prvo pove£anje. . . 27

3.7 Naslednja tri pove£anja . . . 28

3.8 ’e nekaj korakov pove£anja. Na levih digrah je pove£ujo£a s-t pot, na desni pa so pridruºeni digra. . . 29

3.9 ’e nekaj korakov pove£anja. Na levih digrah je pove£ujo£a s-t pot, na desni pa so pridruºeni digra. . . 30 3.10 Na levem digrafu sta ozna£eni pove£ujo£i poti, na desni pa je pridruºeni

SLIKE

3.12 Primer delovanja Edmonds - Karpovega algoritma. . . 38

3.13 Prvo pove£anje po eni izmed najkraj²ih poti. . . 39

3.14 Drugo in tretje pove£ane pretoka. . . 39

3.15 ƒetrto pove£anje poti. . . 39

3.16 Drugi primer za Edmonds - Karpov algoritem. . . 40

3.17 Drugi in tretji korak. . . 41

3.18 ƒetrti oziroma zadnji korak. . . 42

3.19 Primer Goldberg - Tarjanovega algoritma. . . 46

Uvod

V vsakdanjem ºivljenju se sre£ujemo z razli£nimi problemi, za re²evanje le-teh pa se odlo-

£amo na razli£ne na£ine. Podobno je v matematiki. Tako v£asih re²ujemo probleme, pri katerih ºelimo izvesti neko stvar, pri tem pa bi radi to storili £im hitreje, £im bolj uspe²no in s £im manj²imi stro²ki. Pravimo, da bi radi zadevo izvedli optimalno. Gre torej za optimizacijske probleme.

Poglejmo si nekaj prakti£nih primerov. Prvi primer je povezan s cestnimi povezavami, po katerih vsakodnevno potujemo in se vozimo iz enega kraja v drugega. Pred samo potjo se odlo£amo, po kateri poti bi se peljali, da bi bila na²a pot £im kraj²a, da bi porabili £im manj goriva, da smo racionalni pri pla£ilu cestnin ter smo £im hitreje na cilju. Podobne primere sre£amo pri avtobusnih, ºelezni²kih, letalskih ali drugih prevozih. Zanima nas, kako uskladiti vozni red za prevoze iz enega kraja v drug kraj, da se prevozna sredstva nemoteno gibljejo med seboj, da so na neki liniji prevozi dovolj pogosto, da na isti liniji isto£asno ne peljeta dve prevozni sredstvi, itd. Pri tem je potrebno obi£ajno upo²tevati

²e, da so zaposleni enakomerno razporejeni glede na njihov delovnik. Upo²tevati moramo, da so stro²ki £im niºji. Podobno je tudi v podjetjih, kjer ºelimo narediti £im ve£ izdel- kov v £im kraj²em £asu, s £im niºjimi stro²ki ter pri tem optimalno porazdeliti delovno silo.

Na²tetih je zgolj nekaj konkretnih primerov iz prakse, za katere lahko ugotovimo, da

matematike, ki se ukvarja s problemi, kako iz (obi£ajno kon£ne ali pa kve£jemu ²tevno neskon£ne) dane mnoºice poiskati najbolj²o re²itev glede na izbrane kriterije. Kombina- tori£na optimizacija obsega razli£ne dobro znane optimizacijske probleme, kot so problem trgovskega potnika, problem maksimalnega prirejanja, problem barvanja grafov, itd. Za re²evanje tak²nih optimizacijskih problemov uporabljamo posebne metode oziroma algo- ritme, ki nas pripeljejo do optimalne re²itve. Ta je lahko maksimalna ali minimalna vre- dnost funkcije, ki podaja kriterije optimalnosti v podani mnoºici re²itev, oziroma element opazovane mnoºice, pri kateri kriterijska funkcija doseºe maksimum oziroma minimum.

Eden izmed problemov, s katerimi se ukvarja kombinatori£na optimizacija, je tudi problem maksimalnega pretoka. Slednji je glavna tema tega diplomskega dela. Kaj je maksimalni pretok bomo natan£neje izvedeli v naslednjem poglavju. Da pa laºje razumemo problem maksimalnega pretoka si poglejmo na primeru. Podano imamo neko mreºo mest in pove- zav med njimi. Radi bi iz poljubno izbranega mesta v neko drugo poljubno izbrano mesto prepeljali £im ve£ tovora, pri £emer se moramo drºati omejitev o koli£ini na posameznih povezavah. Katere poti izbrati? Za re²evanje problema maksimalnega pretoka poznamo kar nekaj (u£inkovitih) algoritmov. To so Ford - Fulkersonov algoritem, Edmonds - Kar- pov algoritem, Goldberg - Tarjanov algoritem in drugi. Podrobno so predstavljeni v 3.

poglavju.

Poglejmo si konkreten primer problema maksimalnega pretoka. Imejmo primer podzemne jame, ki ima vhod v jamo drugje kot izhod. Po jami se lahko sprehajamo po razli£nih poteh, ki se med seboj lahko kriºajo. Poti v jami so razli£nih ²irin in so zato nekatere bolj, druge manj prehodne. Znano je, koliko obiskovalcev gre lahko naenkrat po poljubni poti. Zanima nas, koliko obiskovalcev lahko naenkrat spustimo v jamo. Pri tem predpo- stavljamo, da se obiskovalci v nobenem trenutku ne zadrºujejo na nekem mestu, ampak se ves £as premikajo po jami. V kontekstu zgornjega poenostavljenega opisa problema maksimalnega pretoka bi bila za konkreten primer mesta kriºi²£a poti, povezave med mesti pa bi predstavljale podzemne poti. Izbrani mesti, med katerimi po²iljamo tovor, sta seveda vhod in izhod v jamo. ’irine poti so omejene in povedo, koliko obisko- valcev gre lahko po posamezni poti. Predpostavimo, da so kriºi²£a dovolj ²iroka, da se obiskovalci lahko sre£ajo.

V preostanku tega uvodnega poglavja si poglejmo ²e osnovne pojme, katere bomo vse- skozi uporabljali ter na kratko ponovimo kaj je linearno programiranje. V 2. poglavju se bomo posvetili teoreti£nemu ozadju problema maksimalnega pretoka in si pogledali njegovo povezavo z minimalnimi rezi. V 3. poglavju bomo podrobno predstavili nekatere algoritme, s katerimi re²ujemo problem maksimalnega pretoka. Primerjavo med algoritmi si pogledamo v zaklju£ku.

1.1. OSNOVNI POJMI

1.1 Osnovni pojmi

V tem razdelku bomo spoznali nekaj osnovnih pojmov, katere bomo vseskozi uporabljali.

Snov je povzeta po knjigah [4] in [6].

Usmerjen graf oziroma digraf D je urejena trojica (V(D), E(D),Φ_D), kjer je V(D) mnoºica vozli²£, E(D)mnoºica povezav ali lokov in

Φ_D :E(D)→V(D)×V(D)\{(v, v) :v ∈V(D)}.

ƒe je Φ(e) = (u, v), pravimo, da je u za£etno, v pa kon£no vozli²£e povezave e. Re-

£emo tudi, da je v tem primeru povezava e usmerjena od u k v. V primeru, ko med nobenima vozli²£ema nimamo dveh povezav, usmerjenih v isto smer, preslikave ΦD ne potrebujemo, saj lahko povezave ozna£imo kar s pripadajo£imi urejenimi pari (u, v), kjer sta u in v razli£ni vozli²£i iz mnoºice V(D). V tak²nem primeru potem govorimo kar o digrafu D = (V(D), E(D)). Naj bo D₁ = (V(D₁), E(D₁),Φ_D1) poljuben digraf. Tedaj je D₁ podgraf digrafa D, £e veljaV(D₁)≤V(D)in E(D₁)≤E(D).

Na sliki 1.1 si poglejmo primer digrafa, kjer je V(D) = {s, a, b, c, t} mnoºica vozli²£, E(D) = {f1, f2, . . . , f6} pa mnoºica povezav. Preslikava ΦD je v tem primeru podana s predpisom Φ_D : f₁ 7→(s, a), f₂ 7→(s, b),f₃ 7→(a, c), f₄ 7→(c, b),f₅ 7→(c, t)inf₆ 7→(b, t). Vidimo, da v tem primeru preslikave Φ_D ne potrebujemo, saj je vsaka povezava natanko dolo£ena ºe s pripadajo£im urejenim parom vozli²£. Zato bomo tudi mi odslej preslikavo Φ_D vedno izpu²£ali, razen £e jo bomo zares potrebovali (£e bomo imeli ve£kratne vzpore- dne povezave.

Slika 1.1: Primer usmerjenega grafa.

Naj bo v poljubno vozli²£e iz mnoºice vozli²£ V(D). Stopnja vozli²£av je ²tevilo pove- zav, katerih za£etno ali kon£no vozli²£e je v. Ozna£imo jo z deg_D(v). V na²em primeru digrafa na sliki 1.1 so vozli²£a s, a in t stopnje 2, vozli²£i b in c pa sta stopnje 3. Pri ra£unanju stopnje torej usmeritve povezav niso pomembne.

Sprehod dolºine k v digrafu D je zaporedje k zaporednih povezav digrafa D, kjer sta povezavi zaporedni, £e je konec prve povezave in za£etek druge povezave v istem voz- li²£u. V zgornjem digrafu D je na primer zaporedje povezav (s, a), (a, c), (c, t) sprehod dolºine 3. V primeru, ko v digrafu nimamo vzporednih ve£kratnih povezav (in torej ne potrebujemo preslikave Φ_D), tak sprehod ozna£imo kar z s−a−c−t in re£emo, da gre za sprehod od vozli²£a s do vozli²£a t. Re£emo tudi, da je to s-t sprehod. ƒe so vse povezave in vsa vozli²£a na sprehodu razli£na, sprehod poimenujemo pot. ƒe sta za£etno in kon£no vozli²£e sprehoda enaka, sprehod imenujemo obhod. Obhod, ki vsebuje vsako povezavo grafa natanko enkrat, je Eulerjev obhod. ƒe graf vsebuje Eulerjev obhod je graf Eulerjev.

Na sliki 1.2 si poglejmo primere poti, sprehoda in Eulerjevega obhoda. Najprej si po- glejmo nekaj primerov poti. To so na primer a−d−f, b−a−c, c−b−d−e−f in f−a−d−e−b. Primer sprehoda, ki ni pot, je a−c−e−f−c−b−d in primer obhoda je lahkoa−d−f−c−e−b−a. Na tem digrafu pa lahko najdemo tudi Eulerjev obhod, na primer c−e−b−a−d−f −a−c−b−d−e−f−c. Tu se lepo vidi, da Eulerjev obhod vsebuje vsako povezavo natanko enkrat in se vrne v za£etno vozli²£e.

b c

e a

d f

Slika 1.2: Primer digrafa na katerem imamo Eulerjev obhod.

1.2. LINEARNO PROGRAMIRANJE

1.2 Linearno programiranje

V naslednjem poglavju bomo dokazali izrek, da ima problem maksimalnega pretoka ve- dno re²itev. Dokaz temelji na teoriji linearnih programov. Zato bomo v tem razdelku na kratko spoznali osnovne pojme te teorije. Snov je deloma povzeta po [2].

Linearno programiranje je metoda za re²evanja optimizacijskih problemov, pri katerih je dopustna mnoºica (to je mnoºica, v kateri i²£emo optimalni element) podana s samimi linearnimi enakostmi in/ali neenakostmi, prav tako pa je linearna tudi cenovna funkcija.

Od konkretnega problema je odvisno ali i²£emo njen minimum ali maksimum.

Poglejmo si najprej za£etke linearnih programov. Prve metode re²evanja linearnih pro- gramov segajo v leto 1939, ko je ruski matematik L. V. Kantorovich²tudiral optimizacijo razvozov v lesni industiji. V tem £asu se je linearno programiranje razvijalo tudi med ameri²kimi znanstveniki. Leta 1941 je ameri²ki matematik F. L. Hitchcock objavil ²tu- dijo o transportnem problemu, leta 1947 pa je G. B. Dantzig razvil najbolj znano metodo za re²evanje linearnih programov, imenovano metoda simpleksov. Linearno programiranje je nato za£elo hitreje napredovati z razvojem ra£unalnikov.

Linearen program deniramo kot problem, pri katerem je potrebno dolo£iti vredno- sti realnim spremenljivkam x_i, kjer je i = 1, . . . , n, pri tem pa vrednosti dolo£imo glede na omejitvene linearne neena£be ali ena£be (tu prikazujemo primer, ko so vse omejitve podane z neena£bami)

a₁₁x₁ + a₁₂x₂ +· · ·+ a_1nx_n ≤ b₁, a₂₁x₁ + a₂₂x₂ +· · ·+ a_2nx_n ≤ b₂,

...

a_m1x₁+a_m2x₂+· · ·+a_mnx_n ≤b_m, tako, da je linearna cenovna funkcija

f(x₁, x₂, . . . , x_n) = c₁·x₁+. . .+c_n·x_n

minimalna ali maksimalna. Pri tem lahko zahtevamo tudi, da so nekatere ali vse spre- menljivke x_i nenegativne. Mnoºico re²itev omejitvenih linearnih neena£b imenujemo do- pustna mnoºica. Pri tem so koecienti a_ij, b_i inc_j poljubna realna ²tevila.

Zgornji linearen program lahko zapi²emo tudi s pomo£jo matrik in vektorjev, kjer je A∈R^m×n, b∈R^m in c ∈Rⁿ. Koeciente a_ij iz neenakosti zberemo v matriko A:

A =















a₁₁ a₁₂ . . . a_1n a₂₁ a₂₂ . . . a_2n ... ... ... ...

a_m1 a_m2 . . . a_mn













 .

Koecienti na desni strani neena£b so komponente vektorja b, koecienti cenovne funk- cije pa komponente vektorja c. ƒe vse omejitvene pogoje zapi²emo kot linearne enakosti hkrati pa zahtevamo, da so vse spremenljivke x_j nenegativne, gre za linearen program v kanonski obliki. Ko pa imamo pogoje zapisane kot same neenakosti in so vse spremen- ljivke nenegativne, tedaj pravimo, da gre za linearen program v standardni obliki. Ni teºko videti, da vedno obstaja pretvorba iz ene v drugo obliko.

Za nadaljevanje diplomskega dela potrebujemo rezultat, ki poda zadosten pogoj, da ima linearen program vsaj eno re²itev. Ker je dokaz tega dejstva precej netrivialen, se ne bomo spu²£ali v podrobnosti. Bralcu, ki bi o linearnem programiranju ºelel izvedeti ve£, v branje priporo£amo [2].

Izrek 1. Linearen program, katerega dopustna mnoºica je neprazna, cenovna funkcija pa je na njej omejena, ima vsaj eno optimalno re²itev.

Kljub temu, da je simpleksni algoritem, ki ga obi£ajno uporabljamo za re²evanje linearnih programov, relativno hiter, nekatere probleme, ki jih je mo£ re²iti s prevedbo na linearen program, re²ujemo z druga£nimi, hitrej²imi algoritmi. Eden izmed takih primerov je problem maksimalnega pretoka.

1.2. LINEARNO PROGRAMIRANJE

Problem maksimalnega pretoka

V uvodu smo ºe omenili, da bomo v tem poglavju spoznali problem maksimalnega pre- toka. Opisali bomo pojme in rezultate, ki se uporabljajo v tej teoriji. Snov je povzeta po knjigi [4].

še v uvodu smo spoznali primer prehoda skozi jamo, ki je primer iz kombinatori£ne optimizacije in bi ga lahko prevedli na problem maksimalnega pretoka. Preden podamo formalno denicijo problema maksimalnega pretoka, si oglejmo ²e en konkreten primer problema maksimalnega pretoka.

Iz Ljubljane ºelimo v Frankfurt prepeljati neko blago. Za prevoz izberemo hitri ºelezni²ki promet, ki vozi po Evropi. Na povezavah med ve£jimi mesti v Evropi imamo omejitve v velikosti vlakov, ki nam povedo koliko ton izdelkov lahko prepeljemo iz enega mesta v drugega. S pomo£jo algoritmov za re²evanje problema maksimalnega pretoka lahko iz- ra£unamo katere poti izbrati, da bomo iz Ljubljane v Frankfurt prepeljali najve£ blaga naenkrat. Na² problem prevedemo na ustrezno omreºje. Ljubljana je na²e za£etno vozli-

²£e, Frankfurt pa je kon£no vozli²£e. Na sliki 2.1 imamo Ljubljano in Frankfurt obrobljeno z rde£o barvo. Mesta, kjer ima vlak postanke, so pod£rtana z modro barvo in predsta- vljajo vozli²£a. Med mesti imamo povezave, ki so ozna£ene s temno sivo barvo. ’tevilke, zapisane ob povezavah, nam povedo koliko enot oz. koliko blaga lahko prepeljemo po

2.1. PROBLEM MAKSIMALNEGA PRETOKA

v Frankfurt prepeljali najve£ blaga. To bomo re²ili s pomo£jo katerega izmed algoritmov, ki jih bomo spoznali v nadaljevanju.

Slika 2.1: Primer transporta izdelkov iz Ljubljane v Frankfurt.

2.1 Problem maksimalnega pretoka

V tem razdelku bomo formalno vpeljali problem maksimalnega pretoka.

Naj bo R⁺ mnoºica nenegativnih realnih ²tevil. Urejeni £etverici (D, k, s, t), kjer je D digraf, s, t∈V(D) in velja s6=t, ter k:E(D)→R⁺, re£emo omreºje. Pri tem vozli²£e s imenujemo za£etno vozli²£e ali izvor, vozli²£e t imenujemo kon£no vozli²£e ali po- nor, vrednost k(e), kjer je e∈E(D), pa je kapaciteta povezavee.

Na²a glavna naloga pri problemu maksimalnega pretoka je, da od za£etnega vozli²£a s do kon£nega vozli²£a t prepeljemo najve£ enot (toka, tovora, izdelkov,. . .), pri £emer pa moramo upo²tevati omejitve, ki jih podaja kapaciteta. Potrebno je torej dolo£iti tako

imenovani pretok skozi vsako povezavo in to tako, da upo²tevamo dane kapacitete, pri tem pa ºelimo, da je skupen pretok od izvora s do ponorat maksimalen.

Pretok skozi omreºje(D, k, s, t)je vsaka funkcijaf :E(D)→R⁺, kjer za vsake∈E(D) velja 0 ≤ f(e) ≤ k(e). Naj bo v ∈ V(D). Potem je preseºek pretoka f v vozli²£u v deniran kot

pre_f(v) = X

e∈δ⁻(v)

f(e)− X

e∈δ⁺(v)

f(e),

kjer je δ⁻(v) mnoºica povezav, katerih kon£no vozli²£e je v, in δ⁺(v) mnoºica povezav, katerih za£etno vozli²£e je v. ƒe je pre_f(v) ≥ 0, to pomeni, da v vozli²£e v prite£e vsaj toliko enot, kot jih odte£e. Pri izvoru vedno odte£e vsaj toliko enot, kot jih prite£e, zato za izvor zahtevamo pre_f(s)≤0. ƒe je za neko vozli²£e pre_f(v) = 0, re£emo, da se pretok f v vozli²£u v ohranja, saj v vozli²£e prite£e ravno toliko enot, kot jih tudi odte£e. Pretok omreºja, za katerega velja, da je pre_f(v) = 0 za vse v ∈ V(D)\{s, t}, se imenuje s-t pretok. Vrednost s-t pretoka f je denirana kot pre_f(t) oziroma −pre_f(s) in nam pove, koliko enot prepeljemo od vozli²£as do vozli²£a t. Da sta ti dve deniciji vrednosti a−b pretoka res ekvivalentni, pove naslednja trditev.

Trditev 2. Naj bo(D, k, s, t)omreºje. Vrednosts-tpreseºka v za£etnem vozli²£u je tedaj nasprotna vrednosti preseºka v kon£nem vozli²£u.

Dokaz. Poglejmo si vsoto preseºkov po vseh vozli²£ih omreºja:

X

v∈V(D)

pre_f(v) = X

v∈V(D)

X

e∈δ⁻(v)

f(e)− X

e∈δ⁺(v)

f(e)

.

Vsaka povezavaev zgornji vsoti nastopa natanko dvakrat, enkrat kot povezava, ki vstopa v vozli²£e (torej tu dobimo f(e)) in drugi£ kot povezava, ki izstopa iz vozli²£a (tu torej dobimo −f(e)). Vsi £leni vsote se zato pokraj²ajo in tako je vsota enaka 0. Po drugi strani pa jef s-tpretok in so zato preseºki na vseh vozli²£ih, razen v za£etnem in kon£nem vozli²£u, enaki 0. Torej:

X

v∈V(D)

pre_f(v) =pre_f(s) +pre_f(t).

2.1. PROBLEM MAKSIMALNEGA PRETOKA

je D= (V, E), je sestavljen iz mnoºice vozli²£ V(D), povezav E(D)in ²e vseh nasprotnih povezav izE(D). Pri tem je nasprotna povezavaepovezaveeusmerjena v nasprotno smer kot e. To je, £e je e usmerjena od u do v, je nasprotna povezava usmerjena od v do u. V podvojenem digrafu sta tako lahko dve povezavi med istima paroma vozli²£ usmerjeni v isto smer. To se zgodi natanko takrat, ko imamo v D med tema dvema vozli²£ema povezavi v obe smeri.

Imejmo omreºje O = (D, k, s, t) in pretok f na njem in naj bo D podvojeni digraf di- grafa D. Glede na pretok f je tedaj pridruºena kapaciteta k_f(e) povezave e ∈ E(D) denirana takole:

- £e je e ∈E(D), je k_f(e) = k(e)−f(e), - £e je e =e⁰ za e⁰ ∈E(D), je k_f(e) =f(e⁰).

Iz denicije sledi, da za vsak e∈E(D) veljak_f(e) +k_f(e) =k(e)−f(e) +f(e) = k(e). Pridruºena kapaciteta torej za povezave iz mnoºice E(D)pove, koliko enot dodatno lahko

²e po²ljemo vzdolº te povezave, za nasprotne pa, za koliko lahko vzdolº originalne pove- zave pretok zmanj²amo.

Pridruºeni digraf D_f omreºja O glede na pretok f je digraf, v katerem je mnoºica vozli²£ V(D) in mnoºica povezav E(D_f) = {e ∈ E(D) : k_f(e) 6= 0}. Vsako s-t pot v pridruºenem digrafu D_f imenujemof-pove£ujo£a pot. Pri iskanju optimalnih pretokov so pove£ujo£e s-tpoti zelo pomembne. ƒef−pove£ujo£as-tpot obstaja, potem se pretok f lahko pove£a vzdolº te poti. Vrednost f lahko pove£amo najve£ za minimalno vrednost pridruºenih kapacitet na povezavah te f−pove£ujo£es-tpoti. Na vseh povezavah izbrane f−pove£ujo£e s-t poti pove£amo pretok za minimalno vrednost pridruºenih kapacitet.

Ideja Ford - Fulkersonovega algoritma, ki ga bomo predstavili v nadaljevanju, je ta, da na vsakem koraku poi²£emo kak²no f−pove£ujo£o pot, £e le ta obstaja. Potem vzdolº te poti pove£amo pretok f.

Primer omreºja, pretoka na njem in pripadajo£ega pridruºenega digrafa, je prikazan na sliki 2.2. Pri prvem digrafu na levi strani si lahko ogledamo digraf s podanimi kapacite- tami. Vsaka povezava tega digrafa ima podano kapaciteto, to je ²tevilka, ki je zapisana ob tej povezavi. Na drugi sliki je za to omreºje podan nek s-t pretok, pri £emer je na

posamezni povezavi podana vrednost pretoka in kapaciteta. Poglejmo si, kaj pomenijo

²tevilke ob povezavah. Izberimo poljubno povezavo, naj bo to povezava (b, e). Pod njo je zapisana ²tevilka 6/8, kjer ²tevilka 8 predstavlja kapaciteto te povezave, ²tevilka 6 pa pretok, ki gre skozi to povezavo. Na tretji sliki imamo prikazan pridruºeni digraf glede na s-t pretok iz srednje slike. Vsaka povezava ima podano pridruºeno kapaciteto.

Slika 2.2: Na prvi sliki vidimo primer digrafa s kapacitetami, na drugi sliki primer digrafa s pretokom in kapacitetami, ter na tretji sliki pridruºen digraf s pridruºenimi kapacitetami.

Kot ºe re£eno, bomo v omreºjih iskali maksimalen pretok. Zanima nas, kdaj sploh obstaja.

S pomo£jo rezultata o linearnih programih bomo v izreku 3 pokazali, da maksimalni pretok vedno obstaja.

Izrek 3. Imejmo omreºje O = (D, k, s, t). Za to omreºje obstajas-t pretok maksimalne vrednosti.

Dokaz. Najprej je potrebno pokazati, da problem lahko prevedemo na linearen program.

O²tevil£imo povezave omreºja z e₁, e₂, . . . , e_m. Ugotoviti moramo, kak²ne pretoke f_i je potrebno spustiti skozi povezave e_i, da bomo dobili maksimalen s-t pretok. Upo²tevati moramo pogoje 0≤f_i ≤k(e_i), kjer jef_i vrednosts-t pretokaf skozi povezavo e_i ink(e_i) kapaciteta povezavee_i,za vsaki∈ {1,2, . . . , m}. Da bo za vsako vozli²£ev ∈V(D)\{s, t}

veljala ohranitev pretoka, mora veljati ²e pogoj X

ei∈δ⁻(v)

fi− X

ei∈δ⁺(v)

fi = 0.

2.1. PROBLEM MAKSIMALNEGA PRETOKA

Ker so tako pogoji, kot cenovna funkcija, katere maksimum i²£emo, linearni, je to linearen program. Dopustna mnoºica je neprazna, saj je pretok f = 0 (torej f_i = 0 za vsak i) v dopustni mnoºici. Cena je navzgor omejena z vsoto

X

ei∈δ⁺(s)

k(e_i),

kar je najve£ji moºen pretok iz za£etnega vozli²£a s. Po izreku 1, v razdelku o linear- nem programiranju, obstaja vsaj ena optimalna re²itev. V tem primeru je to potem kar maksimalen s-t pretok.

Sedaj, ko vemo, da maksimalens-tpretok vedno obstaja, nas zanima, kako ugotoviti, kdaj je s-t pretok maksimalen. Uporaben, potreben in zadosten pogoj bomo dokazali v izreku 5, najprej pa dokaºimo lemo 4, s katero si bomo pomagali pri dokazu izreka.

Lema 4. Naj boO = (D, k, s, t)omreºje. Naj boX ⊆V(D)mnoºica, za katero velja, da je s∈X int 6∈X. Naj bo δ⁺(X) :={(u, v)∈E(D)|u∈X, v /∈X}inδ⁻(X) :={(u, v)∈ E(D)|u /∈X, v ∈X}. Potem za vsak s-t pretok f velja:

1. vr(f) = P

e∈δ⁺(X)f(e)−P

e∈δ⁻(X)f(e), 2. vr(f)≤P

e∈δ⁺(X)k(e).

Dokaz. 1. Vemo, da je pref(v) = 0 za vsak v ∈ V(D)\{s, t}, da t 6∈ X in vr(f) =

−pre_f(s). Torej je vr(f) = X

e∈δ⁺(s)

f(e)− X

e∈δ⁻(s)

f(e)⁽¹⁾= X

v∈X

X

e∈δ⁺(v)

f(e)− X

e∈δ⁻(v)

f(e) (2)

=

(2)= X

e∈δ⁺(X)

f(e)− X

e∈δ⁻(X)

f(e).

Enakost(1)velja, ker vsoti na levi strani dodamo vsote po vozli²£ih izX\{s}, v katerih pa ima f ni£elni preseºek. Povezave, ki imajo obe kraji²£i v X, nastopajo tako v δ⁺(v), kot tudi v δ⁻(v⁰), za ustrezne v, v⁰ ∈X. Tako se vrednost pretoka na teh povezavah od²teje, ostanejo pa nam povezave, ki imajo eno kraji²£e vX, drugo pa zunaj njega. Sledi enakost (2).

2. Enakost

vr(f) = X

e∈δ⁺(X)

f(e)− X

e∈δ⁻(X)

f(e)

smo dokazali ºe v to£ki (1). Po deniciji velja, da je X

e∈δ⁺(X)

f(e)≤ X

e∈δ⁺(X)

k(e) in

X

e∈δ⁻(X)

f(e)≥0.

Iz tega sledi, da je

vr(f)≤ X

e∈δ⁺(X)

k(e).

S tem smo dokaz kon£ali.

Izrek 5. Na omreºju (D, k, s, t)je s-t pretok f maksimalen natanko tedaj, ko ne obstaja nobena f−pove£ujo£as-t pot.

Dokaz. (⇒)

Naj bo pretok f maksimalen. ƒe bi obstajala f−pove£ujo£a pot, bi ga lahko glede na razmislek, ki smo ga navedli ob denicijif-pove£ujo£ih poti, pove£ali. To je v protislovju s predpostavko, da je pretok f maksimalen.

(⇐)

Recimo, da ne obstaja nobena s-t pove£ujo£a pot. To pomeni, da v pridruºenem digrafu Df iz za£etnega vozli²£asni mogo£e priti v kon£no vozli²£et. Naj boX mnoºica, v kateri je vozli²£e s in vsa vozli²£a, ki jih lahko v D_f doseºemo iz s z usmerjenimi potmi. Tedaj torej t /∈ X. Po deniciji digrafa D_f je f(e) = k(e) za vse e ∈ δ⁺(X) in f(e) = 0 za vse e∈δ⁻(X). Ker X ustreza mnoºici iz leme 4, velja:

vr(f) = X

e∈δ⁺(X)

k(e),

kar pa po 2. to£ki iz leme 4 pomeni, da je f maksimalen s-t pretok.

2.2. MAKSIMALNI PRETOK - MINIMALNI REZ

2.2 Maksimalni pretok - minimalni rez

Imejmo omreºje (D, k, s, t). Naj za X ⊆ V(D) velja s ∈ X, t 6∈ X. ƒe v digrafu D odstranimo vse povezave iz

δ⁺(X) :={(u, v)∈E(D)|u∈X, v /∈X}, s-t pot ne obstaja ve£. Mnoºici δ⁺(X)re£emo s-t rez, vsoti

X

e∈δ⁺(X)

k(e)

pa kapaciteta s-t reza δ⁺(X).

Problem minimalnega reza je poiskati s-t rez z minimalno kapaciteto. Po deniciji s-t reza mnoºica X ni nujno povezana (obstajajo pari vozli²£, med katerimi ni nobene poti). To pomeni, da je lahko sestavljena iz ve£ih povezanih komponent. Izkaºe pa se, da je minimalni rez vedno povezana komponenta digrafa D. Denimo nasprotno, da torej ob- staja nepovezana mnoºica X, da jeδ⁺(X)minimalni rez. Ker vsaka s-tpot potuje preko kak²ne povezave iz δ⁺(X)in kerX ni povezana mnoºica, mora vsaka s-t pot potovati po vsaj eni povezavi iz δ⁺(Y), kjer je Y povezana komponenta X, ki vsebuje s. Torej je ºe δ⁺(Y) nek s-t rez. Kapaciteta s-t reza δ⁺(Y) je manj²a od kapacitete reza δ⁺(X), saj nismo upo²tevali povezav na drugih povezanih komponentah X. Dobili smo kapaciteto s-t reza, ki je manj²a od minimalnega reza. Protislovje.

Na sliki 2.3 si poglejmo razli£ne s-t reze za nek konkreten primer in poi²£imo s-t rez z minimalno kapaciteto. Pri vseh primerih je mnoºica X ozna£ena s sivo barvo. Poglejmo si nekaj primerov mnoºic X. Prvi na sliki je digraf D. Pri drugi sliki naj bo X = {s, a, b, c, d, e}, V(D)\X = {t}. ƒe odstranimo vse povezave iz δ⁺(X) (ki so v na²em primeru ozna£ene z rde£o barvo), res dobimo digraf v katerem ni ve£ nobene s-t poti.

Izra£unajmo vsoto kapacitet za ta primer:

X

e∈δ⁺(X)

k(e) = 1 + 9 = 10.

Podobno naredimo pri nekaterih ostalih moºnostih, kjer bomo zapisali mnoºici vozli²£ X inV(D)\X, ter izra£unali kapaciteto pripradajo£egas-treza. Vse povezave, ki jih odstra- nimo, so ozna£ene z rde£o barvo. Na tretjem primeru je X = {s, a, b, c, e}, V(D)\X =

Slika 2.3: Primeri s-t rezov.

{d, t}. Kapaciteta pripadajo£ega s-t reza je X

e∈δ⁺(X)

k(e) = 2 + 9 = 11.

Kapaciteta s-t reza pri £etrtem primeru je prav tako X

e∈δ⁺(X)

k(e) = 2 + 1 + 8 = 11,

kjer je X = {s, a, b, c}, V(D)\X = {d, e, t}. Na petem primeru imamo X = {s, b}, V(D)\X ={a, c, d, e, t}, kapaciteta pripradajo£ega s-t reza pa je

X

e∈δ⁺(X)

k(e) = 4 + 8 = 12.

2.2. MAKSIMALNI PRETOK - MINIMALNI REZ

Za nekaj primerov smo izra£unali kapacitete s-t rezov. Ni teºko videti, da je minimalna kapaciteta v tem primeru 9, kjer je X = {s} in V(D)\X = {a, b, c, d, e, t}. Za izra£un minimalnega s-t reza si lahko pomagamo z nekaterimi algoritmi. Eden izmed njih je al- goritem Gomory-Hu. Ve£ o njem si lahko preberete v knjigi [4], na strani 183.

Da je algoritem, ki poi²£e minimalni s-t rez, koristen tudi za re²evanje problema ma- ksimalnega pretoka, pokaºe naslednji izrek.

Izrek 6 (Maksimalni pretok - minimalni rez). Za vsako omreºje (D, k, s, t), kjer je s, t∈ V(D) in k : E(D) → R⁺, je vrednost maksimalnega s-t pretoka enaka kapaciteti mini- malnega s-t reza.

Dokaz. Ker po 2. to£ki leme 4 velja, da je vrednost poljubnega s-t pretoka navzgor omejena s kapaciteto poljubnegas-t reza, je za dokaz izreka, da je vrednost maksimalnega pretoka enaka kapaciteti minimalnega reza, dovolj pokazati, da so za poljuben s-t pretok f ekvivalentne naslednje trditve.

(1) f je maksimalen s-t pretok.

(2) Ne obstaja nobena f−pove£ujo£as-t pot.

(3) Obstaja s-t rez s kapaciteto, ki je enaka vrednosti f.

(1) →(2)

Da je f maksimalen pretok natanko tedaj, ko ne obstaja nobena f−pove£ujo£a s-t pot, smo pokazali ºe v izreku 5.

(2) →(3)

Dokazati moramo, da £e ni nobene f−pove£ujo£e s-t poti, potem mora obstajati s-t rez, katerega kapaciteta je enaka vrednosti f. Naj bo f s-t pretok, za katerega ne obstaja nobena pove£ujo£a s-t pot. Naj bo X mnoºica vozli²£, ki so v pridruºenem digrafu Df

dosegljiva iz za£etnega vozli²£a s. Ker ne obstaja f−pove£ujo£a s-t pot, velja t 6∈ X. Za vse povezave e, ki se za£nejo v mnoºici X in kon£ajo izven mnoºice X, velja, da je f(e) =k(e). Prav tako za vse povezavee, ki vstopajo v mnoºicoX vemo, da jef(e) = 0. Po lemi 4 sledi

vr(f) = X

e∈δ⁺(X)

f(e)− X

e∈δ⁻(X)

f(e) = X

e∈δ⁺(X)

k(e)− X

e∈δ⁻(X)

0 = X

e∈δ⁺(X)

k(e).

Torej je vrednost f enaka kapaciteti s-t reza δ⁺(X). (3) →(1)

Denimo, da obstaja s-t rez δ⁺(X), kjer je s∈X int 6∈X, s kapacitetovr(f), to je X

e∈δ⁺(X)

k(e) = vr(f).

Po lemi 4 za poljuben s-t pretok f˜velja vr( ˜f)≤ X

e∈δ⁺(X)

k(e) = vr(f), torej je f res maksimalen s-t pretok.

2.2. MAKSIMALNI PRETOK - MINIMALNI REZ

Algoritmi

V tem poglavju si bomo podrobneje pogledali nekatere algoritme, ki jih uporabljamo za re²evanje problema maksimalnega pretoka. Kot re£eno obstaja za ta namen veliko algo- ritmov, mi pa bomo spoznali le nekatere. To so Ford - Fulkersenov algoritem, Edmonds - Karpov algoritem in Goldberg - Tarjanov algoritem. Spoznali bomo same algoritme, dolo£ili njihove £asovne zahtevnosti ter si s pomo£jo primerov pogledali njihovo delovanje.

Ford - Fulkersonov algoritem deluje tako, da v pridruºenem digrafu glede na trenutni pretok poi²£e poljubno pot od za£etnega vozli²£a do kon£nega vozli²£a. Izra£una, kak²no je najve£je moºno pove£anje pretoka vzolº te poti (kar je seveda kar minimum pripadajo-

£ih pridruºenih kapacitet). Nato ustrezno pove£a vrednost pretoka vzdolº te poti in poi²£e novo pot od za£etnega do kon£nega vozli²£a v novem pridruºenem digrafu. To ponavlja toliko £asa, dokler v pridruºenem digrafu obstaja pot od za£etnega do kon£nega vozli²£a.

Ko ni ve£ nobene poti, po kateri bi lahko pove£ali pretok, se algoritem zaklju£i in vrne vrednost maksimalnega pretoka. Edmonds - Karpov algoritem je v resnici le izbolj²ava Ford - Fulkersonovega algoritma, saj se od njega razlikuje le v tem, da pri iskanju pove-

£ujo£e poti vedno poi²£emo najkraj²o pot od za£etnega do kon£nega vozli²£a. Kot bomo videli, ima ta majhna sprememba zelo velik pomen za hitrost delovanja algoritma.

Goldberg - Tarjanov algoritem deluje precej druga£e, saj tokrat operiramo s tako ime-

3.1. FORD - FULKERSONOV ALGORITEM

3.1 Ford - Fulkersonov algoritem

Ford - Fulkersonov algoritem za iskanje maksimalnega pretoka na omreºju sta leta 1956 v £lanku predstavila matematika L. R. F ord J r. in D. R. F ulkerson.

To naj bi bil prvi algoritem za iskanje maksimalnega pretoka na omreºju. Algoritem deluje tako, da za£nemo z ni£elnim s-t pretokom, to je, da najprej dolo£imo f(e) = 0 za vse e ∈ E(D). To pomeni, da na za£etku na nobeni povezavi ²e nimamo pretoka.

Nato poi²£emo kak²no f−pove£ujo£o potP od za£etnega vozli²£as do kon£nega vozli²£a t. Ko najdemo poljubno tako pot, izra£unamo γ, ki je minimalna vrednost pridruºenih kapacitet na povezavah pove£ujo£e poti P. Nato pove£amo f vzdolº poti P za vrednost γ in se vrnemo na korak, kjer ponovno i²£emo f−pove£ujo£o pot. Algoritem se izvaja toliko £asa, dokler obstaja f−pove£ujo£a pot od vozli²£as do vozli²£a t. Ko ne najdemo ve£ nobene f−pove£ujo£e poti, se algoritem kon£a in nam vrne f.

Algoritem:

Vhodni podatek: Omreºje (D, k, s, t).

Izhodni podatek: s-t pretok f z maksimalno vrednostjo.

Potek algoritma:

1. f(e) = 0 za vse e∈E(D).

2. Poi²£i f-pove£ujo£o pot P v pridruºenem digrafu D_f. ƒe ta ne obstaja, kon£aj algoritem in vrni f.

3. Izra£unajγ := min_e∈E(P) k_f(e). Pove£ajf po potiP zaγ in se vrni na 2. korak.

Pojasnimo ²e enkrat kako pretok f pove£amo vzdolº izbrane poti za vrednost γ. Na vseh povezavah f−pove£ujo£e poti P spremenimo pretok f za vrednost γ in sicer tako, da za povezave iz P, ki so tudi v E(D), vrednost pretoka na njih pove£amo, za povezave iz P, ki so obrati povezav iz E(D), pa vrednost pretoka zmanj²amo.

V prakti£nih primerih se obi£ajno sre£ujemo s celo²tevilskimi kapacitetami, ali pa lahko problem prevedemo v tak²no obliko. Tudi mi se za trenutek omejimo le na take primere.

Zanima nas, £e za omreºja s celo²tevilskimi kapacitetami lahko sklepamo, kak²en je ma- ksimalen pretok. Iz Ford - Fulkersonovega algoritma dokaºimo zanimivo in pomembno lastnost maksimalnega pretoka na omreºju s celo²tevilskimi kapacitetami.

Posledica 7. V primeru, ko so vse kapacitete v omreºju cela ²tevila, obstaja tudi celo-

²tevilski maksimalen pretok, to je pretok, ki ima na vseh povezavah omreºja celo²tevilske vrednosti. Ford - Fulkersonov algoritem se zagotovo ustavi.

Dokaz. Preden se prvi£ izvede drugi korak algoritma, je pripadajo£i s-t pretok zagotovo celo²tevilski. V drugem koraku Ford - Fulkersonovega algoritma izberemo f−pove£ujo£o pot. Pridruºena kapaciteta na poljubni povezavi je seveda celo²tevilska (in strogo pozi- tivna), saj so vse kapacitete celo²tevilske. Torej je γ iz tretjega koraka algoritma neko naravno ²tevilo. Pretok f je torej vseskozi celo²tevilski, pa tudi nove pridruºene kapaci- tete so tak²ne. Dokaºimo, da se algoritem ustavi po kon£no mnogo korakih. Premislimo, najve£ koliko korakov algoritma lahko naredimo. Zgornja meja za ²tevilo korakov je po zgornjem maksimalna moºna vrednost s-t pretoka, ki je po lemi 4 omejena z

X

e∈δ⁺(s)

k(e),

saj v vsakem koraku vrednost pretoka pove£amo vsaj za 1. Ker je pretok f vseskozi celo²tevilski, je maksimalni pretok, ki ga dobimo v zadnjem koraku, tudi celo²tevilski. S tem smo dokaz kon£ali.

Poiskati neko pove£ujo£o pot je zelo enostavno, saj moramo samo najti pot od za£etnega do kon£nega vozli²£a, kar lahko na primer doseºemo ºe s tako imenovanim iskanjem v

²irino. Pri tem pa je ²tevilo korakov, ki jih algoritem potrebuje, da doseºe maksimalen pretok, na£eloma precej odvisen od izbire konkretnih pove£ujo£ih poti. Lahko se nam namre£ zgodi, da si z izbiro napa£nih poti £asovno zahtevnost mo£no poslab²amo.

Teºave pri izbiri poti

3.1. FORD - FULKERSONOV ALGORITEM

Slika 3.1: Primer preprostega grafa.

preprost primer prepri£a, da je tudi tu izbira pove£ujo£ih poti zelo pomembna. Na sliki 3.1 vidimo preprost digraf s ²tirimi vozli²£i, petimi povezavami in ozna£enimi kapacitetami, kjer je n ∈ N neko ksno izbrano ²tevilo. Za£etno vozli²£e je ozna£eno z s in kon£no s t. O£itno je, da je vrednost maksimalnega pretoka na tem omreºju 2n. Poglejmo si ko- liko korakov potrebujemo za izra£un vrednosti maksimalnega pretoka, £e pove£ujo£e poti ne izbiramo optimalno. Pri izbiranju pove£ujo£e poti imamo ve£ moºnosti. Odlo£imo se, da vedno izberemo pot, ki vsebuje povezavo med vozli²£em a in vozli²£em b (ali pa njen obrat). Za£nimo z ni£elnim s-t pretokom, to je, najprej dolo£imo f(e) = 0 za vse e ∈ E(D). Kapaciteta na povezavah (s, a) in (s, b) je n, na povezavi (a, b) pa 1. Pretok vzdolº f−pove£ujo£e potis−a−b−t nato pove£amo za minimum pridruºenih kapacitet, torej za γ = min{n,1}= 1. Na sliki 3.2 pri levem digrafu je prikazans-t pretok po prvem

s t

1/n

1/1 n

n 1/n

aa

b

s t

n-1

1 n

n n-1

aa

b

1 1

Slika 3.2: Prvo pove£anje pretoka vzdolº poti s−a−b−t.

pove£anju, na desni sliki pa je prikazan pridruºeni digraf, kjer lahko vidimo, da smo sedaj dobili obratno povezavo (b, a). Ponovno i²£emo f−pove£ujo£o pot. Na voljo imamo ve£

moºnosti. Ker ºelimo uporabiti povezavo med vozli²£em a in vozli²£em b, izberemo pot s−b−a−t, vzdolº katere lahkof zopet pove£amo zaγ = min{1, n}= 1. Pove£anje vidimo na sliki 3.3 na levi strani, na desni pa je prikazan ustrezni pridruºeni digraf. Pove£anja

s t

1/n

0/1 1/n

1/n 1/n

aa

b

s t

n-1

1

n-1

aa

b

1

1 1

1 n-1

n-1

Slika 3.3: Drugo pove£anje toka vzdolº poti s−b−a−t.

vzdolº poti s−a−b−t ins−b−a−t ponavljamo toliko £asa in v enakem vrstnem redu, dokler ne obstaja ve£ nobenaf−pove£ujo£a pot. Sledi, da moramo vzdolº potis−a−b−t narediti npove£anj in vzdolº potis−b−a−t prav takon pove£anj. Z2n koraki pridemo do maksimalnegas-t pretoka, katerega vrednost je2n. ƒe bi pri izbiri pove£ujo£es-tpoti upo²tevali, da vedno izberemo najkraj²os-t poti, bi do re²itve pri²li le v dveh korakih. To izbolj²avo upo²teva Edmonds - Karpov algoritem, ki zahteva, da moramo vedno izbrati najkraj²of−pove£ujo£os-t pot. Ve£ o tem algoritmu sledi v nadaljevanju (razdelek3.2).

ƒe bi upo²tevali ta pogoj, bi izbrali najkraj²o pot, to jes−a−t alis−b−t. Recimo, da najprej izberemo pot s−a−t in pretok pove£amo za γ = min{n, n} = n. Ostane nam

²e f−pove£ujo£a pot s−b−t, kjer prav tako pretok pove£amo za n. Ker nimamo ve£

nobene f−pove£ujo£e poti, kon£amo algoritem. Na² maksimalen s-t pretok ima vrednost 2n (slika 3.4). Iz tega preprostega primera lahko vidimo, da se da maksimalen pretok na

3.1. FORD - FULKERSONOV ALGORITEM

s t

n/n

0/1 n/n

n/n n/n

aa

b

s

t

aa

b

n n

n n

Slika 3.4: Maksimalen s-t pretok in pripadajo£i pridruºeni digraf.

Primer digrafa, kjer so kapacitete iracionalne vrednosti

Pravkar smo se prepri£ali, da se lahko ²tevilo korakov Ford - Fulkersonovega algoritma precej spremeni, £e spremenimo na£in izbire pove£ujo£ih poti. ƒe pa dovolimo, da so kapacitete lahko iracionalnih vrednosti, se nam lahko celo zgodi, da se Ford - Fulkersonov algoritem nikoli ne kon£a. Poglejmo si enega izmed enostavnje²ih primerov, ki ga je leta 1993 v £lanku predstavilU ri Zwick( [10]). Primer si bomo pogledali na omreºju s ²estimi vozli²£i in devetimi povezavami. Zwick v tem £lanku dokaºe tudi, da obstaja ²e manj²e omreºje pri katerem se Ford Fulkersonov algoritem nikoli ne kon£a. To je omreºje s 6 vozli²£i in 8 povezavami ter ima prav tako nekatere iracionalne kapacitete. Ve£ o tem si lahko preberete v £lanku [10]. Poglejmo si sedaj omenjen primer (slika 3.5). Vse povezave,

4 ss

t s

a p₁ b p₃ c p₂ d

4 ss

t s

a 1 b 1 c w d

4 4

4

4

4 4

Slika 3.5: Na levi je primer digrafa z ozna£enimi tremi povezavami, na desni pa digraf s kapacitetami.

katerih za£etno vozli²£e je sin vse povezave, katerih kon£no vozli²£e jet imajo kapaciteto 4. Imamo ²e povezavo p₁ = (b, a) s kapaciteto 1, povezavo p₃ = (b, c) s kapaciteto 1 ter povezavo p₂ = (d, c) s kapaciteto w =

√5−1

2 ≈ 0,618034. Opazimo, da velja w² = 1−w.

Ves £as izvajanja algoritma bomo ²e posebej pozorni na te tri povezave. Na nadaljnih slikah imamo nato na levem digrafu z modro barvo ozna£enof−pove£ujo£o pot, na desnem pa pridruºeni digraf po ustreznem pove£anju. Za£nimo z izvajanjem algoritma. Najprej nastavimo pretokf vseh povezav na 0. Izberimof−pove£ujo£o pots−b−c−tin pretokf pove£ajmo zaγ =min{4,1}= 1. Na povezavi p3 se je spremenila pridruºena kapaciteta, ki je sedaj 0, ostali dve sta ostali nespremenjeni, kar vidimo na sliki 3.6, na drugem digrafu.

Vrednosts-t pretokaf je sedaj 1. Sedaj lahko pretok pove£amo po potis−d−c−b−a−t za minimum kapacitetγ =min{4, w,1}=w(slika 3.7). Dobimos-tpretokf z vrednostjo 1 +w. Poglejmo si pridruºene kapacitete na povezavah med vozli²£ia , b , c ind. Povezava

4 ss

t s

a p1 b p3 c p2

d

4 ss

t s

a 1 b 1 c w d

4 ss

t s

a 1 b c w d

4 4

4

4

4 4

4 4

4 4 3

3 1

1

1 0/4

0/4

0/4 0/4

0/4 0/4

0/1 0/1 0/w

4 ss

t s

a p1 b p3 c p2

d 0/4

0/4

0/4 0/4

0/4 0/4

0/1 0/1 0/w

Slika 3.6: Prvo pove£anje.

p₁ ima pridruºeno kapaciteto1−w=w², na povezavip₂ je pridruºena kapaciteta 0 in na povezavi p₃ je le-ta w.Sedaj lahko pove£amo pretok vzdolº poti s−b−c−d−t in sicer zaγ =min{3, w,4}=w.Dobimo s-tpretok vrednosti1 + 2w.Sedaj je mogo£es-t pretok pove£ati vzdolº s−d−c−b−a−t in sicer zaγ =min{4−w, w,1, w²}=w². Pove£amo

3.1. FORD - FULKERSONOV ALGORITEM

w −w² = w· (1− w) = w ·w² = w³, povezava p₃ pa ima pridruºeno kapaciteto w². Poglejmo si moºnosti pove£anja pretoka. Vidimo, da pretok lahko pove£amo vzdolº poti

4 ss

t s

a p1 b p3 c p2

d 0/4

0/4

1/4 0/4

1/4 0/4

0/1 1/1 0/w

4 ss

t s

a w² b c w d

4-w 4

4 4-w 3

3 1

1 w

w w w

w²

4 ss

t s

a p1 b p3 c p2

d 0/4

w/4

1/4 w/4

1/4 0/4

w/1 w²/1 w/w

ss

t s

a w² b c w d

4-w

4-w 4 4-w

3-w

3 1+w

1 w

w w

1

w

4 ss

t s

a p1 b p3 c p2

d 0/4

w/4

1+w/4 w/4

1/4 w/4

w/1 1/1 0/w

ss

t s

a 1 b c w³ d

3 4-w

3 4

3-w

3 1+w

w² 1

1

1 w

w

w²

Slika 3.7: Naslednja tri pove£anja

s−a−b−c−t, vrednost pove£anja pretoka vzdolº te poti je γ =min{4,1, w²,3}=w². Dobimo s-t pretok vrednosti 1 + 2w+ 2w² = 3.Po pove£anju je pridruºena kapaciteta na povezavi p1 enaka w²,na povezavip2 ostane w³ in na povezavip3 je 0.Zopet se da pretok pove£ati, na primer vzdolº poti s−d−c−b−a−t za γ =w³, kar vidimo na sliki 3.8.

Vrednost s-t pretoka f je sedaj 1 + 2w+ 2w²+w³ = 2 + 2w.

Poglejmo si ²e nekaj korakov pove£anja pretoka v digrafu na slikah 3.8 in 3.9, da bomo laºje obrazloºili delovanje algoritma pri tem primeru. V tabeli 3.1imamo zapisane korake

4 ss

t s

a p1 b p₃ c p2

d 0/4

1/4

1+w/4 1/4

1/4 w/4

1/1 w/1 w²/w

ss

t s

a w² b c w³ d

3

4-w 3 3+w

3-w

2+w 1+w

2-w 1

1 w

1

w² 1-w

w

4 ss

t s

a p1 b p3 c p2

d w²/4

1/4

1+w/4 1/4

2-w/4 w/4

w/1 1/1 w²/w

ss

t s

a w⁴b c d

4-2w

4-w 4-2w 3+w

3-w

2+w 1+w

w³ 2-w

2w

2w w

1-w³

w 1-w

w+w³

4 ss

t s

a p1 b p3 c p2

d w²/4

2w/4

1+w/4 2w/4

2-w/4 w/4

w+w³/1 1-w³/1 w/w

ss

t s

a w⁴b c

d

4-2w 5-3w

4-2w 3+w

4-3w

2+w 3w

2-w 2w

2w 3w-1

1

w² 1-w

w+w³

w³

4 ss

t s

a p1 b p3 c p2

d w²/4

2w/4

3w/4 2w/4

3w-1/4 2-w/4

w+w³/1 1/1 w²/w

ss

t s

a b c d

2+2w 5-3w

2+w 3+w

4-3w

2+w 3w

2-w 2-w

2-2w

3w-1 1-w⁴

w²+w⁴ 1-w

1

w⁵ w⁴

Slika 3.8: ’e nekaj korakov pove£anja. Na levih digrah je pove£ujo£a s-t pot, na desni pa so pridruºeni digra.

3.1. FORD - FULKERSONOV ALGORITEM

4 ss

t s

a p₁ b p₃ c p₂ d

w²/4

2-w/4

3w/4 2-w/4

3w-1/4 2-w/4

1/1 1-w⁴ w²+w⁴

ss

t s

a b c d

2+2w 5-3w

2+w 1+4w

4-3w

4w 3w

4-4w 2-w

2-2w

3w-1 1

w²+w⁴ 3-4w

1-w⁴

/1 /w w⁴ w⁵

4 ss

t s

a p₁ b p₃ c p₂ d

3-4w/4

2-w/4

3w/4 2-w/4

3w-1/4 4-4w/4

1/1 w²+w⁴

ss

t s

a b c d

5-4w 5-3w

5-4w 1+4w

4-3w

4w 3w

4-4w -1+4w

-1+4w

3w-1 1-w⁵

w 3-4w

2-2w

/w w⁶

1-w⁴/1

w⁵

4 ss

t s

a p₁ b p₃ c p₂ d

3-4w/4

-1+4w/4

3w/4

-1+4w/4

3w-1/4 4-4w/4

1-w⁵/1 w/w

ss

t s

a b c d

5-4w 8-8w

5-4w 1+4w

7-8w

4w -3+8w

4-4w -1+4w

-1+4w

-4+8w 1

w-w⁵ 3-4w

2-2w

1-w³/1 w⁶ w⁵

4 ss

t s

a p₁ b p₃ c p₂ d

3-4w/4

-1+4w/4

8w-3/4

-1+4w/4

8w-4/4 4-4w/4

1/1 w-w⁵/w

ss

t s

a b c d

4w 8-8w

4w 1+4w

7-8w

4w -3+8w

4-4w 4-4w

4-4w

-4+8w 1-w⁶

w-w⁷ 3-4w

1

2-2w/1 w⁷

w⁶

Slika 3.9: ’e nekaj korakov pove£anja. Na levih digrah je pove£ujo£a s-t pot, na desni pa so pridruºeni digra.

korak pot p₁ p₂ p₃ γ vrednost s-t pretoka

0 1 w 1

1 s-b-c-t 1 w 0 1 1

2 s-d-c-b-a-t w² 0 w w 1 +w

3 s-b-c-d-t w² w 0 w 1 + 2w

4 s-d-c-b-a-t 0 w³ w² w² 1 + 2w+w² = 2 +w 5 s-a-b-c-t w² w³ 0 w² 1 + 2w+ 2w² = 3

6 s-d-c-b-a-t w⁴ 0 w³ w³ 1 + 2w+ 2w²+w³ = 2 + 2w 7 s-b-c-d-t w⁴ w³ 0 w³ 1 + 2w+ 2w²+ 2w³ = 1 + 4w 8 s-d-c-b-a-t 0 w⁵ w⁴ w⁴ 1 + 2w+ 2w²+ 2w³+w⁴ = 3 +w 9 s-a-b-c-t w⁴ w⁵ 0 w⁴ 1 + 2w+ 2w²+ 2w³+ 2w⁴ = 5−2w 10 s-d-c-b-a-t w⁶ 0 w⁵ w⁵ 1 + 2w+. . .+ 2w⁴+w⁵ = 2 + 3w 11 s-b-c-d-t w⁶ w⁵ 0 w⁵ 1 + 2w+. . .+ 2w⁴+ 2w⁵ =−1 + 8w 12 s-d-c-b-a-t 0 w⁷ w⁶ w⁶ 1 + 2w+. . .+ 2w⁵+w⁶ = 4

... ... ... ... ... ... ...

Tabela 3.1: Prikaz korakov, poti ter vrednost s-t pretoka v vsakem koraku.

in f−pove£ujo£e poti, vrednosti pridruºenih kapacitet na povezavah p1, p2, p3, vrednosti pove£anja pretoka (γ) ter vrednostis-tpretoka po vsakem koraku. Na slikah lahko vidimo, da pretok pove£ujemo po to£no dolo£enem zaporedju poti. Sedaj bomo pretok pove£ali po poti s−b−c−d−t, nato zopet po poti s−d−c−b−a−t, sledi s−a−b−c−t iz zopet pove£anje po poti s−d−c−b−a−t. Vrednost pove£anja pretoka po vsakem koraku se spreminja po enakem sistemu, s tem pa tudi vrednost s-t pretoka.

ƒe primerjamo zgornja pove£anja lahko vidimo, da je v prvem, petem, devetem,... koraku zmogljivost povezav podobna. Vedno je v obliki p₁ = wⁿ, p₂ = wⁿ⁺¹ in p₃ = 0, kjer je n ∈ N. To pomeni, da bi lahko poti v tem vrstnem redu izbirali neskon£no mnogokrat.

Vrednost pripadajo£ih s-t pretokov se ves £as strogo pove£uje in konvergira k vrednosti f = 1 +w+w+ (1−w) + (1−w) +. . .=

3.1. FORD - FULKERSONOV ALGORITEM

= 1 + 2

1−w = 1 + 2 1−

√ 5+1

2

=

= 1 + 2

3−√ 5 2

= 1 + 4 3−√

5 =

= 7−√ 5 3−√

5 = (7−√

5)·(3 +√ 5) (3−√

5)·(3 +√ 5) =

= 21 + 7√

5−3√ 5−5

4 = 16 + 4√

5

4 =

= 4 +√ 5<7.

Ker se pri tak²ni izbiri pove£ujo£ih poti torej algoritem nikoli ne kon£a, ima potemtakem neskon£no £asovno zahtevnost. Poleg tega tudi limitna vrednost 4 + √

5 ni enaka dejanski vrednosti maksimalnega pretoka, ki je 2·4 + 1 = 9, v kar se zlahka lahko prepri-

£amo s pomo£jo izreka 6. Lahko bi rekli, da je za ta primer algoritem neuporaben.

Tudi pri tem primeru z iracionalnimi kapacitetami, bi lahko upo²tevali, da vedno iz- beremo najkraj²o pot, kar zahteva Edmonds - Karpov algoritem. Do maksimalnega s-t pretoka bi tako pri²li ºe po treh korakih. Poglejmo si vse skupaj na spodnji sliki 3.10. Na levem digrafu imamo z modro ozna£eni najkraj²i pove£ujo£i s-t poti, ki sta s−a−t in s−d−t. Na desnem digrafu je prikazan pridruºeni digraf. Izberemo na primer s−a−t in pretok pove£amo za γ = min{4} = 4. Enako storimo ²e za pot s−d−t, kjer je vre- dnost f−pove£ujo£e poti prav tako 4. Dobimo s-t pretok vrednosti 4 + 4 = 8. Poi²£emo

4 ss

t s

a p1 b p3 c p2

d

4 ss

t s

a 1 b 1 c w d

4 4

4

4

4 4

0/4

0/4

0/4 0/4

0/4 0/4

0/1 0/1 0/w

Slika 3.10: Na levem digrafu sta ozna£eni pove£ujo£i poti, na desni pa je pridruºeni digraf

naslednjo najkraj²o f−pove£ujo£o pot, to je s−b−c−t, ki je prikazana na sliki 3.11 na levem digrafu. Pove£amo pretok za γ =min{4,1}= 1. Sedaj je vrednosts-t pretoka enaka 9. Zopet i²£emo pot od za£etnega vozli²£a s do kon£nega vozli²£a t. Ker ni ve£

nobene f−pove£ujo£es-t poti, kon£amo algoritem in dobimo vrednost maksimalnegas-t pretoka, ki je 9. Na sliki 3.11 na desnem digrafu imamo prikazan pridruºen digraf po koncu izvajanja algoritma.

4 ss

t s

a p1 b p₃ c p2

d

4 ss

t s

a 1 b 1 c w d

4 4

3

4 3 4

4/4

4/4

0/4 4/4

0/4 4/4

0/1 0/1 0/w

1

1

Slika 3.11: Na levem digrafu je ozna£ena tretja f−pove£ujo£a pot, na desni pa je pridru- ºeni digraf ob koncu izvajanja algoritma.

Primer z iracionalnimi kapacitetami nam pove, da se v splo²nem Ford - Fulkersonov algo- ritem nikoli ne ustavi. ƒe pa se omejimo le na celo²tevilske vrednosti kapacitet (posledica 7), je £asovna zahtevnost O(m·ϑ), kjer je m²tevilo povezav in ϑ vrednost maksimalnega pretoka (ki pa je seveda na£eloma odvisna od kapacitet povezav). Pri drugi to£ki algo- ritma i²£emo f−pove£ujo£o pot na m povezavah. V tretji to£ki ra£unamo γ, s katerim pove£amo vrednost pretoka f. ’tevilo pove£anj je lahko najve£ ϑ. Tako je £asovna zah- tevnost O(m·ϑ).