Uvjet za kraj Ford-Fulkersonovog algoritma

[Melkor]

Ford-Fulkersonov algoritam staje kad više ne možemo pronaći put od izvora do ponora na kojem bi se tok mogao povećati. To znači da bi na kolokviju morali provjeriti sve moguće putove tražeći eventualno povećanje. No, za neki malo veći graf takvih putova može biti jako puno. Ima li kakav koristan trik kako bismo mogli zaključiti da se tok ne može dalje maksimizirati?

_________________
I don't know half of you half as well as I should like; and I like less than half of you half as well as you deserve.

[Casper]

[goranm]

[Melkor]

[vili]

[goranm]

U svakom slučaju, za dovoljno jednostavni graf netreba puno vremena da se uoči minimalni i-p rez.
I-p rez se može smatrati kao metoda provjere rješenja.
Ako se popune kapacitieti, ali tako da su manji od kapaciteta pronađenog minimalnog i-p reza, onda očito se još negdje mora ići u suprotnom smjeru.
Uglavnom, korisno je znati jaku dualnost.

_________________
The Dude Abides

[Nesi]

u praxi, iz vlastitog gusta sam isla rjesavati sve zadatake koji su bili dopstuni online prije 2 godine.... u prosjeku ti treba 5 minuta krampanja ili vise ako zeznes, ili si gotov 3-4 poteza, ili je toilko ocito da ti je dosadno pisati jer moras step by step iako mislis da vidis rjesenje (i onda zbilja to bude)

zbilja ugodni zadaci.... samo preporucam ici ih vjezbati... rijesiti ih barem 5-10... samostalno

na kolokviju gdje sam bila je zbilaj bilo gotovo u cca 5 ocitih poteza, a onaj prekrivac jedinica u matrici je trebalo 3 poteza...

_________________
It's not who you love. It's how.

[filipnet]

mene malo bune te dualnosti, tj. dal uvijek i-p rez mora biti jednak maksimalnom toku da zadatak bude tocan? po slaboj dualnosti znaci da ne mora, ako sam dobro skuzio?

_________________
Everything happens with a reason!

[Braslav]

@filipnet
Naravno da ne, samo minimalan i-p rez je jednak maksimalnom toku, nekakav drugi je zapravo strogo veci.

Inace ja te zadatke rjesavam onako vrticki, donesem bojice pa
svaki put povecanja toka mi je linija druge boje. Na kraju to izgleda
puno preglednije nego da sam crtao 3-4 posebna grafa, a da ne kazem koliko je brze gotovo.

@melkor
Isprva tok je uglavnom takav da (gotovo) kojim god putem krenuo
imas put povecanja toka. Kasnije kada si nakon kojih 3-4 takva puta vec se priblizio krajnjem rijesenju mozes krenuti zaokruzivati cvorove do kojih mozes doci putem povecanja.
Samim trazenjem puta povecanja mozes vidjeti minimalan i-p rez
jer jednostavno vidis cvorove u koje mozes doci povecanjam, a u chije susjede ne mozes jer npr ulazi maksimalno sto upoce moze izaci. Ako to vrijedi za svaki cvor sa "granice izmedu cvorova prve i druge vrste" tada
imas mak tok i min i-p rez.