Řešení úlohy 7.1
První severní cesta, na které je možné zvýšit tok, je s,V1, V4, V5, t.
Nejmenší kapacitu má hrana mezi uzly V4, V5 (4 jednotky), povedeme po této cestě tok 4.
Hrana se stává nasycenou (označena červeně), po ní už nemůžeme dále zvýšit tok. V závorkách za kapacitou je
u každé hrany aktuální tok.
Další severní cesta, na které je možné zvýšit tok, je s,V3, t. Po této cestě můžeme
„protlačit“ 2 jednotky toku a nasytíme hranu mezi s a V3.
Třetí severní cesta, na které je možné zvýšit tok, je s, V2, V3, t. Omezením je tentokrát
hrana V3,t. Hranou tečou aktuálně 2 jednotky toku, kapacitu má 3, totou cestou můžeme ješte vést navíc
1 jednotku toku.
Na další severní cestě s, V2, V3, V6 t vedeme 3 jednotky toku,
protože to je možné maximum, abychom nasytili hranu V2, V3.
Poslední severní cesta, na které je možné zýšit tok, je s, V2, V6, t. Přidáme 1 jednotku toku
a nasytíme hranu V2, V6.
Nyní již neexistuje žádná cesta, po které bychom mohli zvýšit tok. Maximální tok v síti spočítáme jako součet
aktuálního toku na hranách směřujících do spotřebiče t, tedy 4+3+4 = 11. Provedeme ještě kontrolu: stejný
tok musí téci ze zdroje, tedy 4+2+5 = 11.
