Maximum flow’ni topish jarayonida, ba’zida yechimga erishish uchun allaqachon berilgan flow’ni kamaytirish hisobiga boshqa (parallel) edge’da flow’ni oshiriladi. Inson ko’zi bilan ko’rib, qaysi flow’ni kamaytirish, qaysi flow’ni oshirishni o’zi aniqlab olishi mumkin, lekin kodda nima qilishni qanday ifodalaymiz?
Nima haqida aytayotganim haqida batafsil tushuntiraman. Demak, oldingi mavzudagi kabi, bizdagi boshlang’ich graph:
O’tgan mavzuda biz flow hisoblashni s -> 0 -> 3 -> t dan boshlagandik. Bu safar s -> 0 -> 4 -> t ga birinchi bo’lib flow qiymatini beramiz:
s -> 0 edge to’ldi (flow = capacity).
Keyingi qadam s -> 0 -> 2 -> 5 -> t, path uchun max flow 10 ga teng.
t ga inflow uchun bo’sh edge faqat 3 -> t qoldi. Lekin 3 vertax’ni o’z ichiga olgan s -> 0 -> 3 -> t path’da s -> 0 to’lgan, path uchun 10 flow 0 -> 4 edge orqali ketyapti. Biz 0 -> 4 edge’dan 9 flow’ni orqaga qaytarib, uni 0 -> 3 edge’dan yuborsak bo’larmikin:
Flow’ni ikkiga bo’lganimizning yaxshi tarafi – 4 -> t edge’da 9 flow uchun joy ochildi, avval 10/10 edi, hozir 1/10. Biz bo’shagan edge’dan unumli foydalanishga urinamiz:
s -> 1 -> 4 -> t path’ga 5 flow beramiz:
s -> 2 -> 5 -> 1 -> 4 -> t path’ga 3 flow beramiz:
Maximum flow 28 ga teng chiqdi.
* * *
Biz flow’ni orqaga qaytarib boshqa edge’ga bo’lishni o’zimiz fikrlab amalga oshirdik. Kodga esa ishlashi uchun flow’ni bo’lish, orqaga qaytarish kabi fikrlashni «chaynab» solib qo’yishimiz kerak. Buning uchun bizga o’zgarishlarni qayd etib borishga yana bir graph – residual graph zarur bo’ladi.
Umumiy holda, Ford-Fulkerson algoritmi ikki konseptga asoslanadi.
- Residual graph (yoki residual network)
- Augmenting path
Residual graph
Residual graph (yoki residual network) – original graph’dagi kabi vertex’larga ega va vertex’lari bitta yoki ikkita edge bilan bog’langan graph. U graph’da qo’shimcha ehtimoliy flow’larni (addditional flow) aniqlab beradi.
Har bir edge uchun qo’shimcha flow’larni quyidagicha hisoblaymiz:
Additional flow = edge capacity — edge flow
Residual graph’ni hosil qilish uchun original graph’ni olib, har bir edge’ning capacity’siga edge uchun additional flow qiymatini beramiz. Agar original graph’dagi edge’da flow qiymati 0 dan katta bo’lsa, residual graph’da mos holda ikki vertex uchun reverse edge qo’shib chiqamiz.
Original (bo’sh) graph 
Residual graph
s -> 0 -> 4 -> t path’ga flow bersak:
Reverse edge’ni yana backward edge ham deyiladi.
Augmenting path
Augmenting path – residual graph’da s dan t gacha boradigan ehtimoliy path. Masalan yuqoridagi misolda augmenting path – s -> 2 -> 5 -> t bo’lishi mumkin, sababi ushbu path original graph’da hali bo’sh.
Maximum flow topilgan graph’da augmenting path bo’lmaydi.
Algoritmning ishlash tartibi
- Barcha edge’larga 0 qiymat bilan boshlaydi
- s dan t gacha edge’larga flow berib augmenting path borligini tekshiradi.
- Agar bor bo’lsa flow’ni qaytaradi