Page 1 of 1

[D&A] Vraagje Lemma 4.1 p19

Posted: Tue Jun 09, 2009 6:28 pm
by zarry
Er sta zo da die afstand minimaal moet zijn in da bewijs en dan zo iets tussen haakjes.. Hoe komt da? En dan zeggen ze zo wa verdere: Therefore, (u, v) cannot be an edge in Gf, waarom is da? Zou vet zijn als iemand da ff zou wille uitlegge want kheb da al paar keer geleze en ksnap da echt ni :D wsl is da ni eens zo moelek!

Posted: Tue Jun 09, 2009 6:44 pm
by VFlicka
f' komt na f.
En omdat ermonds-karp het kortste pad neemt veronderstellen we het omgekeerde.
Dus sigma_f(s, v) > sigma_f'(s, v) (dit is dus fout he ;))
met sigma_f'(s, v) minimaal: als er toch een korter pad in f' bestaat (s, u) dan was het in de vorige flow f maximaal even lang, dus hadden we toen (s, u) moeten selecteren.

Posted: Tue Jun 09, 2009 6:48 pm
by zarry
ja zoiets dacht ik al :D kzal da gewoon zo opschrijve :)