4736387693

Jaką drogę powinien wybrać kierowca, aby zminimalizować koszty podróży. Rozwiązać dwie wersje zadania: przy założeniu, że kierowca zabiera pasażerów oraz przy założeniu, że kierowca nie zabiera pasażerów. Czy w obu przypadkach można zastosować algorytm Dijkstry? Odpowiedź uzasadnić.

3.    Znaleźć (w książce lub w internecie) algorytm znajdowania najkrótszej drogi w grafie (różny od algorytmu Dijkstry oraz Bellmana-Forda) oraz zastosować go do rozwiązania poprzednich zadań.

4.    Na podstawie algorytmu Dijkstry opracować algorytm znajdowania najkrótszej drogi wyjścia z labiryntu.

10. Przepływ w sieciach

1.    Udowodnić następujący lemat, który pojawił się na wykładzie. Niech G = (V, E, s, t, c) będzie siecią oraz niech / będzie przepływem w G. Ponadto niech f będzie przepływem w sieci residualnej Gf. Wtedy funkcja f + f jest przepływem w G o wartości |/ + f'\ = \ f\ + \f'\.

2.    Niech G = (V, E,s,t,c) będzie siecią oraz niech / będzie przepływem w G. Udowodnić, że

(a)    dla wszystkich X CV mamy f(X,X) = 0;

(b)    dla wszystkich X,Y CV mamy f(X,Y) = —f(Y,X).

(c)    Dla wszystkich X, Y, Z C V zachodzi:

f(x u y, z)=f(x, z) + f(Y, z) - f(x n y, z) f(z,x u Y)=f(z, X) + f(z, Y) — f(z,x n y).

(d)    \f\ = f(s,V) = f(V,t).

3.    Pokazać, że jeśli w sieci G = (V, E, s, t, c) przepustowość c przyjmuje wartości całkowitoliczbowe, to (niezależnie od wybranej metody znajdowania ścieżki powiększającej)

(a)    maksymalny przepływ obliczany metodą Forda-Fulkersona jest całkowitoliczbowy,

(b)    pesymistyczny czas działania algorytmu Forda-Fulkersona wynosi 0(\E\ • 1/1), gdzie / jest maksymalnym przepływem w G.