IV003 Algorithms and Data Structures II

Toky

Algoritmom pre hľadanie maximálneho toku v grafe sú venované dve prednášky a cvičenia.

V texte sa odkazujem na slajdy z prednášky, s. 491-633. Plný text k slajdom nájdete v učebnici KT Kleinberg, Tardos: Algorithm Design. Popis algoritmov nájdete aj v učebnici CLRS Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms. Odkaz na demonštráciu výpočtu algoritmov nájdete na visualgo.net, využiť môžete aj demo k slajdom a vizualizáciu Push Relabel metódy.

História problému a motivácie k jeho skúmaniu sú vo videu

Formulácia problému maximálneho toku je na slajdoch 491-503. Duálnym problémom k maximálnemu toku je problém minimálneho rezu. Algoritmy v skutočnosti riešia obidva problémy. Vzťah medzi nimi je kľúčový pre dôkaz korektnosti.

Pre riešenie problému sa používajú dve základné metódy: metóda Forda a Fulkersona a metóda Push Relabel (aka Goldbergova a Tarjanova metóda). Spresnením metód dostávame celý rad rôznych algoritmov, postupne sa zoznámime s tými najzákladnejšími.

Metóda Forda a Fulkersona

Hladová, iteratívna metóda. Výpočet začína s nulovým tokom. V každej iterácii sa hľadá taká cesta zo zdroja do stoku, ktorá umožní zvýšiť hodnotu toku. Ilustrácia postupu je na slajdoch 506-513. Slajd 513 je dôležitý pre pochopenie metódy. Na slajde vidíte príklad siete, kde použitie hladového prístupu neviedlo k nájdeniu toku s maximálnou hodnotou. Metóda Forda a Fulkersona preto využíva "opravný mechanizmus", tj. možnosť znížiť tok na hrane. K tomu sa využíva reziduálna sieť (s. 514), ktorá je jednoznačne priradená k dvojici (sieť, tok), a ktorá obsahuje informácie o všetkých možnostiach ako upraviť tok na hrane.

DIY Ako je v reziduálnej sieti vyjadrená možnosť znížiť tok na hrane? Aké hrany medzi vcholmi x, y sú v reziduálnej sieti ak tok na hrane (x,y) je nulový resp. rovný kapacite hrany (x,y)?

Reziduálna sieť nám umožňuje pracovať so všetkými zmenami, tj. zvýšením aj znížením toku na hrane, jednotným spôsobom. Konkrétne, v reziduálnej sieti sa hľadá zlepšujúca cesta, jej definíciu nájdete na slajde 515.

DIY Čo je reziduálna kapacita zlepšujúcej cesty?

DIY Ako sa pomocou zlepšujúcej cesty vypočíta nový tok v sieti? O koľko sa zvýši jeho hodnota?

Výslednú metódu nájdete na slajde 517. Hovorí sa o nej ako o Fordovom a Fulkersonovom algoritme alebo metóde. Dávam prednosť označeniu metóda, ktoré lepšie vystihuje fakt, že FF neurčuje mechanizmus hľadania zlejpšujúcich ciest. Jednotlivé algoritmy odvodené z FF metódy sa líšia práve spôsobom výberu zlepšujúcich ciest.

Korektnosť a zložitosť

Parciálnu korektnosť (ak sa výpočet zastaví, výsledkom je maximálny tok) dokazujeme pomocou Vety o maximálnom toku a minimálnom reze, viz slajdy 527-527. Konvergencia (výpočet sa zastaví) závisí od toho, aké sú kapacity hrán v sieti.

Kapacity sú prirodzené čísla: v priebehu celého výpočtu je tok celočíselný a v každej iterácii sa zvýši jeho hodnota aspoň o 1 ==> výpočet skončí. Tzv. integrality invariant a theorem sú formulované na slajde 540. Budeme ich často využívať!
Kapacity sú racionálne čísla: kapacity prenásobíme vhodnou konštantou a prevedieme na prípad prirodzených čísel.
Kapacity sú iracionálne čísla: výpočet môže cykliť pretože hodnota toku sa v každej iterácii bude zvyšovať o stále menšiu hodnotu. Príklad siete a nekonečného výpočtu nájdete v učebnici J. Ericksona na strane 335 alebo na wikipedii

Zložitosť výpočtu pre siete s celočíselnými kapacitami je určená zložitosťou nájdenia zlepšujúcej cesty a počtom iterácií, ktorý je v najhoršom prípade rovný hodnote maximálneho toku.

Základné heuristiky, ktoré sa používajú pre výber zlepšujúcej cesty v reziduálnej sieti sú:

cesta s maximálnou reziduálnou kapacitou
cesta s dostatočne veľkou reziduálnou kapacitou
cesta s minimálnym počtom hrán

Škálujúci algoritmus (Capacity-Scaling alorithm),

Myšlienka: ak zo siete odstránim hrany z nízkou kapacitou, tak reziduálna kapacita zlepšujúcej cesty (ak existuje) je vysoká. Viz slajdy 545-549.

Najkratšia zlepšujúca cesta

Pre nájdenie najkratšej cesty zo zdroja do stoku v reziduálnej sieti použijeme algoritmus BFS, ktorý má lineárnu zložitosť. Počet iterácii sa neprekročí m.n (súčin počtu hrán a vrcholov siete), viz slajdy 552-559.

Nad rámec prednášky nájdete na slajdoch Dinitzov algoritmus. Prehľad existujúcich algoritmov nájdete na slajdoch 578-579.

Metóda Push Relabel (Goldbergova)

Audiokomentár

Demo

Varianty problému maximálneho toku

Pri riešení problémov často narazíme na situáciu, keď by sa nám hodilo, aby sieť resp. tok mali špecifické vlastnosti. Ukážeme si rôzne varianty problému maximálneho toku ktoré dokážeme riešiť tak, že ich prevedieme na základnú variantu.

Násobné zdroje a stoky, viz sl. 626-627.
Cirkulácie s potrebami a požiadavkami (circulations with supplies and demands), viz sl. 629-631. Umožňujú modelovať situácie v ktorých nie je rovnováha medzi prítokom a odtokom z vrchola. Pozor, hľadáme cirkuláciu a nie maximálny tok!
Dolné ohraničenia kapacít, viz sl.632-633. Umožňujú formulovať požiadavky na veľkosť toku. Pozor, aj v tomto prípade je úloha formulovaná ako existencia cirkulácie.

Aplikácie

Algoritmom pre výpočet maximálneho toku venujeme veľkú pozornosť preto, že veľa reálnych problémov je možné previesť na problém toku. Asi najznámejšie a najčastejšie používané sú redukcie problémov maximálneho párovania v bipartitnom grafe a počtu hranovo disjunkných ciest. Popis redukcií nájdete na slajdoch 610-616 resp. 619-623. Všimnite si, že v oboch prípadoch má popis redukcie rovnakú schému.

Bipartitnému grafu G priradíme sieť G' (sl. 612).
Ukážeme, že pre každé párovanie v G veľkosti k existuje v G' celočíselný tok s hodnotou k.
Ukážeme, že každému celočíselnému toku v G' s hodotou k zodpovedá párovanie v G veľkosti k.
Z 3 a 4 vyplýva, že maximálnemu celočíselnému toku zv G' zodpovedá párovanie v G s maximálnou veľkosťou.
Ako posledný krok zostáva ukázať, že v sieti G' existuje taký maximálny tok, ktorý je celočíselný a že algoritmus FF vypočíta maximálny celočíselný tok v G'. To je ale tvrdenie Integrality Invariant a Theorem, slajd 540.

Ďalším aplikáciam sú venované cvičenia. Komentáre k jednotlivým príkladom: