Kombinatorikos teorija egzaminui

1.ĮVADAS Daugelis valdymo uždavinių (bei kitų inžinerinių uždavinių) gali būti modeliuojami taikant tinklinius modelius. Ir ieškant optimalaus šio tinklinio modelio sprendinio mums tenka spręsti kombinatorikos uždavinius. Kombinatorinė optimizacija nuo įprastinių optimizacijos metodų pagrinde skiriasi tuo, kad optimizacinėje kombinatorikoje pagrindiniai kintamieji kinta ne tolygiai, bet diskretiškai. Iš pirmo požiūrio atrodytų, kad tuo būdu yra sumažinama galimų sprendinių aibė, tačiau šios uždavinių grupės algoritmai yra daug sudėtingesni, kadangi šiems uždaviniams netinka įprastinės optimizacijos matematinės prielaidos. Bendru atveju bet kurį kombinatorinį uždavinį galima išspręsti perrinkus visas galimas kombinacijas. Pvz.: priskyrimo uždavinys: turime n asmenų ir n užduočių. Atskiros užduoties atlikimo kaina yra susieta su konkrečiu asmeniu ir konkrečia užduotimi. Reikia kiekvienam asmeniui priskirti vieną užduotį, kad bendroji kaina būtų minimali. 1)Sudarome visas galimas užduočių paskirstymo kombinacijas 2)Apskaičiuojame kiekvienos kombinacijos bendrą kainą 3)Išrenkame pačią pigiausią. Bendras kombinacijų sk. – n!, jei turim n=70, tai galimų kombinacijų skaičius 70!=2332. Realiai šio uždavinio išspręsti negalime. Šis algoritmas yra teisingas, bet nepraktiškas. Mes skirsime dėmesį efektyvių algoritmų analizei. 2.GRAFAI. BENDROS ŽINIOS APIE GRAFUS Tinkliniai uždaviniai modeliuojami taikant grafų teorijos elementus. 2.1.BENDRIEJI ELEMENTAI BEI TEIGINIAI Bendru atveju grafas žymimas G=(N,A), N – grafo mazgų aibė, A – grafo briaunų aibė. Grafų būna kryptinių ir nekryptinių. Kryptiniai – kai briauna turi kryptį: N={1,2,3,4,5,6,7} A={(1,2),(1,3),(2,3),(2,4),(3,6),(4,5),(4,7),(5,2),(5,3),(6,7)} Nekryptiniame grafe ta pati briauna užrašoma 2 kartus (Pvz.: (1,3) ir (3,1)). Kai turim kryptinę briauną 12, tai taškas 1 vadinamas uodega (tail), taškas 2 – galva (head). Briauna (1,2) yra incidentiška 1 ir 2 mazgams. Mazgo laipsnis – įeinantis ir išeinantis. Įeinantis – įeinančių į mazgą briaunų sk-ius. Išeinantis – išeinančių iš mazgo briaunų sk-ius. Mazgo laipsnis – abiejų laipsnių suma. Nekryptiniame grafe turime tik mazgo laipsnį. Jei mazgo laipsnis lygus 0, tai mazgas yra izoliuotas. Dalinis grafas – G’=(N’,A’) – šis grafas yra dalinis grafo G=(N,A) atžvilgiu, jei N’N, A’A. Ėjimo grafas – tai yra kryptinis grafas Gl=(Nl,Al), kuris yra tuo pat metu dalinis pradinio grafo atžvilgiu. (1)į 2 2)niekur 5)į 2 ir 7 7)niekur) Kelio grafas – tai ėjimo grafas, kuriame nė vienas mazgas nesikartoja 2 kartus. Kryptinis kelias – tai kelias be grįžtamųjų briaunų. Ciklas – kelias, kurio pirmutinis ir paskutinis mazgas yra tas pats. Mazgų susietumas – sakome, kad mazgas i ir j yra susieti, jei  bent vienas kelias nuo i-tojo į j-ąjį mazgą. Ir tyrinėjamas grafas vadinamas susietuoju, jei jo na mazgų pora yra susietoji. Priešingu atveju grafas yra nesusietasis. Grafo medis – tai dalinis grafas, kuriame visi tyrinėjamo grafo mazgai yra sujungti tarpusavyje vieninteliu keliu, t.y. dalinis grafas, kuris neturi nei vieno ciklo. Grafo karkasas – tai yra medis, kuriame yra n–1 briauna, jei N=n. T.y. mazgas jungiamas su kitu mazgu tik viena briauna (izoliuotų mazgų negali būti). Dvidalis grafas (beprtile) – jame visus mazgus galime sudalyti į 2 aibes, t.y. visos galimos grafo briaunos prasideda 1-oje mazgų aibėje ir baigiasi kitoje. G=(N,A) 1)iN1, jN2 2) jN1, iN2 2.2.GRAFŲ DUOMENŲ STRUKTŪROS Bendru atveju: (lij , uij) – papildomi parametrai Pvz: Grafų saugojimo būdai: 1)Mazgų briaunų incidentinė matrica G=(N,A), kur N=n ir A=m, n – mazgų, m – briaunų. Matricos dydis nm (Šone surašomi mazgai, o viršuje visos briaunos. Susikirtime rašomas –1 kai įeina ir 1 kai išeina, o visur kitur 0). Ši matrica turi specialią struktūrą, jos elementai yra tik –1, 0, 1. Efektyvumas: nenulinių elementų turime 2m. Tai nėra efektyvus būdas. Trūkumai:*)labai brangu apdoroti informaciją *)sunku sudaryti efektyvius algoritmus. Privalumai: tokia matrica atitinka apribojimo matricą sprendžiant minimalios kainos srauto uždaviniį. 2)Mazgų kaimynystės matrica. G=(N,A), kur dydis nn (šone ir viršuje surašomi mazgų numeriai, pirmam stulpelyje mazgai iš kurių išeina, 1 rašomas, kai tarp dviejų mazgų yra briauna). Ši matrica turi n2 elementų, iš kurių tik m yra nenuliniai. Saugojimo erdvė išnaudojama efektyviai tik tankių grafų atveju (kai turim daug briaunų palyginant su mazgais). Retų tinklų atv erdvė išnaudojama neefektyviai. Privalumai: *)saugojimo paprastumas leidžia nesunkiai taikyti daugelį tinklinių algoritmų. *)lengva organizuoti informacijos paiešką. Papildoma briaunų informacija saugojama analogiškoje matricoje: pirmieji parametrai bus vienoje matricoje, antrieji – kitoj, ir jie bus toj vietoj, kur yra 1. 3)Briaunų kaimynystės sąrašas. Sąrašai sudaromi tiesinių sąrašų principu. Tiesinis sąrašas turi tokią struktūrą. [1][2, 25 ir 30][3, 35 ir 50, 0] [2][4, 15 ir 40, 0] [3][2, 45 ir 10, 0] [4][3, 15 ir 30][5, 45 ir 60, 0] [5][3, 25 ir 20][4, 35 ir 50, 0] Privalumai: *)efektyviai išnaudojama saugojimo erdvė *)greita info paieška *)leidžia efektyviai taikyti kombinatorikos algoritmus. 4)Tolstančios ir grįžtamosios žvaigždės būdai (Foward and reverse star) 2 informacijos grupės: indeksų masyvas ir informacinis masyvas. Indeksų masyvas turi vienu elementu daugiau nei mazgų sk-ius. Foward star metodas: 1 [1] 1 [1, 2, 25 ir 30] 2 [3] 2 [1, 3, 35 ir 50] 3 [4] 3 [2, 4, 15 ir 40] 4 [5] 4 [3, 2, 45 ir 10] 5 [7] 5 [4, 3, 15 ir 30] 6 [9] 6 [4, 5, 45 ir 60] 7 [5, 3, 25 ir 20]  8 [5, 4, 35 ir 50] nurodoma info, k-me įraše prasideda info iš atitinkamo mazgo Privalumai: *)efektyviai išnaudojama saugojimo erdvė, *) lengva info paieška bei panaudojimas, *) vienodai tinka tiek retiems, tiek tankiems tinklams. Pastaba: šis principas labiau tinka apdoroti išeinančių iš mazgo briaunų informacijai. Grįžtančios žvaigždės principas skirtas aprašyti į mazgą įeinančių mazgų informacijai. Jis yra analogiškas išnagrinėtam. Palyginimas (3) ir (4) būdo: *)tolstančios žvaigždės sugojimo būdas (4) yra efektyviausias erdvės atžvilgiu. Šį metodą lengviausia realizuoti procedūrinėmis kalbomis, tokiomis kaip Fortran. *)briaunų kaimynystės sąrašą (3) lengviau programuoti Paskalio ar C kalbomis, nes jomis nesunkiai galime programuoti susietųjų sąrašų manipuliacijas. *) (3) yra susietas per i stulpelį *)naudojant (3) nesunku pridėti ar pašalinti briauną, o taip pat ir mazgą, tuo tarpu taikant (4) būdą šios operacijos reikalauja laiko proporcingo briaunų skaičiui,(3) būdui šios operacijos užima fiksuotą pastovų laiką. 2.3.NEKRYPTINIŲ GRAFŲ SAUGOJIMO YPATUMAI Aprašant nekryptinius grafus, taikomi tie patys metodai kaip ir kryptinių grafų atveju. Tiktai šiuo atveju no tinklo briauną (i,j) mes turime aprašyti 2 kartus: (i,j) ir (j,i). Formuojant (1) ir (2) būdu, bendroji saugojimo vieta lieka ta pati. Saugant (2) būdu, mūsų pagrindinė matrica virsta simetrine, todėl galime saugoti tik jos viršutinį trikampį. Taikant (3) ir (4) būdais, saugojimo vieta dvigubėja. Jei norim modifikuoti informaciją (pvz.: išmesti briauną (1,2)), tai turim ją modifikuoti 2 vietose (t.y. išmesti ir (2,1) briauną). Aprašant nekryptinius grafus atkrinta grįžtančios žvaigždės metodas. 3. TINKLINIŲ UŽDAVINIŲ TIPAI 1.Minimalios kainos srauto uždaviniai(minimum cost problem) Šia klase galime aprašyti šiuos praktinius uždavinius: 1) produkcijos paskirstymas iš gamyklų į bazes ir iš bazių į parduotuves; 2) turime miesto gatvių tinklą ir planuojame automobilių eismą; 3) medžiaginių resursų analizė konveerinėje technologijoje gamyklose; 4) skambučių srauto valdymas telekomunikacijų tinkluose. Šiems uždaviniams mes turime turėti kryptinį tinklą G=(N,A). Su na briauna a(i,j)A mes turime vienintelio srauto kainą cij, srauto žemutinę ribą lij ir viršutinę ribą uij. Su nu mazgu iN mes turime b(i) konstantą, aprašančią šio mazgo tiekimo ar pareikalavimo galimybes. Kas tiekiama priklausys nuo konkretaus uždavinio. b(i)>0 - mazgas tiekiantysis b(i)O(1) – įterpti Popall(s)->O(|s|) – pašalinti Sudėtingumo analizė:Kadangi turime n operacijų, įterpimo sudėtingumas bus O(n), o pašalinimo – O(n2). Tačiau O(n2) žymiai viršija realius skaičiavimo poreikius, nes pašalinimas iš steko vyksta vienu metu, t.y. mes pilnai išvalome steką. Ir mes negalime daugiau pašalinti elementų nei jų įterpiame. Per kiekv. push op. mes galime įterpti daugiausia n elementų => kad atsitiktine push ir popall operacijų seka turi sudėtingumą ne didesnį kaip O(n). Šitą sudėtingumo analizę galime lengvai atlikti taikant potencinių f-jų metodą. Potencinę f-ją sudarome tokiu būdu: (k)=|s|. Pradiniu atv. (0)=0. Pašalinimo operacija sumažina op. sk. mažiausiai vienetu iki 0. Realiai proporcinga Push (k)=1; Popall (k)=k. Daugiausia f-jos reikšmė gali būti n. 4.3 Parametrų balansavimo metodas. Jo taikymas algoritmų sudėtingumo analizei Taikomas, kai alg. sudėtingumo f-ja O išreikšta keliomis neprikl. f-jomis nuo iteracijų skaičiaus:O(f(m,n,k)+(n,m,k)) Šiuo atv. taikomas param. balans. metodas. Reikia surasti optimalią k reikšmę. Randame I f-jos išvestinę ir prilyginam 0. Skaičiuojam k reikšmę. Trūkumas: dažnai gauname tokiu atv. neišreikštines f-jas, kurių tikslaus sprendinio negalime rasti analitiniais metodais. Be to I išvestinės prilyginimo atvejį galime taikyti, kai abi f-jos monotoniškai didėjančios arba mažėjančios. Tuo atveju, kai 1 f-ja monot. >, o kita mon. d(i) + Cij then d(i) = d(i) + cij pred(j) = I end; end; Praktiškai šio alg. Teisingumas įrodomas remiantis teorinėmis prielaidomis, pateiktomis ankstesniame poskyryje. 7.6 Algoritmo sudėtingumas Dikstros alg. Galime išskirti 2 pagr. operacijas: 1)mazgų išrinkimas. Operacija kartojama N kartų ir kiekv. kartą mazgų mažėja. 2)atstumo modifikavimas. Tai kiekv. mazgui atliekame |A(i)| kartų. |A(i)| = m -> O(m) Galutinis alg. Sudėtingumas O(m^2). Pastabos. O(m^2) praktiškai būna labai tankiems tinklams, t.y. kai m = (m2) (brianų sk. = mazgų sk.2) Kitiems tinkl;ams šis efektyvumas g.b. ir pagerintas. Tam tikslui naudojamos duom. struktūros, susietos su užd. formulavimu. 7.7. Atbulinis Disktros algoritmas Pradinėje Disktros algoritmo versijoje apskaičiavome trumpiausią kelią nuo pradinio taško iki bet kurio kito tinklo taško. Tačiau sprendžiant praktinius uždavinius, kartais kyla poreikis apskaičiuoti trumpiausią kelią nuo bet kurio tinklo mazgo iki apibrėžto poreikių mazgo (galutinio). Tai praktiškai analogiškas uždavinys ir taikomas tas pats Disktros algoritmas, tik su nedidele modifikacija. Ta modifikacija vadinama atviruoju Disktros algoritmu. Tada pradinis taškas tampa atbuliniu. Formuojame atstumų žymes nuo galutinio taško: d’(j). j(t). Turime S’ ir S’-. Analogiškai viskas bus atvirkščiai. 7.8 Dvikryptis DikStros algoritmas. Dažnai turime tikslų pradinį bei galutinį mazgus. Šio tipo uždavinių sprendimui vienu metu taikome tiesioginį ir atvirkštinį Disktros algoritmą. T.y. iš mazgo S taikome tiesioginį, o iš T – atvirkščiai. Operacijas atliekame tol, kol tiesioginis ir atvirkštinis algoritmai pastoviai pažymi tą patį mazgą [SS+ = {k}] Tada kelias randamas P(k)P’(k). Pastaba: Šis algoritmas yra efektyvus, kad vienoje iteracijoje pažymime du mazgus ir tuo pačiu sumažinamas tyrinėjamų briaunų skaičius, kurios yra susietos. Kuprinės uždavinys. Gali būti suformuluotas kaip ilgiausio kelio uždavinys. Turime daiktų rinkinį ir kiekvienas daiktas turi savo svorį ir kainą. Mes taip pat turime didžiausią leistiną kuprinės svorį. Mūsų tikslas – rasti, prikrauti mūsų kuprinę tokiais daiktais, kurių bendra kaina būtų max, bet neviršytų leistino kuprinės svorio. maxin vixi, in wixiw. xi –pasirinktas daiktas. n=3, w{2,1,3}, v{30,10,20}, w = 4. Šito tinklinio modelio mazgai aprašys 2 poromis: i – mūsų turinėjamas daiktas. w – likęs svoris, kurį dar galima įdėti. Pilnai suformuoti tinklą, įvedame objektus n+1, w.Kaip randamos tinklo briaunos? Sakykime turime i,w  i+1,w. Ši briauna išreiškia veiksmą, kad nededame į kuprinę. i,w  i+1, w-w1 – dedame į kuprinę.n+1,w  n+1,w-1. Paskutinio tipo briauna gali būti įvesta tik paskutiniame etape tam , kad būtų suformuotas kryptinis kelias iki galutinio mazgo. 8. Trumpiausi keliai: žymių korekcijos algoritmai Žymių korekcijos algoritmai leidžia tyrinėti tinklų trumpiausius kelius, kaip jie nėra specialios struktūros. PASTABA: Šie algoritmai nėra tokie efektyvūs ir so nuo konkrečios problemos sprendimo, nes bendru atveju šio tipo uždaviniai so NP uždavinių klasei. 8.1 Žymių korekcijos alg-mų kūrimo teorinės prielaidos. Bendru atv visi šios klasės alg-mai turi sekančią loginę schemą: atskirame alg-mo veikimo etape atstumo žymė d(j) yra kuriama kio tinklo mazgui, jN. Tarpiniuose skaičiavimo etapuose čis įvertinimas d(j) yra tik viršūtinė ieškomo trumpiausio kelio riba. Ir tik po paskutinio etapo žymė s(j) yra trumpiausio kelio ilgis. d(j)d(i)+Cij ,(i,j)A - optimalumo sąlyga Kryptinis kelias P: S=i1-i2-i3-...-ik=j Galima rekurentiškai išreikšti visus d(j): d(j) = d(ik)d(ik-1)+Cik-1ik ... d(i2)  d(i1)+Ci1i2 | || 0 visas nelygybes sudėjus, gaunamas įvertinimas d(j)=d(ik) tai apatinė rio kryptinio kelio riba iki j mazgo, ir tuo pačiu yra viršutinė trumpiausio kelio iki j riba. Visi žymių korekcijos alg-mai paremti redukuotais briaunų ilgiais Cij: Cdij = Cij+d(i)-d(j) Šie redukuoti briaunų ilgiai turi sekančias savybes: 1) riame kryptiniame tinklo cikle: -ciklo briaunų aibė 2) riam kryptiniam keliui P iš k į l mazgą, turime 3) mazgų žymės d atitinka trumpiausio kelio ilgio žymes, tai redukuotų briaunų kainos yra neneigiamos: Cij0 (i,j)A 8.2 Apibendrintas žymių korekcijos alg-mas d(i)=0, pred(S)=0 -pagalbinis mazgas d(j)= jN-{S} while (i,j) tenkina d(j)>d(i)+Cij do d(j)=d(i)+Cij; pred(j)=i; end; end Čia nėra nusakyta, briaunų išrinkimo tvarka; t.y šį alg-mą turim atlikti, kai briaunų sąrašas, tenkinančių sąlygas, tampa lygus 0. Praktiškai me alg-mo etape bendru atv reikia išnagrinėti visas tinklo briaunas. Šio alg-mo sudėtingumas bendru atv apskaičiuojamas: • iš visų Cij išrenkamas |max| ir pažymimas C; -Cd(j)nC • trumpiausiame kelyje gali b. (n-1) briaunų • d(j) kitimo riba 2nC • blogiausiu atv d(j) reikšmė sumažėja 1 (vienetu) reikšme oje iteracijoje, tai reikės 2nC(n-1) iteracijų ir sudėtingumas O(n2C) nam mazgui šalia d turime informaciją pred, tai bendru atv iš šio mazgo galima atstatyti einamojo trumpiausio kelio viršutinės ribos grafą: kol yra medis, nėra ciklo; kai atsiranda ciklai: PVZ: (6,2), kur d(2)>d(6)+C62 Cd62>0 Tada šią briauną reikia įtraukti į kelią ir pred(2)=6, o briauną (1,2) išmesti iš kelio. Tokia situacija yra neigiamo ciklo situacija; tuo būdu aptinkame, kad tinklas neigiamą ciklą. Jeigu tinklas neturi neigiamo ciklo, tai šis grafas, sudarytas iš pred masyvo el-tų, turės medžio pavidalą. Jeigu yra neigiamas ciklas, kelio rasti trumpiausio nebegalima. 8.3 Modifikuotas žymių korekcijos alg-mas Iš esmės tai tas pat apibendrintas žymių korekcijos alg-mas, tik jame įvestos briaunų sąrašo, tyrinėjamo je iteracijoje, formavimo taisyklės: d(S)=0 pred(S)=0 d(j)= jN-{S} list={S} while list0 do begin pašalinti i iš list for (i,j)A(i) iš i-tojo prasideda if d(j)>d(i)+Cij Cdij1* 2) Binarinio tyrimo: Atspindi bendrą binarinio tyrimo ideologiją. [ ,] iš jo užsiduodame Jei gauname neigiamą ciklą, tai 0>* ir intervalą keičiame [  , 0 ]. (priešingu atveju) Jei randamas nulinis ciklas, tai intervalas bus [0 , ]. Taip intervalas mažinamas, kol intervalas nebus mažesnis už , kur 0 yra max{ij: (i,j)A}. 9. Visų trumpiausių kelių uždavinių grupė (all pairs shortest path) Šiame skyriuje bus aptariami uždaviniai, k-se tyrinėjamos trumpiausių kelių nuo rio tinklo mazgo radimo problemos. 9.1 Teorinės alg-mo kūrimo prielaidos Jei rią mazgų porą tinkle pažymėsim [i,j], tai trumpiausias atstumas tarp šių mazgų bus d[i,j] ir turint tokį aprašymą galima formuluoti visų porų trumpiausių kelių optimalumo sąlygą (trikampio taisyklę). nai porai [i,j]NN, tegu d[i,j] yra kažkurio kryptinio kelio iš i-tojo į j mazgą ilgis k – tarpinis mazgas Yra sąlyga: d[i,j]d[i,k]+d[k,j] riam i,j,k mazgams. PASTABA: ši optimizavimo sąlyga veikia tik tada, kai visos turi teigiamus ilgius 9.2 Floyd-Worshall alg-mas visų porų trumpiausiems keliams rasti Šis alg-mas paremtas sekančia teorema: d[i,j]=min{[i,j], d[i,k]+d[k,j]}, atlikus šias operacijas riai d[i,j] mazgų porai, esant visoms galimoms k reikšmėms (kN), narys d[i,j] tampa lygus trumpiausiam keliui tarp i ir j mazgų, jei visi atstumai yra neneigiami (Cij>0). Begin for all ij dij= dij=Cij for i=1, n, do dii= for k=1, n? do for i=1, nik do for j=1, njk do dij=min{dij, dik+dkj} end Paskutiniame alg-mo realizavime naudojame 2 matricas: [D], kurioje bus trumpiausi kelių ilgiai ir [H] – pateikiam info apie trumpiausia kelio sandarą tarp i,j mazgų. PVZ: 10. Maksimalūs srautai 10.1 Uždavinio formulavimas Turime kryptinį tinklą G=(N, A) ir na briauna (i,j)A yra susieta su pralaidumu uij. Išskiriami 2 mazgai: s – šaltinio ir t – poreikių. Ieškome maksimalaus srauto dydžio iš šaltinio į poreikių mazgą. max V (srautas). Ribojimai: Kur suma lygi 0, tai tie mazgai yra persiuntimo mazgai. Čia xij – srautas ai duotajai briaunai (ieškomas kintamasis). V – visų išeinančių iš s šaltinio briaunų srautų suma arba visų briaunų, įeinančių į t mazgą, srautų suma. Prielaidos: 1. tinklas yra kryptinis; 2. visi pralaidumai yra neneigiami skaičiai; 3. tinklas neturi kryptinio kelio iš s į t, sudaryti tiktai iš briaunų, kurių pralaidumas = ; 4. tinklas neturi lygiagrečių briaunų (kurios turi tą patį pradžios ir pabaigos tašką). PVZ.: bet kuris tinklinis uždavinys su pralaidumo fizinėmis galimybėmis, pralaidumo funkcija. 10.2 Teorinės prielaidos Šios uždavinių klasės algoritmai paremti liekamojo tinklo koncepcija. liekamojo grafo briaunos: Liekamojo grafo pralaidumas rij = uij - xij, toms briaunoms, kurių kryptis sutampa su pagrindinio tinklo briaunų kryptimis. Galima kontroliuoti srautą ir kita kryptimi rji = xij. Duotam grafui liekamasis tinklas yra: (iš 4 į 2 atbulinės nebus nes srauto nėra) Atbulinės liekamojo grafo briaunos leidžia sumažinti srautą duotąja briauna. Kol srautas tinkle lygus 0, liekamasis grafas sutampa su pradiniu. Vieni algoritmai tejungia liekamąjį tinklą, o ne tiesioginį grafą. s-t pjūvis Bet kuri pjūvis sudalina grafo mazgus į 2 aibes S ir . Šis pjūvis bus s-t, kai sS ir t. Bet kuri briauna pjūvyje vadinama tiesiogine, jei (i,j) iS, o j. Jei iS, o j, tai turėsim atbulinę briauną. Pjūvio pralaidumas u bus pjūvio tiesioginių briaunų pralaidumo suma: Šis pralaidumas yra viršutinė maksimalaus srauto suma. Analogiškai tam pačiam pjūviui liekamajame grafe galima apskaičiuoti s-t pjūvio liekamuosius pralaidumus: (=3 iš PVZ) Liekamasis pralaidumas tik tiesioginių briaunų. Srautas per pjūvį s-t bus visų briaunų, esančių tame pjūvyje, srautų suma. (V – srauto prieaugis, pereinant nuo grafo prie liekamojo). Ši paskutinė lygtis ir yra pagrindinė algoritmo konstravimo lygtis.Bet kurį kryptinį kelią iš šaltinio į poreikių mazgą liekamajame grafe vadiname prieaugių keliu. Startuojam nuo nulinio srauto ir pirmajame etape liekamasis grafas sutaps su tiesioginiu (pradiniu). Pasirenkam kryptinį kelią 1-2-3-4 (prieaugių kelias). Šiam prieaugių keliui: (P – l iekamasis grafas) Srautas keliu 1-2-3-4 bus 2. V=2, V=2. Arba iteracija: sudaromas liekamasis grafas Pasirenkamas kitas kelias 1-3-2-4 (nebūtiniai optimaliausias) (2 (seno)+1(naujo)) 3 iteracija: kryptinis kelias 1-3-4 4 iteracija: daugiau kryptinio kelio iš s į t nebėra, ir tai reiškia kad šis srautas maksimalus. (galima šakoje 2-3 didinti pralaidumą, bet srautas nuo to nedidelis, todėl tą šaką galima imti prastesnės kokybės; atbulinė briauna parodo koks teka srautas). Jei diagonalusis elementas . Turim ciklą; (\). P(1,6)=5 H(1,6)=4 P(1,4)+P(4,6) (kelias skaidomas į 2 dalis) H(1,4)=2 H(4,8)=3 P(1,2)+P(2,4)+P(4,3)+P(3,6) H(1,2)=0 H(2,4)=0 H(4,3)=0 H(3,6)=0 (toliau skaidyti nebereikia) P(1,2)+P(2,4)+P(4,3)+P(3,6) Šį algoritmą galima naudoti ir neigiamiems ciklams rasti (jei diagonalės elementai

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!