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 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.