1 Sieci przepływowe: algorytmy i ich zastosowania.

2 Sieć przepływowa Przez sieć przepływową (ang. flow network) będziemy rozumieli spójny graf skierowany G=(V,E) (ang. connected directed graph lub conected digraph), w którego krawędziach odbywa się przepływ (ang. flow) jakiegoś czynnika. W sieci przepływowej wyróżnia się jeden wierzchołek s, z którego wychodzą przepływy - jest to tzw. źródło (ang. source), oraz jeden wierzchołek t, do którego zbiegają się przepływy - jest to tzw. ujście (ang. sink).

3 Przepustowość Z każdą krawędzią grafu (w terminologii sieci przepływowych krawędzie nazywamy kanałami - ang. chanels) skojarzony jest parametr określający tzw. przepustowość (ang.capacity), która oznacza maksymalną ilość czynnika mogącego przez tę krawędź przepływać. Przepustowość jest nieujemną funkcją rzeczywistą oznaczaną zwykle przez c(u,v), gdzie u i v ∈ V. Jeśli wierzchołki u i v są połączone kanałem, czyli (u,v) ∈ E, to przepustowość tego kanału spełnia warunek c(u,v) ≥ 0. Jeśli wierzchołki u i v nie są połączone kanałem, czyli(u,v) ∉ E, to c(u,v) = 0.

4 Zastosowanie Sieci przepływowanie mają zastosowanie m.in. w algorytmach: Forda-Fulkersona Dinica 3 hindusów

5 Algorytm Forda-FulkersonaMetoda 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 Dinica. 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.

6 Zapis w pseudokodzie Ford-Fulkerson-Method(G,s,t) inicjowanie f na 0 while istnieje ścieżka powiększająca p do powiększ przepływ f wzdłuż p return f

7 Algorytm Dinica Kolejny algorytm rozwiązujący problem maksymalnego przepływu opiera się na pojęciu przepływu blokującego. Def. Przepływem blokującym w sieci rezydualnej G(f) nazywamy taki przepływ b, który nasyca co najmniej jedną krawędź w każdej najkrótszej ścieżce z s do t w sieci G(b).

8 Zapis w pseudokodzie f = 0; while („istnieje cieka od s do t w G(f)”) { „znajdź przepływ blokujący b w G(f)”; „powiększ przepływ f do b”; „wyznacz sieć rezydualną G(b)”; }

9 Algorytm 3 Hindusów W algorytmie tym użyte zostało pojęcia przepustowości wierzchołka w sieci. Def. Przepustowości wierzchołka v w sieci G nazywamy wartość mniejszą z dwóch wartości: i Przepustowość wierzchołka v oznacza się przez c(v). W algorytmie trzech Hindusów, w każdym wykonaniu głównej pętli algorytmu, nasycany jest jeden wierzchołek sieci (tj. jego przepustowo spada do zera), poprzez przesłanie z niego przepływu do przodu i w pewnym sensie do tyłu. W czasie wykonywania pętli funkcja f nie spełnia warunku zachowania przepływu, jednak pod koniec ten warunek zostanie przywrócony.

10 Zapis w pseudokodzie algorytm MKM; (Malhotra, Kumar i Maheshwari) b = 0 „skonstruuj sieć warstwową G’(f)”; while (E’f ≠ Ø) { „znajdź wierzchołek v o najmniejszej wartości c(v)”; „prześlij c(v) jednostek przepływu krawędziami wychodzącymi z v”; „prześlij c(v) jednostek przepływu krawędziami wchodzącymi do v”; „usuń krawędzie nasycone wychodzące z v lub docierające do v”; for (i = ds(v)+1; i<=n-1;i++) for wƐ {jƐV: ds(j)=i} { forward(w); „popraw przepustowość w”; „usuń krawędzie nasycone wychodzące z w”; }; for (i = ds(v)-1; i>=1;i--) for wƐ{jƐV: ds(j)=i} { back(w); „usuń krawędzie nasycone docierające do w”; }; „usuń v z grafu”; }