Пример
Kesimlarga misollar— множества S1={(a,y), (a,x), (a,z)}, S2={(a,z), (x,z), (y,z), (y,b)}, S3={(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.
Isbot. P (A) minimal kesma bo'lsin. Lemma 1 tomonidan ixtiyoriy oqim f uchun bizda bor
W(f) = f(A, V \A) – f(V \A, A) f(A, V \A) =
Maksimal oqimni qanday aniqlash mumkin
Shuni ta'kidlash kerakki, 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.
Do'stlaringiz bilan baham: |