Problem maksymalnego przepływu

Problem maksymalnego przepływu – 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,\dots ,s_n$ oraz m ujść $t_1,t_2,\dots ,t_m$ konstruujemy sieć $G^{\prime }=(V^{\prime },E^{\prime }),$ gdzie:

$V^{\prime }=V\cup \{s,t\},$

$E^{\prime }=E\cup \{(s,s_1),(s,s_2),\dots ,(s,s_n),(t_1,t),(t_2,t),\dots ,(t_m,t)\}.$

Ponadto:

$c(s,s_i)=\mathrm{\infty }$ dla każdego $i=1,2,\dots ,n,$

$c(t_j,t)=\mathrm{\infty }$ dla każdego $j=1,2,\dots ,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

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, WNT, 2004, Szablon:ISBN.