Metoda Forda-Fulkersona

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Metoda Forda-Fulkersona jest stosowana do znajdowania maksymalnego przepływu w sieci przepływowej. Stanowi podstawę wielu algorytmów, między innymi algorytmu Edmondsa-Karpa czy algorytmu Dynica

Zasadę jej działania można streścić w następujący sposób: Należy zwiększać przepływ wzdłuż dowolnej ścieżki ze źródła do ujścia, dopóki jest to możliwe.

Pojęcia[edytuj]

Dla dowolnej sieci przepływowej o źródle i ujściu , w której dowolna krawędź należąca do zbioru ma przepustowość oraz przepływu definiuje się następujące pojęcia:

Sieć residualna[edytuj]

Siecią residualną dla sieci przepływowej nazywamy sieć , gdzie jest zdefiniowane następująco:

gdzie oznacza tzw. przepustowość residualną dla krawędzi . Ta natomiast jest dana wzorem:

Krawędzie należące do nazywa się krawędziami residualnymi.

Bardziej intuicyjnie, przepustowość residualna dla pewnej krawędzi oznacza, o ile można zwiększyć przepływ przez nią, tak jednak, aby nie przekroczył on jej przepustowości. Do sieci residualnej natomiast należą te krawędzie, przez które przepływ można zwiększyć.

Należy zwrócić uwagę, że może zachodzić

.

Ma to miejsce w przypadku, gdy . W szczególności, do mogą należeć krawędzie nienależące do .

Ścieżka powiększająca[edytuj]

Ścieżką powiększającą dla sieci nazywamy dowolną ścieżkę z do w sieci residualnej dla . Przepustowość residualną dowolnej ścieżki powiększającej dla sieci określamy wzorem:

Jest to wartość, o jaką maksymalnie można zwiększyć przepływ przez wszystkie krawędzie należące do ścieżki .

Algorytm[edytuj]

Poniżej przedstawiono zapis metody Forda-Fulkersona w pseudokodzie:

while istnieje pewna ścieżka powiększająca  do
    for each  do
        
        

Złożoność czasowa[edytuj]

Złożoność czasowa metody Forda-Fulkersona silnie zależy od sposobu wyszukiwania ścieżki powiększającej . Można jednak znaleźć jej górne ograniczenie. Zauważmy, że za każdym razem, gdy taka ścieżka zostanie znaleziona, przepływ ze źródła do ujścia zostanie zwiększony co najmniej o 1. Niech oznacza maksymalny przepływ w sieci . Wtedy pętla while zostanie wykonana w co najwyżej iteracjach. Ponieważ na ścieżce może leżeć co najwyżej krawędzi, dla każdej takiej ścieżki pętla for each zostanie zakończona po nie więcej, niż przebiegach. Ponieważ również wyszukiwanie ścieżki powiększającej można zrealizować w czasie , złożoność czasowa metody Forda-Fulkersona, to .

W rzeczywistości, jedna z popularniejszych implementacji tej metody, algorytm Edmondsa-Karpa ma złożoność .

Przykład[edytuj]

Poniższy przykład przedstawia początkowe kroki metody Forda-Fulkersona w sieci z 4 wierzchołkami, źródłem A oraz ujściem D. Ścieżki powiększające są wyszukiwane za pomocą przeszukiwania w głąb, w którym sąsiadujące wierzchołki są odwiedzane w kolejności alfabetycznej. Jest to najgorszy możliwy przypadek, gdyż w każdej iteracji pętli głównej procedury przepływ jest powiększany tylko o 1.


Ścieżka Przepustowość Otrzymany przepływ
Sytuacja początkowa Ff-flow 0.png



Ff-flow 1.png



Ff-flow 2.png
Sytuacja końcowa Ff-flow f.png

Warto zwrócić uwagę, w jaki sposób przepływ "wraca" z wierzchołka C do B po wykorzystaniu ścieżki A,C,B,D.

Bibliografia[edytuj]