Forum@DeGiorgi :: Pogledajte temu - Ford, Fulkerson, 1. kolokvij

through

[^/[Print]\]

Forum@DeGiorgi -> Matematičko modeliranje

#1: Ford, Fulkerson, 1. kolokvij Autor/ica: Unnamed One,

Postano: 22:08 čet, 5. 1. 2006
—
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? Confused

#2: Autor/ica: vili, Lokacija: Keglić

Postano: 22:57 čet, 5. 1. 2006
—
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 Confused

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 Wink

#3: Autor/ica: Unnamed One,

Postano: 23:54 čet, 5. 1. 2006
—
Hvala na odgovoru.
Planirao sam se nešto žaliti na taj zadatak - čini se da ipak ništa od toga... Crying or Very sad

Riješio sam taj zadatak na sličan način kao i ti, ali sad vidim gdje sam pogriješio: Shocked

nisam krenuo od nultoka, nego od zadanog toka.

#4: Re: Ford, Fulkerson, 1. kolokvij Autor/ica: markov,

Postano: 23:37 pet, 6. 1. 2006
—

Unnamed One (napisa):

[i]

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? Confused

Dobar početak. Ako se radi o luku iz S^c u S (za NEKI minimalan i-p rez (S,S^c)), prema tom zadatku s vježbi upravo slijedi zaključak da je za SVAKI maksimalan tok vrijednost toka na tom luku nužno jednaka nuli.

#5: Autor/ica: Grga,

Postano: 11:47 ned, 8. 1. 2006
—

Unnamed One (napisa):

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

Mozes rijesiti kontradikcijom. Tj, pretpostavis da tok u tom luku moze biti 1, tada gledas koji lukovi moraju biti u S i u komplementu (ako je vrh povezan s drugim vrhom koji je iz komplementa, i ukupan zbroj kapaciteta koji ulaze od njega manji od kapaciteta na tom luku, tada i taj vrh mora biti u komplementu), i dobijes kontradikciju.

#6: Autor/ica: Unnamed One,

Postano: 21:51 ned, 8. 1. 2006
—
@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.

#7: Malo pojašnjenje Autor/ica: markov,

Postano: 0:42 pon, 9. 1. 2006
—

Unnamed One (napisa):

@markov
Jesi li 100% siguran da vrijedi "za SVAKI"?

Jesam. Premda je za rješenje tog zadatka s vježbi potrebna teorija (jaka dualnost) za ovu primjenu je ipak dovoljno samo pažljivo pročitati zadatak. Da ne bude zabune citirat ću ga.

Neka je (S,S^c) minimalan i-p rez i f maksimalan tok. Tada
Za svaki luk a iz S u S^c vrijedi f(a)=c(a),
Za svaki luk a iz S^c u S vrijedi f(a)=0.

Nigdje nisu specificirani maksimalni tok i minimalni i-p rez (mogu biti proizvoljni - ako ih ima više). Dakle, ne bi trebalo biti teško pročitati: Ako za NEKI minimalan i-p rez luk a ide iz S^c u S onda vrijedi f(a)=0 za bilo koji (SVAKI) maksimalan tok f.

#8: Autor/ica: Unnamed One,

Postano: 16:06 pon, 9. 1. 2006
—
@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.

#9: Autor/ica: markov,

Postano: 10:12 uto, 10. 1. 2006
—

Unnamed One (napisa):

@markov
Ispričavam se ako sam ispao nepristojan.

Niste. Sve OK.

Citat:

Jednostavno nisam odmah shvatio nešto što je ipak prilično očito. Hvala na objašnjenju.

Nije baš tako očito. Ipak je to bio jedan od težih detalja na kolokviju.

Citat:

Hvala na objašnjenju.

I drugi put.

Forum@DeGiorgi -> Matematičko modeliranje

output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Stranica 1 / 1.