382 383

382 Programowanie sieciowe

dzie 2-3, 2-5 lub 2-6 (rys. 8.17). Załóżmy, że decydujemy się na wybór krawędzi

2- 3 i znajdujemy się teraz w wierzchołku 3. Ponieważ przepustowość krawędzi

3- 4 jest równa 0, jedyną możliwością, jaka pozostaje, jest wybór wierzchołka 5 (rys. 8.18). Przepustowości krawędzi 5-6 oraz 5-4 są równe 0, stąd ponownie jedyną możliwością, która pozostaje, jest wybór wierzchołka 7 (rys. 8.19). Otrzy-

Rysunek 8.18

Fl-ponoc    łtfiKSmftUfy PRZEPŁYW u SIECI    PRZEPŁYW.282

_Rpzuiazijuanic zadania

Iteracja 1

mujemy w ten sposób pierwszy przepływ w sieci, który przechodzi przez wierzchołki I -2-3~5-7. Określamy wielkość tego przepływu, którą jest minimalna wartość przepustowości (zgodnej z kierunkiem przepływu) na krawędziach tworzących tę drogę (rys. 8.20). Obliczamy nowe przepustowości dla krawędzi, które zostały wykorzystane w rozpatrywanym przepływie. Sposób obliczania nowych przepustowości ilustruje tablica 8.1.

Rysunek 8.19

Rysunek 8.20