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 ${\displaystyle 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 ${\displaystyle f}$ w sieci ${\displaystyle G=(V,E)}$ o źródle ${\displaystyle s}$ i ujściu ${\displaystyle t,}$ jego wartość jest zdefiniowana następująco:

${\displaystyle |f|=\sum _{u\in V}f(s,u).}$

Istnieje też uogólnienie tego problemu, w którym sieć ${\displaystyle G}$ zawiera wiele źródeł i ujść. Można jednak w prosty sposób sprowadzić je do przedstawionej wersji: Dla sieci ${\displaystyle G=(V,E)}$ zawierającej n źródeł ${\displaystyle s_{1},s_{2},\dots ,s_{n}}$ oraz m ujść ${\displaystyle t_{1},t_{2},\dots ,t_{m}}$ konstruujemy sieć ${\displaystyle G'=(V',E'),}$ gdzie:

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

${\displaystyle 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:

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

${\displaystyle c(t_{j},t)=\infty }$ dla każdego ${\displaystyle j=1,2,\dots ,m.}$

Innymi słowy, dodajemy do sieci ${\displaystyle G}$ wierzchołek ${\displaystyle s}$ połączony krawędziami o nieskończonej przepustowości ze wszystkimi źródłami oraz wierzchołek ${\displaystyle t}$ połączony krawędziami o nieskończonej przepustowości ze wszystkimi ujściami. Wierzchołek ${\displaystyle s}$ zwany jest superźródłem, zaś wierzchołek ${\displaystyle 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.