Problema fluxului maxim în reţea de transport. CO - Braila Alexandru

Extras din document

1. Problema fluxului maxim în reţea de transport: modelul matematic al problemei; noţiunea de tăietură; tăietură minimă; teorema Ford-Fulckerson. O retea de transport - graf orientat in care fiecare muchie are asociata o capacitate si o anumita cantitate de flux. Fluxul primit de fiecare muchie tre sa fie <= decat capacitatea acesteia. De asemenea, pt fiecare nod, fluxul ce intra in nod tre sa fie = cu cantitatea de flux ce iese din nod. Din nodul sursa poate doar iesi flux, in timp ce in nodul destinatie poate doar intra flux. Valoarea fluxului unei retele de transport = cu suma fluxului ce iese din sursa sau cu suma fluxului ce intra in destinatie (cele doua fluxuri sunt egale).