Maximum flow'ni topiş uçun Ford-Fulkerson algoritmi
Avvalgi maqolada maximum flow allaqaçon topilgan graph'ni körib ötdik. Endi flow'ni qanday hisoblaş haqida söz yuritamiz.
Mana öşa graph:
Maximum flow 28 ga teng.
Ammo qanday qilib 28 kelib çiqdi? Qanday qilib flow hisoblandi? Biz hisoblaşlarni qadamma-qadam körib ötamiz.
Ford-Fulkerson algoritmi
Tuşunarliroq bölişi uçun, graph'ni yönalişga ega quvurlar tarmoği deb olamiz.
Dastlabki holatida flow hisoblanmagan (quvurlar böş).
Max flow = 0
Har bir edge'ning (quvurning) ötkaziş qobilyati - capacity aniq berilgan. Biz bir vaqtning özida capacity'dan köp flow bera olmaymiz (capacity qiymatidan köp suv yubora olmaymiz).
Boşlanğiç nuqta - s dan maximum flow yuboriş uning edge capacity'lari yiğindisiga teng - 30. Biz quvurlar tizimining boşlanğiç nuqtasidan maksimum 30 şartli birlik (masalan, litr) suv yuborişimiz mumkin ekan: s -> 0 dan 10, s -> 1 dan 5, s -> 2 dan 15.
Lekin qolgan edge'lar capacity'si boşlanğiç nuqta - s nikidan past, demak biz maksimum 30 yubora olmaymiz. (Quvurlarni yorib yubormaslik uçun) avval s dan t gaça path'dagi edge capacity uçun çeklovlarni hisobga olişimiz kerak.
s dan t ga path'larni (quvurlarni) körib çiqamiz.
s -> 0 -> 3 -> t path'ning bir vaqtda maksimum ötkaziş qobilyati 9 ga teng, sababi 0 -> 3 capacity = 9. Uşbu path'ga max flow beramiz. (quvurlardan suv yuboramiz):
Max flow = 9
s -> 0 edge'ga yana 1 flow qöşişimiz (quvurdan yana 1 litr suv yuborişimiz mumkin). 1 qiymati 0 -> 4 -> t dan ketadi.
Max flow = 10
s -> 0 maksimum flow'ga erişdi. s dan keyingi edge'lar orqali t ga path qidiramiz.
s -> 1 -> 4 -> t path topildi. Uning maksimum ötkaziş qobilyati 5, sababi s -> 1 ning capacity'si 5 ga teng. Path edge'lariga 5 qöşib çiqamiz (quvurlardan 5 litr suv yuboramiz).
Max flow = 15
s -> 1 maksimum flow'ga erişdi. Bizda s -> 2 edge böş. s -> 2 orqali t ga path qidiramiz.
s -> 2 -> 5 -> t path topildi. Uning maksimum ötkaziş qobilyati 10 (quvurlardan 10 litr suv yuboramiz):
Max flow = 25
Biz quvurlarning ötkaziş qobilyatidan maksimum darajada foydalanyapmizmi? Hozirça yöq, s -> 2 edge yana 5 flow qöşişimiz mumkin. Bizda s dan t gaça yana böş path bormi? Ha, s -> 2 -> 5 -> 1 -> 4 -> t Uning maksimum ötkaziş qobilyati 3, sababi 1 -> 4 da 3 qöşişga böş joy bor.
Max flow = 28
Bizda yana böş path bormi? Yöq, barça path'lardagi kamida bitta edge capacity tölgan: s -> 0, 1 -> 4, 5 -> t. Biz s boşlanğiç nuqtadan t gaça ortiqça suv yubora olmaymiz.
Graph'ni tölgan capacity edge'lari böyiça ikkiga ajratsak, minimum cut'ni ham topgan bölamiz:
Biz maximum flow'ni topiş barobarida, maxflow = mincut teoremasini ham isbotladik.
Natijani sahifaning yuqorisidagi tayyor graph bilan taqqoslaganimizda t ga inflow farq qilyapti, {8, 10, 10} ga {9, 9, 10}. Bu qaysi (s t) path'lariga flow beriş tartibiga boğliq.
Şuningdek, biz reverse flow, flow'ni kamaytirişga ham duç kelmadik. Agar s -> 0 -> 4 -> t path'dan boşlaganimizda, keyinçalik biz 0 -> 4 ni 10/15 dan 2/15 ga kamaytirgan bölardik (erinmasangiz, özingiz şu yöl bilan hisoblab köring).