Identifikatsiyalash

Ford-Falkerson algoritmiga misol.
Maksimal oqim qiymati minimal qirqim qiymatiga teng boʻlishining isbotini aniq misolda koʻrish mumkin. Berilgan tarmoq uchun maksimal oqim va minimal qirqimni Ford – Falkerson (belgilar qoʻyish) algoritmi orqali yechamiz. Bizga transport tarmogʻi uchun maksimal oqim va minimal qirqimni topish quyidagi graf koʻrinishida berilgan boʻlsin.


2.3.3-rasm. Transport tarmogʻi.
dan gacha boʻlgan oqimda – kirish, – chiqish hisoblanadi. Oqimni deb olamiz. dan gacha boʻlgan oqimdagi barcha yoʻllarni ketma-ket ravishda qarab chiqamiz. Oqimdagi yoʻllarni qarab chiqish jarayonida shunga e’tibor berish kerakki, oʻchirilgan yoydan qayta yurish mumkin emas.
1 - QADAM. Boshlangʻich oqim qiymatini beramiz va belgilashni boshlaymiz. Boshlangʻich oqim 0 deb olinadi. tugundan boshlab gacha boʻlgan ixtiyoriy oqimni tanlaymiz, masalan: oqimni qaraymiz. Bu oqimning
o ʻtkazish qobiliyati uning tarkibiga kiruvchi barcha yoylar orasidagi minimaliga, ya’ni 6 ga tengdir. Shu oqimdagi yoylarning oʻtkazish qobiliyatini 6 ga kamaytiramiz. Toʻyingan yoyni oʻchiramiz. Tugunlarni qaytadan belgilab chiqamiz.

2-QADAM. tugundan boshlangan navbatdagi ixtiyoriy oqimni qaraymiz, masalan: . Bu oqimning oʻtkazish qobiliyati uning tarkibiga kiruvchi barcha yoylar orasidagi minimaliga, ya’ni 24 ga tengdir. Shu oqimdagi yoylarning oʻtkazish qobiliyatini 24 ga kamaytiramiz. Toʻyingan yoyni oʻchiramiz. Tugunlarni qaytadan belgilab chiqamiz.




3-QADAM. tugundan boshlangan navbatdagi ixtiyoriy oqimni qaraymiz, masalan: . Bu oqimning oʻtkazish qobiliyati uning tarkibiga kiruvchi barcha yoylar orasidagi minimaliga, ya’ni 57 ga tengdir. Shu oqimdagi yoylarning oʻtkazish qobiliyatini 57 ga kamaytiramiz. Toʻyingan yoyni oʻchiramiz. Tugunlarni qaytadan belgilab chiqamiz.