Sieć przepływowa

Sieć przepływowa

Sieć przepływowa G(V,E) to graf skierowany, w którym każda krawędź (u,v) z zestawu krawędzi E ma nieujemną przepustowość c(u,v) ≥ 0. W sieci wyróżniamy dwa kluczowe wierzchołki: źródło s oraz ujście t.

Pojęcia podstawowe

Przepływ w sieci G definiuje się jako funkcję f: V × V → R, która spełnia następujące warunki:

• Warunek przepustowości: dla każdej krawędzi (u,v) ∈ E zachodzi f(u,v) ≤ c(u,v).
• Warunek skośnej symetryczności: dla każdej krawędzi (u,v) ∈ E zachodzi f(u,v) = -f(v,u).
• Warunek zachowania przepływu: dla każdego wierzchołka u ∈ V {s,t} zachodzi suma przepływów do i z wierzchołka u: ∑(v∈V) f(v,u) = ∑(v∈V) f(u,v).

Przepływ netto definiuje wartość f(u,v), która wskazuje na ilość przepływu z wierzchołka u do wierzchołka v.

Zagadnienia związane z sieciami przepływowymi

• Problem maksymalnego przepływu: Kluczowe zagadnienie, które polega na maksymalizacji całkowitego przepływu z wierzchołka źródłowego s do ujścia t.

Sieci przepływowe są istotnym obszarem badań w teorii grafów i mają zastosowanie w różnych dziedzinach, takich jak logistyka, telekomunikacja czy zarządzanie zasobami.