Srautai tinkluose


Informatikos konspektas. Pagrindinės sąvokos. Maksimalaus srauto konstravimo algoritmas. Pagalbinio tinklo Sf apskaičiavimo algoritmas. Maksimalaus srauto apskaičiavimo algoritmas. Tarkime, kad turime tinklą automobilinių kelių, kuriais galima nuvykti iš punkto A į punktą B. Keliai gali kirstis tarpiniuose punktuose. Kiekvienai kelio atkarpai yra žinomas maksimalus skaičius automobilių, kuriuos ši kelio atkarpa gali praleisti per laiko vienetą (kelio pralaidumas). Koks didžiausias skaičius automobilių per laiko vienetą gali nuvažiuoti iš punkto A į punktą B? Šis automobilių skaičius vadinamas nagrinėjamo kelio tinklo automobilių srauto dydžiu. Paparastai mus domina ne vien tik koks didžiausias automobilių skaičius gali nuvykti iš A į B, bet ir kiekvieno kelio ruožo srautas, t.y. koks skaičius automobilių vyksta šiuo kelio ruožu. Aišku, kad galimas ir kitas klausimas: kiek ir kokių kelių pralaidumus reikia padidinti, kad maksimalus automobilių srautas per šį kelių tinklą padidėtų nurodytu dydžiu? Maksimalaus srauto konstravimo algoritmas.


kiekvienam grafo G lankui galioja nelygybė

Įrodymas. Tarkime, kad – minimalus pjūvis. Remiantis lema, bet kokiam srautui f gausime:

Remdamiesi tinklu Gf, sudarome pagalbinį tinklą, kuris neturi kontūrų (ciklų) ir kurio struktūra vaizduoja visas trumpiausias didinančiasias tinklo Gf grandines. Pažymėkime šį tinklą simboliu Sf. Tinklas Sf konstruojamas paieškos platyn grafe Gf metodu, ir į tinklą Sf įtraukiami tinklo Gf srauto f atžvilgiu leistinieji lankai. Tuo būdu į tinklą Sf įeina šaltinis s, nuotakis t ir grafo Gf leistinieji lankai , čia viršūnė u nutolusi nuo šaltinio s atstumu d, o viršūnė v – atstumu d+1, , o l yra tinklo Sf ilgis, t.y. atstumas nuo s iki t grafe Gf. Šio lanko pralaidumą žymėsime ir apibrėšime formule

Maksimalaus srauto konstravimas baigiamas, kai iš tinklo Gf nebegalima sukonstruoti pagalbinio tinklo Sf.

Tinklo Sf pseudomaksimalaus srauto apskaičiavimo procedūra maxpsa

for v ( SV do Q [v] := 0; { Krovinių inicializacija tinklo Sf viršūnėse }

XN := SV;{ Aibėje XN bus saugomas tinklo Sf nenulinio potencialo viršūnės }

while XN ( ( do { Pagrindinis ciklas }

Srautai tinkluose. (2010 m. Gegužės 28 d.). http://www.mokslobaze.lt/srautai-tinkluose.html Peržiūrėta 2016 m. Gruodžio 05 d. 16:37