Mavzu: Maksimal o

Belgi qo'yish usuli
To'r yagona boshlang'ich uchga va yagona oxirgi uchga ega bo'lsin. Har bir yoyga uning dan ga yo'nalishdagi o'tkazish qobiliyati deb ataluvchi nomanfiy son mos qo'yilgan bo'lsin. Bunda bo'lishi shart emas. To'rda dan ga oqim deb, yoylarga mos qo'yilgan shunday nomanfiy sonlarning to'plamiga aytiladiki; ular uchun

bajarilsa, buyerda , son oqim kattaligi deyiladi.
Maksimal oqim tuzish algoritmini bayon qilamiz. Biror boshlang'ich, masalan, nol oqim olinadi. Yoylarning boshlang'ich o'tkazish qobiliyatlari berilgan. Aytaylik algoritmning bir qancha qadamidan keyin biror oqim yoylarning o'tkazish qobiliyatlarining joriy qiymatlari va v oqim kattaligining biror joriy qiymati olingan bo'lsin. U holda algoritm quyidagicha ishlaydi:
1⁰ Musbat q o'tkazish qobiliyatga ega dan ga yo'l tanlanadi, buyerda q -yo'lni hosil qiluvchi yoylar o'tkazish qobiliyatlarining eng kichigi. Buning uchun quyidagi algoritmdan foydalanish mumkin ( uch avval boshida belgilangan, lekin qo'rib chiqilmagan deb hisoblanadi, qolgan barcha uchlar esa belgilanmagan deb hisoblanadi):
1.a. Belgilangan, ammo ko'rib chiqilmagan ixtiyoriy uch tanlanadi.
1.b. shart bajariladigan barcha uchlarga belgilar quyiladi va ularni belgilangan deb hisoblanadi. uch ko'rib chiqilgan deb hisoblanadi. Agar bunda oxirgi uch belgilangan bo'lib qolsa, u holda belgilar bo'yicha dan gacha izlanayotgan yo'lni tiklash oson. Aks holda 1.a. qadamga o'tiladi. Agar buning imkoniyati bo'lmasa, u holda izlanayotgan yo'l mavjud bo'lmaydi.
2⁰. Aytaylik , , …, , topilgan yo'l bo'lsin. U holda bu yo'lga kiruvchi har bir yoy uchun

operatorlar bajariladi. Keyin 1⁰ qadamga o'tiladi. Agar musbat o'tkazish qobiliyatga ega bo'lgan yo'l mavjud bo'lmasa, u holda olingan oqim maksimal bo'ladi.