Ovako:
Znam da treba ulazni graf transformisati u jedinicni graf (nesto kao kod matchinga), a posebno sacuvati informacije o dubinama pojedinih grana.
Dalje, shvatio sam i da treba ogranicenost protoka kroz cvorove na 1 resiti formiranjem dva cvora i postavljanjem grane kapaciteta 1 izmedju njih.
I sad, kada pustim Ford-Fulkersonov algoritam nad takvim grafom, protok koji mi on saopsti mi je broj disjunktnih puteva kojima voda u izvornoj formulaciji treba da tece, zar ne?
Moje pitanje glasi: kako sad da odredim te puteve?
Jer, ako znam koji su to putevi, jednostavno prodjem njima u onom izvornom grofu i nadjem najdublju ivicu i time je zadatak rijesen.
Dakle, kako da u Ford-Fulkersonovom algoritmu odredim puteve (odnoso, njima prodjem)?
Znam da treba ulazni graf transformisati u jedinicni graf (nesto kao kod matchinga), a posebno sacuvati informacije o dubinama pojedinih grana.
Dalje, shvatio sam i da treba ogranicenost protoka kroz cvorove na 1 resiti formiranjem dva cvora i postavljanjem grane kapaciteta 1 izmedju njih.
I sad, kada pustim Ford-Fulkersonov algoritam nad takvim grafom, protok koji mi on saopsti mi je broj disjunktnih puteva kojima voda u izvornoj formulaciji treba da tece, zar ne?
Moje pitanje glasi: kako sad da odredim te puteve?
Jer, ako znam koji su to putevi, jednostavno prodjem njima u onom izvornom grofu i nadjem najdublju ivicu i time je zadatak rijesen.
Dakle, kako da u Ford-Fulkersonovom algoritmu odredim puteve (odnoso, njima prodjem)?