Maxsimal oqimlarni o’tkazish algoritmlarining qiyosiy tahlili

Maksimal oqimlar boyicha dastlabki algoritm 1956 yilda Ford-Falkerson[1] tomonidan taklif qilindi. Undan oldin masala chiziqli dasturlash metodlaridan foydalanib yechilgan va effektiv bo’lmagan. Ford, qirraning qoldiq o’tkazuvchanik qobiliyati tushunchasini kiritdi va uning o’tkazuvchanlik qobiliyati hamda undan o’tgan oqimning ayirmasiga tengligini aytiladi. Bu algoritmning ketma-ketligi quyidagicha: 1) s uchdan t uchga qoldiq o’tkazuvchanligi noldan katta bo’lgan yo’l topib olinadi. Agar bunday yo’l topilmasa, demak topilgan oqim maksimal hisoblanadi va algoritm o’z ishini tugatadi. Aks holda 2-qismga o’tiladi. 2) Topilgan yo’ldagi qirralarning qoldiq o’tkazuvchanlik qobiliyatlari orasidan minimali topiladi. Bu yo’ldagi qirralarning qoldiq o’tkazuvchanlik qobiliyatlaridan minimal qiymat tog’ri yo’nalish boyicha ayriladi, teskari yo’nalish boyicha qo’shiladi. Topilgan minimal qiymat o’tkazilgan oqimga qo’shiladi va 1-qismga o’tiladi. Algoritm iterativ davom etadi. Maksimal oqimning qiymatini F bilan belgilaylik. Iteratsiylar soni izlanayotgan maksimal oqim qiymatiga bo’gliq. Agar har iteratsiyada u birga oshadigan bo’lsa bu eng yomon holat hisoblanadi va iteratsiyalar soni F ga teng bo’ladi. Har bir iteratsiyada yo’lni topib olish uchun eng ko’pi bilan graf qirralar soni M ga teng amal bajariladi. Demak algoritmning umumiy ishlash vaqti O(F•M). Boshqa tamondan iteratsiyalar soni N•M dan oshmaydi va umumiy iteratsiyalar soni O(N•M2) ga teng bo’ladi.