W ramach laboratorium należy zaimplementować algorytm Forda-Fulkersona, a następnie użyć go jako składnika algorytmu wyznaczania spójności krawędziowej grafów.
Dany jest graf skierowany G = (V,E), funkcja c: E -> N dająca wagi krawędziom, oraz wyróżnione wieżchołki s i t. Należy znaleźć maksymalny przepływ w grafie G pomiędzy s i t, tzn. funkcję f: E -> N spełniającą warunki definicji przepływu, zapewniającą największą przepustowość.
Do rozwiązania zadania należy wykorzystać algorytm Forda-Fulkersona, porównując dwie strategie znajdowania ścieżek powiększających:
Dany jest graf nieskierowany G = (V,E). Spójnością krawędziową grafu G nazywamy minimalną liczbę krawędzi, po których usunięciu graf traci spójność. Przykładowo:
Opracuj i zaimplementuj algorytm obliczający spójność krawędziową zadanego grafu G, wykorzystując algorytm Forda-Fulkersona oraz następujący fakt:
(Tw. Mengera) Minimalna ilość krawędzi które należy usunąć by zadane wierzchołki s, t znalazły się w różnych komponentach spójnych jest równa ilości krawędziowo rozłącznych ścieżek pomiędzy s i t
Wskazówka: jak można zinterpretować ilość krawędziowo rozłącznych ścieżek jako problem maksymalnego przepływu?
loadDirectedWeightedGraph z biblioteki dimacs (funkcja działa tak samo jak loadWeightedGraph z poprzedniego laboratorium, ale zwraca graf skierowany, czyli listę trójek (u,v,w) oznaczających krawędź z wierzchołka u do v o wadze w).zaimplementuj algorytm uaktualniania przepływu przy użyciu zadanej ścieżki powiększającej
W ramach laboratorium należy wykorzystać:
flowconnectivityW przykładowych grafach szukamy przepływów między pierwszym i ostatnim wierzchołkiem!