Matematické Fórum

Ford-Fulkersonov algoritmus pracuje na grafe, kde hrany maju hodnotu rezervy. V každom kroku algoritmu hľadáš, či existuje cesta od zdroje k stoku s kladnou rezervou, oznacuje sa niekedy ako vylepsujuca cesta (augmenting path). Pokial ju najdes, posles cestou tolik toku kolik je hodnota nejmensi rezervy na ceste. Na zaciatku algoritmu sa kapacita rovna rezerve. Teda priklad prveho kroku v Tvojom priklade by bola povedzme cesta z-a-d-s. Najmensia rezerva na tejto ceste je na hrane a-d, coz je 1. Posleme teda touto cestou tok velkosti 1. A znizime rezervu o 1 na tejto ceste, teda na hranach z-a-d-s budu hodnoty 1,0,3. Kedze je to ale rezerva a nie kapacita, tak v protismere na ceste s-d-a-z budeme mat hodnoty 1,1,1. Rezerva totiz neznamena len kapacitu ale aj tok po protilahlej hrane. Rozdiel medzi rezervou a kapacitou by som odporucal studovat z nejakych materialov.
To je jeden krok, a taketo kroky robis dovtedy, kym neupravis graf do tej podoby, ze nenajdes ziadnu orientovanu cestu od zdroja do stoku. Budes tam mat totiz nulove hrany, ktore ti v tom zabrania.  A body ktore ziskas jednoduchym prehladavanim do sirky/dlzky od zdroju budu v mnozine R. A nulové hrany incidentné  s bodmi v mnozine R budu tvoriť požadovaný rez.

Takze spravnejsia formulaci by podla mna znela:

Maximalní tok získam Ford-Fulkersonovym algoritmom, kde v kazdom kroku algoritmu hľadám vylepšujúcu cestu. Keďže graf má racionálne kapacity, algoritmus prejde v konečnom čase. Vďaka ford-fulkersonovej vete viem, že veľkosť minimálneho rezu oddelujuceho zdroj a stok sa rovná veľkosti maximálneho toku medzi zdrojom a stokom. Teda pokiaľ mám tok F velkosti T a nájdem rez C velkosti T, tak C je dôkazom (niekedy sa hovorí, certifikátom), že F je maximálny.

body nemaji rezervu, hrany maji rezervu. Na konci FF algoritmu by nemela byt zadna cesta od zdroje k stoku, ktera by neobsahovala hranu s nulovou rezervu, takze pokud pustim DFS alebo BFS od zdroje, tak dostanu mnozinu bodu, ktere jeste dosahnutelne jsou, stok mezi nimi nebude. Nulove hrany incidentne s temito vrcholy budou tvorit minimalni rez.

Nerozumim znaceni na tvem obrazku. Pokud dvojice (a,b)  je a-rezerva ve smeru sipky, b-rezerva proti smeru sipky. Pak este graf neni v konecnem stadiu, protoze muzes najit dalsi nenulove cesty, treba z-b-d-s.

edit: uz chapem znaceni, je to (tok, kapacita), ale to neni dobre, ty musis pracovat s rezervami, ne s kapacitami a tokem. Tok dopoctes jenom na konci algoritmu. Pokial C(u,v) je kapacita hrany u,v,
F(u,v) je tok hranou u,v. Potom rezerva na hrane u,v je R(u,v)=C(u,v)-F(u,v)+F(v,u). Rezerva nie je teda len rozdiel medzi tokom a kapacitou, musis pripocitat aj tok v protilahlom smere. Tiez musis pocitat, ze pokial v povodnom grafe su hrany len v jednom smere, tak si musis domysliet, ze v opacnom smere je tiez hrana s kapacitou 0, v urcitom kroku algoritmu ale tam moze byt rezerva kladna. Napriklad v tvojom priklade je R(a,d)=1-1+0=0. Ale R(d,a)=0-0+1=1.V kazdom kroku algoritmu ale je bud F(u,v) alebo F(v,u) rovne nule, tok tecie jenom jednym smerem. Pracujes teda s grafom, kde hrany mas ohodnotene rezervami. Na konci budes mat nulove hrany a plati co jsem psal vyse.

Myslim, ze si docela ignoroval moji poznamku o rezervach, skus spocitat rezervy na hranach

z-a-e-b

podle toho co jsem psal vyse, teda R(u,v)=C(u,v)-F(u,v)+F(v,u).  Touhle cestou se dostanes k b.
trik je totiz v tom, ze na hrane (e,b) (ne (b,e)) je rezerva 1, pretoze v protismere jede proud 1.

nezamotal si sa do toho, presne tak to funguje, pokud poslel proud nejakou hranou, automaticky musis v protismeru zvysit o tolik rezervu. A zduraznuju, ze vo FF algoritmu pracujes prave z rezervou. Postup by mal byt teda taky, ze na zacatku algoritmu si vsude namisto kapacity napises rezervy, v algoritmu pracujes s rezervami. Na konci algoritmu prevedes rezervy na tok.

To jestli vyhledani R spada do FF, zavisi od toho jak si to udelas, jak chytre si to naprogramujes. FF slouzi primarne na vyhledani maximalniho toku, jestli potrebujes mnozinu R, tak si to tam dodelas tim prohledavanim od zdroje. Inak mam stale pocit, ze tomu nerozumis kdyz mluvis "najdu všechny cesty z Z do S". To nie je celkom pravda, pretoze tym, ze v protismere hran ti vznikaju kladne rezervy tak v kazdom kroku algoritmu ti moze pribudnut nejaka dalsia cesta od zdroja k stoku. Takze presnejsie by bolo vyjadrenie, FF hleda vylepsujici cesty do tehdy, kym zadna dalsi vylepsujici cesta neni.
Snad teda je to jasnejsie o nieco.

FF algoritmus sam o sobe muze mit velkou zlozitost. Vime ze pro celociselne a racionalne kapacity urcite dobehne. Pro iracionalni kapacity, nemusi dobehnout vubec. Problem jednokomoditneho toku ktery FF resi (Single-commodity flow problem) a patri do triedy P, pretoze nan existuje polynomialni algoritmus, vylepseni FF, napriklad Edmond-Karp O(m^2n).

Nechcem Ta nejak slovickarit, mne to je v podstate jedno ale veta
Věděl bys ještě do jaké třídy problémů tento algoritmus spadá?
taky moc nedava zmysl. Algoritmy maji casove/prostorove zlozitosti. Zatim co problemy jako treba Single-commodity flow problem patri do tridy P, NP. Tim, ze vime, ze existuje polynomialni algoritmus na Single-commodity flow problem tak vime, ze tento problem patri do P. Dualni problem minimalniho rezu (Minimum cut) taky patri do P, protoze sa resi tim samym algoritmem. Samotny FF ve sve obecne forme ale nedokazuje ze Single-commodity flow problem, protoze ma vysokou casovou zlozitost a pro iracionalni kapacity nemusi vubec dobehnout.

jinak treba o tocich je napsano v textu
http://mj.ucw.cz/vyuka/ga/ga.pdf