Ford, Fulkerson, 1. kolokvij

[Unnamed One]

Neka je zadana transportna mreža i na njoj neki početni tok.
(a) Ford Fulkersonovim algoritmom odrediti jedan maksimalan tok.
(b) Pronaći jedan minimalni i-p (s-t) rez.
(c) Postoji li maksimalan tok u kojem je neki luk (nazovimo ga L) kapaciteta 1 saturiran?

Ovo je bio jedan od zadataka na ovogodišnjem prvom kolokviju iz modeliranja. (a) i (b) dijelovi su prilično jasni - riješili smo više takvih zadataka na vježbama. Pitanje je kako riješiti (c).

Jedina ideja koja mi pada na pamet je zadatak koji smo riješili na vježbama u kojem se tvrdi da ako luk ide iz S u S^c onda je saturiran, tj. ako ide iz S^c u S onda je tok na tom luku 0. Ako sam pod (a) dobio da taj luk L ide iz S^c u S mogu li iz toga zaključiti da ne postoji maksimalan tok u kojem je taj luk saturiran?

[vili]

Nisam baš siguran da to možeš zaključiti, osim ako je to jedini minimalni i-p rez. Valjda bi se dao iskonstruirati neki primjer

Ja sam to riješio tako da sam uzeo početni tok sve 0 i krenuo redom. Prvo sam ubacio neko proširenje toka koje će ići tim spornim lukom(meni je bilo samo jedno takvo moguće, ali inače mislim da bi se trebali razmotriti i drugi slučajevi).
Dalje sam tražio puteve povećanja toka i povećavao ga, ali tako da niti jedan ne mjenja tok na spornom luku i na kraju došao do toga da nemam više puteva povećanja toka koji ne idu preko tog luka, a ako ubacim put povećanja toka preko tog luka, imam maksimalan, i ne mogu tok na luku nikako vratit na 1.

Hope it helps

[Unnamed One]

Hvala na odgovoru.
Planirao sam se nešto žaliti na taj zadatak - čini se da ipak ništa od toga...
Riješio sam taj zadatak na sličan način kao i ti, ali sad vidim gdje sam pogriješio: nisam krenuo od nultoka, nego od zadanog toka.

[markov]

[Grga]

[Unnamed One]

@markov
Jesi li 100% siguran da vrijedi "za SVAKI"?
Kao što vili kaže to bi moglo biti u redu ako imam samo jedan i-p rez. Meni u bilježnici piše da ako luk ide iz S u S^c onda je saturiran, ako ide iz S^c u S onda je tok na njemu 0, ali nigdje ne kaže da ako je, npr. vrh A iz S, vrh B iz S^c s obzirom na neki max-tok koji promatram da je onda luk AB saturiran u nekom novom max-toku. Čini mi se da je to ipak puno jača tvrdnja koja mi baš i nije očita iz iskaza zadatka. S 2. strane nisam baš doma s teorijom pa je lako moguće da sam nešto propustio.

@grga
Hvala na odgovoru.

[markov]

[Unnamed One]

@markov
Ispričavam se ako sam ispao nepristojan. Nije mi to bila namjera. Jednostavno nisam odmah shvatio nešto što je ipak prilično očito. Hvala na objašnjenju.

[markov]