DSC00317 (5)

Przykład takiej sieci z przepływem jest przedstawiony na rys. 11.!, gdzie wartości h(x_ty) przedstawiono w prostokątach. Przepływ/* nazywamy maksymalnym, dla danej sieci S_t gdy

v{f*) «■ max t>(/) f

gdzie F jest zbiorem wszystkich, możliwych przepływów dla danej sieci. Przy danym przepływie/łuki (x,y) sieci dzielimy na trzy rodzaje:

1)    łtlki nasycone: f{x_%y) **h(x,y)\

2)    łuki nienasycone: 0</(*,y)<h(x_ty);

3)    łuki' wyschnięte: /(*, y) m 0.

Zauważmy, że dla przyjętej, standardowej sieci, w której dolne ograniczenie, dla wartości przepływu na łuku, jest zerowe, istnieje zawsze co najmniej jedna funkcja/spełniająca warunki przepływu. Jest nią funkcja tożsamościo-wo równa zeru. -Zatem F^0. Gdyby natomiast dolne ograniczenie na przepływ, które oznaczymy l(x, y) nie było zerowe, to dla danej sieci zbiór możliwych przepływów F mógłby być pusty.

Przekrojem rozdzlelejącym (źródło i odpływ) nazywamy podzbiór P zbioru U łuków sieci, określony następująco

? = {<x,y>eC/: xeW_lt ye\V₂}

gdzie W_x uW₂= Jf, W_lnW₂=0, seW_u teW₂.

Zauważmy, że po usunięciu łuków należących do P nie istnieje ani jedna droga z W_x do 1V₂, a tym samym z s do t. W ten sposób możemy utożsamić przekrój rozdzielający P z odpowiednią parą podzbiorów

wk

Na przykład, przekrojem rozdzielającym sieci z rys. 11.1 jest P**

Przepustowością przekroju rozdzielającego nazywamy liczbę H(P)~ l h(x_ty)

Oznaczmy przez P zbiór wszystkich przekrojów rozdzielających danej sieci.

Minimalnym przekrojem rozdzielającym P* nazywamy taki przekrój, dla którego

H (?*)« min H (P)

r«p

Twierdzhnib 11.1. Wartość maksymalnego przepływu v(f*) jest równa przepustowości minimalnego przekroju rozdzielającego H(P*).