Problem maksymalnego przepływu

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Problem maksymalnego przepływu to zagadnienie często spotykane w informatyce. Polega ono na znalezieniu dla danej sieci przepływowej takiego przepływu f\,, którego wartość jest maksymalna, gdzie wartość przepływu jest zdefiniowana jako łączny przepływ opuszczający źródło. Bardziej formalnie, dla danego przepływu f\, w sieci G = (V, E) \, o źródle s\, i ujściu t\,, jego wartość jest zdefiniowana następująco:

|f| = \sum_{u \in V} f(s, u)

Istnieje też uogólnienie tego problemu, w którym sieć G\, zawiera wiele źródeł i ujść. Można jednak w prosty sposób sprowadzić je do przedstawionej wersji: Dla sieci G = (V, E)\, zawierającej n źródeł s_1, s_2, ..., s_n\, oraz m ujść t_1, t_2, ..., t_m\, konstruujemy sieć G' = (V', E')\, , gdzie:

V' =  V \cup \left \{s, t\right\}
E' = E \cup \left \{ (s, s_1), (s, s_2), ..., (s, s_n), (t_1, t), (t_2, t), ..., (t_m, t)\right\}

Ponadto:

c(s, s_i) = \infty\, dla każdego i = 1, 2, ..., n\,
c(t_j, t) = \infty\, dla każdego j = 1, 2, ..., m\,

Innymi słowy, dodajemy do sieci G\, wierzchołek s\, połączony krawędziami o nieskończonej przepustowości ze wszystkimi źródłami oraz wierzchołek t\, połączony krawędziami o nieskończonej przepustowości ze wszystkimi ujściami. Wierzchołek s\, zwany jest superźródłem, zaś wierzchołek t\, - superujściem.

Maksymalny przepływ można znaleźć m. in. za pomocą algorytmu Edmondsa-Karpa opartego na metodzie Forda-Fulkersona.

Bibliografia[edytuj | edytuj kod]