Netwerkmodellen, maxflow, ford fulkerson-algoritme

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer

Bericht 26-01-'12, 14:35

hir

Berichten: 114

Netwerkmodellen, maxflow, ford fulkerson-algoritme

- Ik begrijp niet goed waarom men bij het Ford Fulkerson-algoritme in een pad een achterwaartse boog (backward arc) mag gebruiken, in het echte netwerk is het toch onmogelijk om een pad te nemen waar de achterwaartse boog in voorkomt?

- Als residuele capaciteit neemt men voor deze achterwaartse boog zijn huidige stroom. Ik veronderstel dus dat dit de capaciteit waarmee de huidige stroom van de achterwaartse boog kan verminderen.

Maar als men de werkelijke stroom van de achterwaartse boog verminderd, hoe kan het algoritme dan garanderen dat er een omleidend pad zal zijn voor deze achterwaartse boog en daarbij dat het omleidend pad nog voldoende residuele capaciteit heeft om deze extra stroom op te vangen ?
Omhoog
Reageer

Terug naar “Wiskunde”