Problem maksymalnego przepływu

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Problem maksymalnego przepływu to zagadnienie często spotykane w informatyce. Polega ono na znalezieniu dla danej sieci przepływowej takiego przepływu , 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 w sieci o źródle i ujściu , jego wartość jest zdefiniowana następująco:

Istnieje też uogólnienie tego problemu, w którym sieć zawiera wiele źródeł i ujść. Można jednak w prosty sposób sprowadzić je do przedstawionej wersji: Dla sieci zawierającej n źródeł oraz m ujść konstruujemy sieć , gdzie:


Ponadto:

dla każdego
dla każdego

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

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

Bibliografia[edytuj]