# Toky, řezy, cesty Kolman 9. 6. 2014

<{ForumPost(poster="mathemage", timestamp=2014-06-10 19:10:56)}>
*  Přehled toků a jejich duální problémy  
\[  
součtové vs. spravedlivé (souběžné) toky <-> multiřez vs. nejřidší řez  
potrubní algoritmus a myšlenka, jež se za ním skrývá:  
1) celá síť má stejný objem jako hodnota zlomkového řešení  
2) koule jsou disjunktní $\Rightarrow$ součet objemů je shora omezen objemem sítě a tím pádem i hodnotou zlomkového řešení  
3) min vzorce/poměru, který používáme při hledání ideálního poloměru, je shora odhadnut jistou hodnotou $\alpha$; tudíž cena řezu z této aproximace je shora odhadnuta $\alpha$-násobkem objemů vnitřků koulí. Ten je zase shora odhadnut $\alpha$-násobkem hodnoty zlomkového řešení, z toho příslušný aproximační faktor  
]
*  Generování sloupců

5,5 dne učení, za 1!
<{/ForumPost}>