Edmonds-Karp Algorithm — Maksimal oqimni residual grafdagi eng kam qirrali oshiruvchi yo‘lni BFS bilan takror topish orqali hisoblaydigan Ford–Fulkerson varianti. Uning to‘g‘ri qo‘llanishi ishlash mexanizmi, kirish shartlari va natija kafolatini birgalikda tushunishni talab qiladi.
Algoritmik tuzilish
Har iteratsiyada BFS s dan t gacha residual sig‘imi musbat yo‘l topadi. Yo‘ldagi eng kichik residual sig‘im bottleneck bo‘lib, oqim shu miqdorga oshiriladi; oldinga va orqaga residual qirralar birga yangilanadi.
Edmonds-Karp Algorithmni dasturda qo‘llashdan oldin kirish modeli aniq belgilanadi: ma’lumot turi, indekslash, graf yo‘nalishi, ehtimollik taqsimoti yoki arifmetik aniqlik haqidagi farazlar algoritm kafolatining bir qismidir. Nazariy shart bajarilmasa, tez va xatosiz ishlagan kod ham mazmunan noto‘g‘ri javob berishi mumkin. Shu sabab API kirishni tekshiradi yoki cheklovni hujjatida ochiq bildiradi.
Hisoblash xususiyatlari
Vaqt O(VE²), xotira O(V+E). Chegara sig‘im qiymatlariga bog‘liq emas, chunki kritik qirraning BFS masofasi monoton o‘sadi. Zich yoki juda katta grafda Dinic ko‘pincha tezroq.
Edmonds-Karp Algorithm samaradorligi faqat Big O bilan baholanmaydi. Real natijaga graf zichligi, alphabet hajmi, cache lokaliteti, priority queue amallari, katta son arifmetikasi va tasodifiy generator xarajati ta’sir qilishi mumkin. Benchmark odatiy kirish bilan birga noqulay taqsimot, maksimal o‘lcham va ko‘p dublikatli holatlarni ham qamrab oladi. Natijaning to‘g‘riligi esa alohida etalon yoki invariant bilan tasdiqlanadi.
Amaliy vazifalar
Tarmoq sig‘imi, bipartite matchingning sodda reduksiyasi, taqsimot va cut masalalarida deterministik polynomial yechim beradi.
Edmonds-Karp Algorithm tanlanganda preprocessing narxi, bitta operatsiya yoki so‘rov vaqti, xotira sarfi va natijaning aniqligi birga baholanadi. Bir martalik kichik kirishda sodda usul afzal bo‘lishi mumkin; ko‘p takrorlanadigan yoki katta ma’lumotda esa tayyorlov xarajati keyingi amallar hisobiga qoplanadi. Nazariy ustunlik real ish yukida profil orqali tasdiqlanadi.
Nazorat mezoni
Yakuniy oqim sig‘im va conservation shartlarini bajaradi; residual grafda s–t yo‘l qolmasligi va oqim min-cut sig‘imiga tengligi tekshiriladi.
Edmonds-Karp Algorithm implementatsiyasida xato holati ham interfeysning bir qismidir. Bo‘sh kirish, mavjud bo‘lmagan yechim, overflow, yetarli bo‘lmagan aniqlik yoki noto‘g‘ri parametr uchun qaytariladigan qiymat oldindan belgilanadi. Diagnostika foydali bo‘lishi uchun versiya va asosiy parametrlar qayd etiladi, lekin katta yoki maxfiy kirish to‘liq jurnalga chiqarilmaydi. Property-based test tasodifiy kichik misollarda matematik xususiyatlarni muntazam tekshiradi.
+## Muhim xususiyat
Edmonds–Karpda bir qirra qayta kritik bo‘lishidan oldin uning uchlari orasidagi BFS darajasi kamida ikkiga o‘sadi. Shu monotonlik oshirishlar sonini O(VE) bilan cheklaydi va umumiy O(VE²) vaqt isbotini beradi.
Edmonds-Karp Algorithm ishlab chiqarish muhitida qo‘llanganda natija bilan birga algoritm versiyasi, asosiy parametrlar va kirishning muhim xususiyatlari qayd etiladi. Kuzatuv ko‘rsatkichlari mavzuga mos tanlanadi: DFS chuqurligi, kengaytirilgan tugunlar, hash collisionlari, qabul qilish ulushi, sample variance, interval aniqligi yoki kodlangan baytlar soni shular jumlasidandir. Chegara qiymati oshsa, avval correctness invariantlari tekshiriladi, keyin profiling orqali qimmat bosqich aniqlanadi. Bu yondashuv nazariy kafolat bilan amaldagi xatti-harakat orasidagi farqni ko‘rsatadi.
Bog‘liq tushunchalar
Edmonds–Karp algorithm, maximum flow, breadth-first search, residual graph, augmenting path, minimum cut