#1 03. 01. 2012 17:46
Maximální tok grafu
Dobry podvečer, chtel bych se jenom presvedcit ze dane problematice rozumim a proto bych potreboval overit vysledek toho to grafu.
Najdete maximalni tok grafu mezi vrcholy x a y
Vyslo mi ze maximalni tok je 22. Ale nejsem si prave jisty. Tak jestli by nekdo mohl potvrdit a nebo vyvratit. Predem dekuji :)
Nejsem dokonalý a i já dělám chyby z kterých se holt učim.
Offline
#3 03. 01. 2012 19:08
Re: Maximální tok grafu
Také bych řekl, že 24. Po každé hraně z x můžu poslat tok o maximální kapacitě té hrany (pokud se správně koukám, tak to skutečně projde), no a pokud tohle je správný tok, tak větší už určitě nenajdeš – to by po některé hraně ze zdroje muselo téct více než je její kapacita.
Mýlím se častěji, než bych chtěl. Pokud vám v mém příspěvku něco nehraje, neváhejte se zeptat.
Jsem stále mlád a je mi příjemnější tykání. :)
Offline
#4 04. 01. 2012 09:14 — Editoval NaEx (04. 01. 2012 18:02)
Re: Maximální tok grafu
EDIT:Omlouvám se za šíření klamných informací, tok je opravdu těch 24, nevšimnul jsem si jedné hrany..
původní:
(Tlacenka: Ten obrázek už jsem někde viděl:), že by naše skripta... str. 113
Ale výsledek mám jako ty tzn. 22
tady je algoritmus, který je daleko elegantnější, než učili nás : http://forum.matweb.cz/viewtopic.php?id=5763
Stýv, Oxyd : Tok 24 by byl v případě, že by hrana "w-t" byla orientovaná opačně, jinak to není možné, výsledek je tedy podle mě těch 22.)
Offline
#5 04. 01. 2012 10:23
Re: Maximální tok grafu
Já bych si to rozdělil na čtyři části:
Cesta x-v:
Směrem x-u-v projde 3
Přímým směrem x-v projde 8
Tedy celkem 11
Cesta v-y
Směrem v-w-y projde 3
Přímým směrem v-y projde 9 (využijeme pouze 8)
Tedy celkem 12 (využijeme pouze 11)
Horní částí může projít pouze 11 (celkové omezení předchozí cesty x-v)
Cesta x-s
Směrem x-r-s projde 5
Přímým směrem x-s projde 8
Tedy celkem 13
Cesta s-y
Směrem s-t-y projde 3 (omezeno s-t na 3)
Přímým směrem s-y projde 10
Tedy celkem také 13
Průchodnost dolní částí je 13
Celkový tok horní a dolní části je tedy 11+13=24
Offline