Kantorning diagonal usuli. Oqim miqdori tushunchasi. Yig’indi va qatorlar algoritmlarining tahlili

Misol uchun



Kesimlarga misollar— S₁={(a,y), (a,x), (a,z)}, S₂={(a,z), (x,z), (y,z), (y,b)}, S₃={(y,b), (z,b)}.

Ushbu kesmalarning o'tkazuvchanligini aniqlang

Теорема (Форд и Фалкерсон).

s dan t gacha bo'lgan har bir oqim qiymati s va t ni ajratadigan

minimal qismning o'tkazuvchanligidan oshmaydi va shu qiymatga yetadigan oqim mavjud.

W(f) = f(A, V \A) – f(V \A, A)  f(A, V \A) =

Maksimal oqimni qanday aniqlash mumkin

Agar manbadan keladigan oqim manbani tark etadigan qovurg'alar orqali tushadigan narsalarning yig'indisiga teng bo'lsa yoki drenajga oqadigan oqim drenajga kiradigan qovurg'alar orqali o'tadigan narsalarning yig'indisiga teng bo'lsa, u holda oqim maksimal bo'ladi. Shu bilan birga, oqim maksimal darajada bo'lishi mumkin va ushbu belgilarning hech birini qondirmasdan.