Sieci przepływowe

https://en.wikipedia.org/wiki/Flow_network

WPROWADZENIE

Grafy ważone mogą być wykorzystywane do badania przepływu pewnej substancji pomiędzy ustalonymi punktami. Może to być przepływ cieczy, towarów, pojazdów. Formalnie definiuje się sieć przepływową (ang. flow network) jako graf skierowany o nieujemnych wagach (przepustowościach) krawędzi. Krawędzie przeciwne są zabronione. Sieć zawiera dwa wyróżnione wierzchołki: źródło (ang. source) i ujście (ang. sink). źródło ma jedynie krawędzie wychodzące, a ujście jedynie krawędzie wchodzące. W pozostałych wierzchołkach zachodzi zachowanie przepływu, czyli szybkość wpływania musi być równa szybkości wypływania.

Cormen przyjmuje założenie, że każdy wierzchołek sieci przepływowej leży na pewnej ścieżce od źródła do ujścia.

MAKSYMALNY PRZEPŁYW

Najprostszym problemem pojawiającym się w sieciach przepływowych jest problem maksymalnego przepływu. Wybrane algorytmy rozwiązujące ten problem [Cormen]:

• Algorytm Forda-Fulkersona, wykorzystuje sieć residualną i ścieżki powiększające.
• Algorytm Edmondsa-Karpa, działa w czasie O(V*E^2).
• Algorytmy typu "prześlij i przemianuj", działają w czasie O(V^2*E).
• Algorytm "przemianuj i przesuń na początek", działa w czasie O(V^3).