386 387

386 Programowanie sieciowe

Tablica 8.3

Krawędź	Przepustowości poprzednie		Przepustowości nowe
1-2	2	3	2-2=0	3 + 2 = 5
2-6	3	0	3-2=1	0 + 2 = 2
6-7	2	0	2-2 = 0	0 + 2 = 2

Iteracja 4

Konstruujemy czwartą drogę od źródła do ujścia. W tym celu wykorzystujemy zmodyfikowane przepustowości. Otrzymujemy drogę 1-4-7. Porównanie wyróżnionych wartości przepływu wskazuje na to, że przepustowość tej drogi jest równa 4 (rys. 8.23).

Rysunek 8.23

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.4.

Tablica 8.4

Krawędź	Przepustowości poprzednie		Przepustowości nowe
1-4 4-7	7 4	0 0	7-4 = 3 4-4 = 0	0 + 4 = 4 0 + 4=4

Iteracja 5

Przystępujemy do próby konstrukcji kolejnej drogi prowadzącej od źródła do ujścia. Wykorzystujemy w tym celu sieć ze zmienionymi po raz kolejny przepus-towościami. Kolejne próby pozwalają nam skonstruować drogi, które nie dochodzą jednak do ujścia. Otrzymujemy kolejno:

1-3-2-6-5,

I-3-5-6,

1 -4-3—2—6—5,

1-4-3-5-2-6,

1-4-5-3-2-6,

1 -4-5—2—6.

Żadna z tych dróg nie prowadzi do ujścia. Ponieważ wyczerpane zostały w ten sposób wszystkie możliwości tworzenia nowych dróg i żadna z nich nie doprowadziła do wierzchołka końcowego, oznacza to, że przepustowości czterech dróg znalezionych w poprzednich iteracjach określają maksymalny przepływ w rozpatrywanej sieci. Zostało to pokazane na rys. 8.24.

Rysunek 8.24

Rozwiązanie optyetalne