Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#2 04. 01. 2009 20:54
- kaja.marik
- Veterán
- Příspěvky: 1915
- Reputace: 57
Re: maximální tok
Je na to algoritmus. V nektere literature se myslim jmenuje Forduv Fulkersonuv. Zkuste ho pohledat v knihach o teorii grafu. Nejake odkazy jsem sem na forum daval, http://forum.matweb.cz/viewtopic.php?id=5322
Offline
#4 04. 01. 2009 22:17
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4246
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: maximální tok
Zkus uvažovat takhlle:
Cestou Z-A-B-S proteče kolik? Evidentně 7. Proto odečteme 7 od všech hran na této cestě.
Cestou Z-A-B-D-S proteče pouze 2, od všech hran na této cestě odečteme 2.
Cestou Z-A-C-D-S proteče 4 (to je kapacita cesty Z-A po předchozích odečteních), odečteme od jejích hran 4.
Cestou Z-C-D-S proteče 7, odečteme od jejích hran 7.
Cestou Z-C-E-F-S proteče 9, od jejích hran odečteme 9.
Teď si všimneme, že do vrcholů D,F,S nevedou žádné hrany s nenulovou kapacitou, nalezený tok zvýšit nelze. Minimální řez proto odděluje vrcholy D,F,S od zbytku. Celkový tok je roven součtu odečtených hodnot, tedy 7+2+4+7+9=29.
Cesty přitom vybíráme prohledáváním grafu do hloubky (mírně modifikovaným, pokud je na nalezené cestě nějaká hrana vynulovaná, nemá smysl dál uvažovat cesty, které ji obsahují.)
BRKOS - matematický korespondenční seminář pro střední školy
Offline