Úloha 1 (Pomalý vstup): Najděte příklad sítě s nejvýše 10 vrcholy a 10 hranami, na níž Fordův-Fulkersonův algoritmus může provézt více než milion iterací.

Úloha 2 (Oprava?): Ukázalo se, že Fordův-Fulkersonův algoritmus nevrátí maximální tok, pokud dovolíme zlepšovat tok pouze po směru hran. Opravíme tento problém, budeme-li uvažovat pro zlepšení toku nejkratší cesty?

Úloha 3 (Svišti): Na louce je $n$ svišťů a $m$ děr v zemi (obojí je zadáno jako body v rovině nebo raději body v nepříliš velké celočíselné mřížce). Když se objeví orel, zvládne svišť uběhnout pouze $d$ metrů, než bude uloven. Kolik maximálně svišťů se může zachránit útěkem do díry, když jedna díra pojme nejvýše jednoho sviště? A co když pojme $k$ svišťů?

Úloha 4 (Šachovnice s dírami): Mějme šachovnici velikosti $r \times s$, ve které chybí některá políčka. Chceme na ni postavit co nejvíce věží tak, aby se navzájem neohrožovaly. Věž nemůžeme položit na chybějící políčko a ohrožuje celý řádek a sloupec, na kterém stojí.

Úloha 5 (Hranově disjunktní cesty): Navrhněte algoritmus, který pro zadaný orientovaný graf a jeho vrcholy $u$ a $v$ nalezne největší možný systém hranově disjunktních cest z $u$ do $v$. Jak se situace změní, pokud graf bude neorientovaný?

Úloha 6 (Vrcholově disjunktní cesty): Upravte předchozí algoritmus, aby našel dokonce vrcholově disjunktní cesty (až na $u$ a $v$).

Úloha 7 (Šachovnice se sloupy): Znovu chceme pokládat věže, ale tentokrát v šachovnici $r \times s$ jsou sloupy. Věže pak neohrožují přes tyto sloupy. Navrhněte efektivní algoritmus, který takové rozestavění najde.

Úloha 8 (Nekonečno): Najděte síť s reálnými kapacitami, na níž Fordův-Fulkersonův algoritmus nedoběhne. Lze dokonce zařídit, aby k maximálnímu toku ani nekonvergoval.