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

Skonstruuj dro^e od £r64ł« do

Wyszukiwarka

Podobne podstrony:
370 371 370 Programowanie sieciowe Rysunek 8.4 Iteracja 4 Do zbioru wierzchołków połączonych zalicza
376 377 376 Programowanie sieciowe Rysunek 8.10 FI - ptMttoc Iteracja 3 NAJKRÓTSZE DK0G1 U SIECI Rof
Wybrane zagadnienia bezpieczeństwa danych w sieciach komputerowych Rysunek 15. Schemat systemu wykry
Przechwytywanie w trybie pełnoekranowym 03 023800 Kultura języka polskiego. Teoria. Zagadnienia le
Przechwytywanie w trybie pełnoekranowym 03 023809 U Kultura języka polskiego. Teoria. Zagadnienia
skanuj0003 (13) 380 PROGRAMY EUROPEJSKIE ® miasta    1---1—1— —1 516 t ostoje przyrod
50 w funkcji naprężeń. Rysunek 3.15 przedstawia okno programu z wprowadzoną krzywą pierwszego magnes
372 373 Programowanie sieciowe8.3. Najkrótsze drogi w sieci Omówienie zagadnienia poszukiwania najkr
> Zarządzanie sieciami WAN <13 Rysunek 15. Rodzaje łączy w sieciach asynchronicznych ATM Sieć
img010 Treści programowe: Seminaria od 8.15 (3 x 90 minut) I.    Odmienności budowy a
IMG98 Metody programowania sieciowego wprowadzono pod koniec lat pięćdziesiątych naszego wieku
s216 (2) 216 Hoznai Lmux 4 W oknie Category (rysunek 15.6) wskaż kursorem menu Navigator (rysunek 15
Rysunek 15: Funkcja przynależności trapezoid * gauss Rysunek 16: Funkcja przynależności complement(g

więcej podobnych podstron