Matematické Fórum

Kdyz jsem se kdysi ucil tento algoritmus a jemu podobne, taky mi prislo divne posilat tok proti smeru hrany. Tady je moje pomocka, pomoci ktere jsem tomu porozumel. Mejme sit

          Z
         / \
        /   \
       /     \
      v      v
     A <----B
     \         /
      \       /
       \     /
        v  v
          S

Kde hrany jsou jednosmerne silnice s pouze jednim pruhem (kapacita kazde hrany je 1). Je celkem jasne, ze kdyz chci poslat co nejvic aut z bodu Z do bodu S, tak poslu dve kolony, jedna cestou Z-A-S, druha cestou Z-A-S. Kdybych ale tento tok hledal FF algoritmem, muzu nejdriv objevit cestu Z-B-A-S. Poslu kolunu aut, ale ta druha uz se mi tam nevejde. Kdybych to resil, jako nejaky kontrolor dopravy, tak bych proste rekl, ze auta misto z bodu B do A pojedou z B do S. Tim se mi uvolni cesta A-S, a tedy i cela cesta Z-A-S, kterou muzu poslat opet celou jednu kolonu.  Tento postup ma uplne stejny vysledek, jak kdyz poslu jednotkovy tok zlespujici cestou Z-A-B-S proti smeru hrany B-A. Z tohoto pohledu je taky jasne, proc nemuzu posilat tok proti smeru hrany, pokud v ni po smeru jeste nic netece. Je to vlastne, jako bych ten tok zatlacil zpatky.

↑ Lishaak:Už je mi to jasnější (názorných vysvětlení není nikdy dost, obzvlášť zde v matematice), když FF algoritmem nešikovně zatarasím jiné potenciální cesty, maximální tok bude stejný, jako kdyby se cesty rovnou vybíraly šikovně (Dinicův/Edmonds-Karpův algoritmus), prostě se to tam musí nějak naskládat.

↑ nordec:

Racionální kapacity snadno pořešíš tak, že vezmeš nejmenší společný násobek jmenovatelů X a tím ty kapacity vynásobíš. Pak máš celočíselné kapacity. Najdeš max. tok, ten je X krát větší než max. tok v původní síti.

Pro iracionální čísla výše zmíněný postup nefunguje. Mj. další algoritmy popsané v tom textu zvládnou i iracionální čísla.

↑ nordec:Zacyklí se to, pokud nevhodně vybíráme ty cesty. Může se nám stát, že pořád něco přičítáme, ale jsou to čím dál menší čísla, tu "nejdůležitější" vylepšovací cestu opomíjíme. Můžeme tak třeba do nekonečna přičítat 1+1/f+1/f^2+1/f^3+... , kde f<1 součet bude 1/(1-f), ale někde vedle vede hrana s kapacitou 42/(1-f), ke které se nedostaneme. U racionálních kapacit je tomuto zabráněno tím, že nikdy nevylepšujeme o méně než 1/d, kde d je společný násobek jmenovatelů všech kapacit (použijeme-li trik s vynásobením, pak vždy vylepšujeme alespoň o 1).