Maximum Flow — Sig‘imli yo‘naltirilgan tarmoqda manbadan nishonga yuboriladigan, sig‘im va oqim saqlanishi cheklovlariga bo‘ysunuvchi eng katta oqim. Bu tushuncha algoritmlar va ma’lumotlar tuzilmalarida natijani aniq ifodalash, murakkablikni tahlil qilish hamda muqobil yechimlarni solishtirish uchun ishlatiladi.
Asosiy qoidalar
Har yoydagi f(u,v) qiymat 0≤f(u,v)≤c(u,v) shartini bajaradi. Manba va nishondan boshqa tugunda kiruvchi oqim yig‘indisi chiquvchi oqim yig‘indisiga teng; maqsad manbadan chiqadigan jami qiymatni kattalashtirishdir.
Maximum Flowni tushunishda uning matematik ta’rifi bilan dasturiy ko‘rinishini ajratish muhim. Matematik model qaysi obyektlar va munosabatlar ruxsat etilishini belgilaydi; implementatsiya esa ularni massiv, ro‘yxat, xarita yoki boshqa tuzilma orqali saqlaydi. Bir xil model turli xotira va vaqt xususiyatlariga ega ko‘rinishlarda amalga oshirilishi mumkin. Shuning uchun “to‘g‘ri” tanlov faqat ta’rifga emas, bajariladigan so‘rovlar, kirish hajmi va yangilanish chastotasiga ham bog‘liq.
Yechish usullari
Ford–Fulkerson usuli residual tarmoqdagi oshiruvchi yo‘llarni takror topadi. Edmonds–Karp eng qisqa qirralar sonli yo‘lni BFS bilan tanlab O(VE²) chegara beradi; Dinic qatlamli graf va blocking flowdan foydalanib ko‘p amaliy tarmoqlarda tez ishlaydi.
Maximum Flowning foydasi faqat yakuniy javob bilan o‘lchanmaydi. U masalani qaysi qismlarga ajratish, qaysi invariantni saqlash va natijani qanday tekshirish mumkinligini ham ko‘rsatadi. Algoritm tanlanganda preprocessing, asosiy so‘rov, yangilash va natijani tiklash xarajatlari alohida baholanadi. Bir martalik hisoblash uchun ma’qul usul doimiy yangilanadigan xizmat uchun qimmat bo‘lishi mumkin.
Amaliy cheklovlar
Butun sig‘imlarda oshirish algoritmlari butun oqim topadi. Haqiqiy sonli sig‘imlar va noto‘g‘ri suzuvchi nuqta solishtirishlari tugashni murakkablashtirishi mumkin. Parallel yoylar, qaytish yoylari va juda katta yig‘indilar uchun ma’lumot turi ehtiyot tanlanadi.
Maximum Flow bilan ishlovchi dastur kirish shartlarini aniq tekshirishi kerak. Tugun yoki element identifikatorlari, yo‘nalish, vazn, tenglik va dublikat qoidalari oldindan kelishilmasa, nazariy jihatdan to‘g‘ri algoritm noto‘g‘ri model ustida ishlashi mumkin. Testlar minimal holat, bo‘sh kirish, uzilgan yoki takroriy ma’lumot, teng qiymatlar va eng yomon tartibni qamrab oladi. Katta kirishda natijaning o‘zi bilan birga xotira sarfi, bajarilish vaqti va I/O hajmi ham o‘lchanadi.
Hisoblash namunasi
s→a sig‘imi 3, s→b sig‘imi 2, a→t sig‘imi 2, b→t sig‘imi 3 va a→b sig‘imi 1 bo‘lsa, jami 5 birlik oqim yuborish mumkin. Manbadan chiquvchi sig‘imlar yig‘indisi ham 5 bo‘lgani uchun bundan katta qiymat imkonsiz.
Amaliy hujjatda Maximum Flow uchun kuzatiladigan kafolatlar alohida yoziladi: natijaning aniqligi, deterministikligi, murakkablik chegarasi va xato holatidagi xatti-harakat. Nazariy Big O bahosi kirish o‘sgandagi tendensiyani beradi, lekin kesh lokaliteti, disk murojaati va ma’lumot taqsimoti real tezlikka ta’sir qiladi. Shu bois kichik etalon implementatsiya bilan natijani solishtirish, so‘ng real ish yukida profil olish ishonchli tekshiruv usulidir.
+## Natijani tasdiqlash
Natijada har yoy sig‘im chegarasini, ichki tugunlar esa oqim saqlanishini bajarishi tekshiriladi. So‘ng residual grafda s dan t ga yo‘l qolmagani va oqim qiymati shu holatdan olingan cut sig‘imiga tengligi tasdiqlanadi. Maximum Flow implementatsiyasi uchun bu tekshiruvlar oddiy unit testdan kengroq bo‘lib, modelning asosiy matematik shartlarini nazorat qiladi. Etalon bilan farq topilsa, tasodifiy kirish minimal qarshi misolgacha kichraytiriladi; shu misol regressiya testiga qo‘shiladi.
Bog‘liq tushunchalar
maximum flow, minimum cut, residual graph, Ford–Fulkerson, Dinic algorithm, capacity