|
|
Toky cestami omezené délky
Altmanová, Kateřina ; Kolman, Petr (vedoucí práce) ; Pangrác, Ondřej (oponent)
V bakalářské práci se zabýváme problémem k-omezeného toku, a tedy toku, který lze dekomponovat na cesty délky nejvýše k. Podáváme přehled o známých výsledcích v této oblasti a zmiňujeme také problém k-omezeného řezu, což je množina hran z tokové sítě, která po odebrání z tokové sítě způsobí, že nee- xistuje v takto pozměněné síti k-omezený tok. Hlavním cílem práce je detailní prozkoumání článku The Maximum k-flow in a Network od autorů V. Kou- bek a A. Říha, publikovaného ve sborníku konference Mathematical Foundations of Coputer Science 1981, str. 389-397 a podání vysvětlení složitých pasáží a do- plnění vynechaných důkazů. Cíl doplnit chybějící důkazy, v této práci naplněný není. Ukázalo, že v citovaném článku mají autoři zásadní chybu. Místo doka- zování vynechaných důkazů se zaměřujeme na popsání problému, proč původní algoritmus nefunguje. 1
|
host ::
RSS.