380 381

380 Programowanie sieciowe

Rysunek 8.15

W zagadnieniu maksymalnego przepływu wyróżniamy wierzchołek początkowy, zwany źródłem, i wierzchołek końcowy, zwany ujściem. Każda krawędź grafu opisana jest dwoma liczbami, które nazywamy, odpowiednio, przepustowością i przepustowością rezydualną. Należy zaplanować przepływ między źródłem i ujściem, uwzględniający przepustowości wszystkich krawędzi, tak aby łączna wielkość tego przypływu była największa.

Istotną rolę w dalszych rozważaniach odgrywa zasada równowagi przepływu dla wszystkich rozpatrywanych krawędzi, którą można sformułować następująco: dopuszczalne wykorzystanie przepustowości krawędzi w określonym kierunku (nie przekraczające aktualnej przepustowości maksymalnej) skutkuje zmniejszeniem wielkości przepustowości w tym kierunku o wielkość przepustowości wykorzystanej oraz zwiększeniem przepustowości w kierunku przeciwnym o taką samą wielkość. Zasadę tę można wyjaśnić w ten sposób, że planowany przepływ można odwołać (co jest możliwe dzięki zwiększeniu przepustowości w kierunku przeciwnym do rozpatrywanego). Ewentualne odwołanie przepływu skutkuje powrotem obu przepustowości rozpatrywanej krawędzi do wielkości wyjściowych.

8.4.1. Reguły postępowania przy poszukiwaniu maksymalnego przepływu w sieci

W każdej iteracji algorytmu maksymalnego przepływu wykonujemy następujące kroki:

1.    Znajdujemy dowolną drogę prowadzącą od wierzchołka początkowego (źródła) do wierzchołka końcowego (ujścia), dla której przepustowości wszystkich łuków są większe od zera. Jeżeli takiej drogi nie można wyznaczyć, to przepływ nie istnieje (lub maksymalny przepływ wyznaczono już w poprzednich krokach).

2.    Na wyznaczonej drodze znajdujemy krawędź o najmniejszej przepustowości w rozpatrywanym kierunku. Znalezioną przepustowość oznaczamy jako p.

3.    Zmniejszamy przepustowość łuków leżących na znalezionej drodze o p i zwiększamy o tę samą wartość odpowiednie przepustowości rezydualne. Przechodzimy do wykonania kroku 1.

8.4.2. Kolejne iteracje

Prześledzimy przebieg kolejnych iteracji dla zadania sformułowanego w przykładzie 8.3.

Iteracja 1

Konstruujemy pierwszą drogę od źródła do ujścia. Dla wierzchołka 1 mamy trzy możliwości wyboru pierwszej krawędzi: 1—2, 1—3 lub 1-4 (rys. 816).

Arbitralnie decydujemy o wyborze krawędzi 1-2. Z wierzchołka 2 mamy możliwość dalszego kontynuowania poszukiwania trasy — możemy wybrać krawę-

Rysunek 8.16

Iteracja 1

HAKSYWłUlY PKZF.PhYU U SIECI Rozulazuuanie zadania

PRZEPŁYW,282

Skonstruuj dro^e od £r64ł« do