#1: Broj maksimalnih tokova u transportnoj mreži Autor/ica: davidiot, Postano: 19:17 ned, 2. 7. 2006 — 1. zadatak s pismenog ispita 28. 6. 2006.
Dokažite tvrdnju: Ako u transportnoj mreži imamo dva maksimalna toka, onda ih postoji beskonačno mnogo.
Molim pomoć, ne znam otkud početi.
Hvala!
#2: Autor/ica: markov, Postano: 23:00 pon, 3. 7. 2006 — Jednostavno rješenje bi bilo uzeti proizvoljnu konveksnu kombinaciju zadanih maksimalnih tokova f_1 i f_2: Za proizvoljan t iz intervala (0,1) promatramo tok zadan s
f(a)=t f_1(a) + (1-t) f_2(a),
na svakom luku a. Nije teško provjeriti da je ovakav tok dopustiv (Kirchoffovost osim u izvoru i ponoru te nenegativnost i ograničenost kapacitetima) i maksimalan. Zbog proizvoljnosti broja t imamo tvrdnju.
Drugo rješenje djeluje kompliciranije, ali i zanimljivije s gledišta transportnih mreža:
Dobar pocetak bi bio luk na kojem se dva zadana toka f_1 i f_2 razlikuju. Uzmimo da je to luk a_1 među vrhovima A i B te f_1(a_1)<f_2(a_1). Zbog Kirchoffovosti u vrhu B, tokovi se razlikuju bar još na jednom luku incidentnim s B. Preciznije, postoji
a) luk a_2 koji nastavlja u istom smjeru kao a_1 za kojeg je f_1(a_2)<f_2(a_2) ILI
b) luk a_2 u suprotnom smjeru od a_1 za kojeg je f_1(a_2)>f_2(a_2).
Primijetite da isti zaključak možemo dobiti ako je B ponor (ili izvor) transportne mreže (tu, naravno, ne koristimo Kirchoffovost, već činjemicu da su vrijednosti tokova f_1 i f_2 jednake).
Taj proces nastavimo i dalje (za novi uočeni luk). U konačnom broju koraka zatvorit ćemo ciklus. Skicirajte primjer! Takav ciklus ne može istovremeno sadržavati izvor i ponor (inače bismo imali put povećanja toka f_1 ili f_2).
Sada nije teško nastaviti sličnom idejom kao u Ford-Fulkersonovom algoritmu: Najmanju vrijednost razlike f_2-f_1 na svim lukovima u tom ciklusu s istom orjentacijom kao a_1 (s obzirom na put kojim smo otkrivali nove vrhove) označimo s D, a najmanju vrijednost razlike f_1-f_2 na suprotnim lukovima s d. Neka je T manji od brojeva d i D. Ako povećamo tok f_1 za t<T na lukovima s istom orjentacijom kao a_1, odnosno smanjimo za t na suprotnim lukovima, dobivamo također maksimalan dopustivi tok.
