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'=(V',E'),$ gdzie:

$V'=V\cup \left\{s,t\right\},$

$E'=E\cup \left\{(s,s_{1}),(s,s_{2}),\dots ,(s,s_{n}),(t_{1},t),(t_{2},t),\dots ,(t_{m},t)\right\}.$

Ponadto:

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

$c(t_{j},t)=\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, ISBN 83-204-2879-3.