4261638925

5

Stosując algorytm Forda-Fulkersona wyznacz maksymalny przepływ w sieci ze źródła s = 1 do ujść ti = 6 i ti = 7. Przedstaw kolejne kroki wyznaczania rozwiązania. Przy wyznaczaniu ścieżki powiększającej do ścieżki jest zawsze włączany wierzchołek o jak najmniejszym numerze.

Zadanie 18

Bajtolini zamierza otworzyć swoją firmę programistyczną, niestety zamieszkuje on krainę gdzie panuje ogromna biurokracja. Przed założeniem firmy należy odwiedzić szereg urzędów gdzie należy pobrać odpowiednie druki, które z kolei należy złożyć w innych urzędach. Czasem nie jest możliwe pobranie druków z urzędu jeżeli wcześniej nie zostały w nim złożone druki pobrane z innego urzędu. Jeżeli w urzędzie X należy pobrać druk, który ma być złożony w urzędzie Y, to fakt taki zapisujemy w następujący sposób: X —* Y. Dla tak podanego opisu składania diuków w urzędach należy zaproponować algorytm, który umożliwi odpowiedź na pytanie, w jakiej kolejności należy odwiedzać poszczególne urzędy aby założyć firmę (należy skorzystać z jednego z algorytmów, które zostały przedstawione w trakcie zajęć). Zaproponowany algorytm należy wykonać dla następujących danych:

5

6

2

5

1

Zadanie 19

Wykonać algorytm Johnsona dla grafu składającego się z czterech wierzchołków, opisanego macierzą wag.

2    3    4

1 oo 5    1 oo 2 oo oo oo 2

3 oo -3 oo oo

4    -4 oo 2

Zadanie 20

Wykaż, że jeżeli graf nie zawiera cykli o ujemnej długości, to po wykonaniu algorytmu Bellmana-Forda dla każdego luku (u,v) spełniona jest zależność: d[d < d[u] + w(u,v), gdzie d[v\ i d[u] są równe długości