DSA maksimal oqim

---

Maksimal oqim masalasi

Maksimal oqim masalasi yo‘naltirilgan graf orqali grafning bir joyidan boshqa joyiga o‘tadigan maksimal oqimni topishdan iborat.

Aniqroq aytganda, oqim \(s\) manba cho‘qqisidan chiqadi va \(t\) quyilish cho‘qqisiga borib tushadi, grafdagi har bir qirra esa oqim va sig‘im bilan aniqlanadi; bunda sig‘im — shu qirradan o‘tishi mumkin bo‘lgan maksimal oqim.

Maksimal oqimni topish juda foydali bo‘lishi mumkin:

• Kelajakda tirbandliklarning oldini olish maqsadida shahardagi yo‘llarni rejalashtirish uchun.
• Suv quvuri, elektr simi yoki tarmoq kabelini olib tashlash qanday ta’sir qilishini baholash uchun.
• Masalan, transport harakati, ma’lumotlar trafigi yoki suv oqimini oshirish maqsadida oqim tarmog‘ining qayerida sig‘imni kengaytirish eng yuqori maksimal oqimga olib kelishini aniqlash uchun.

---

---

Terminologiya va tushunchalar

Orqali oqim o‘tadigan yo‘naltirilgan grafni ko‘pincha oqim tarmog‘i deb ataymiz.

Qirraning sig‘imi \(c\) shu qirra orqali qancha oqim o‘tishiga ruxsat berilganini bildiradi.

Har bir qirrada, shuningdek, shu qirradagi joriy oqim qanchaligini bildiruvchi oqim qiymati ham bor.

Yuqoridagi rasmdagi \( v_1 \) cho‘qqisidan \( v_2 \) cho‘qqisiga boradigan \( v_1 \rightarrow v_2 \) qirrasining oqimi va sig‘imi 0/7 ko‘rinishida ifodalangan, ya’ni oqim 0ga, sig‘im esa 7ga teng. Demak, bu qirradagi oqimni 7 gacha oshirish mumkin, lekin undan ortiq emas.

Eng oddiy ko‘rinishida oqim tarmog‘ida oqim chiqadigan bitta manba cho‘qqisi \(s\) va oqim kiradigan bitta quyilish cho‘qqisi \(t\) bo‘ladi. Boshqa cho‘qqilar orqali esa oqim shunchaki o‘tib ketadi.

\(s\) va \(t\) dan tashqari barcha cho‘qqilar uchun oqimning saqlanishi amal qiladi, ya’ni cho‘qqiga qancha oqim kirsa, undan xuddi shuncha oqim chiqishi ham kerak.

Maksimal oqim Ford-Fulkerson yoki Edmonds-Karp kabi algoritmlar yordamida topiladi: ular oqim tarmog‘idagi qirralar orqali tobora ko‘proq oqim yuboradi va qirralarning sig‘imi boshqa oqim yuborishga imkon bermay qolguncha shunday davom etadi. Orqali yana oqim yuborish mumkin bo‘lgan bunday yo‘l kengaytiruvchi yo‘l deb ataladi.

Ford-Fulkerson va Edmonds-Karp algoritmlari qoldiq tarmoq deb ataladigan tuzilma yordamida amalga oshiriladi. Bu keyingi sahifalarda batafsilroq tushuntiriladi.

Qoldiq tarmoq har bir qirradagi qoldiq sig‘imlar asosida tuziladi; qirraning qoldiq sig‘imi shu qirradagi sig‘imdan oqim ayirilganiga teng. Shunday qilib, qirradagi oqim oshirilganda qoldiq sig‘im xuddi shuncha kamayadi.

Qoldiq tarmoqdagi har bir qirra uchun asl qirraga qarama-qarshi yo‘nalgan teskari qirra ham mavjud. Teskari qirraning qoldiq sig‘imi asl qirradagi oqimga teng. Teskari qirralar maksimal oqim algoritmlarining bir qismi sifatida qirra bo‘ylab oqimni orqaga yuborish uchun muhim.

Quyidagi rasmda ushbu sahifa yuqorisidagi simulyatsiyadagi grafning teskari qirralari ko‘rsatilgan. Har bir teskari qirra qarama-qarshi yo‘nalishga qaragan va boshida grafda oqim bo‘lmagani uchun teskari qirralarning qoldiq sig‘imlari 0 ga teng.

Qoldiq tarmoq va teskari qirra kabi ba’zi tushunchalarni tushunish qiyin bo‘lishi mumkin. Shu sababli bu tushunchalar keyingi ikki sahifada batafsilroq va misollar bilan tushuntiriladi.

Maksimal oqim topilganda, oqim tarmog‘i orqali jami qancha oqim yuborish mumkinligini bildiruvchi qiymatga ega bo‘lamiz.

---

Bir nechta manba va quyilish cho‘qqilari

Ford-Fulkerson va Edmonds-Karp algoritmlari maksimal oqimni topa olishi uchun bitta manba cho‘qqisi va bitta quyilish cho‘qqisi bo‘lishini kutadi.

Agar grafda bittadan ortiq manba cho‘qqisi yoki bittadan ortiq quyilish cho‘qqisi bo‘lsa, maksimal oqimni topish uchun grafni o‘zgartirish kerak.

Grafda Ford-Fulkerson yoki Edmonds-Karp algoritmini ishga tushira olishingiz uchun uni o‘zgartirishda, agar bir nechta manba cho‘qqisi bo‘lsa, qo‘shimcha super-manba cho‘qqisini, bir nechta quyilish cho‘qqisi bo‘lsa, qo‘shimcha super-quyilish cho‘qqisini yarating.

Super-manba cho‘qqisidan asl manba cho‘qqilariga cheksiz sig‘imli qirralar yarating. Xuddi shunday, quyilish cho‘qqilaridan super-quyilish cho‘qqisiga ham cheksiz sig‘imli qirralar yarating.

Quyidagi rasmda ikkita manba — \(s_1\) va \(s_2\) hamda uchta quyilish — \(t_1\), \(t_2\) va \(t_3\) bo‘lgan shunday graf ko‘rsatilgan.

Bu grafda Ford-Fulkerson yoki Edmonds-Karp algoritmini ishga tushirish uchun asl manba tugunlariga cheksiz sig‘imli qirralar boradigan \(S\) super-manba va asl quyilishlardan unga cheksiz sig‘imli qirralar keladigan \(T\) super-quyilish yaratiladi.

Endi Ford-Fulkerson yoki Edmonds-Karp algoritmi \(S\) super-manbadan \(T\) super-quyilishga borish orqali bir nechta manba va quyilish cho‘qqilari bo‘lgan grafda maksimal oqimni topa oladi.

---

Maksimal oqim va minimal kesim teoremasi

Bu teorema nima deyishini tushunish uchun avval kesim nima ekanini bilishimiz kerak.

Cho‘qqilardan ikkita to‘plam tuzamiz: ichida faqat manba cho‘qqisi bo‘lgan "S" deb ataluvchi to‘plam va ichida qolgan barcha cho‘qqilar (quyilish cho‘qqisi ham) bo‘lgan "T" deb ataluvchi to‘plam.

Endi manba cho‘qqisidan boshlab, S to‘plamini qo‘shni cho‘qqilarni qo‘shish orqali kengaytirishimiz mumkin va quyilish cho‘qqisini qo‘shmagunimizcha qo‘shni cho‘qqilarni xohlagancha qo‘shishda davom etishimiz mumkin.

S to‘plamini kengaytirish T to‘plamini kichraytiradi, chunki har qanday cho‘qqi yo S to‘plamiga, yo T to‘plamiga tegishli bo‘ladi.

Har qanday cho‘qqi yo S, yo T to‘plamiga tegishli bo‘lgan bunday holatda to‘plamlar orasida "kesim" bo‘ladi. Kesim S to‘plamidan T to‘plamiga cho‘zilgan barcha qirralardan iborat.

S to‘plamidan T to‘plamiga boradigan qirralarning barcha sig‘imlarini qo‘shsak, kesimning sig‘imini olamiz — bu shu kesimda manbadan quyilishga mumkin bo‘lgan umumiy oqimdir.

Minimal kesim — biz hosil qila oladigan eng kichik umumiy sig‘imli kesim bo‘lib, u tor joy (bottleneck) bo‘ladi.

Quyidagi rasmda ushbu sahifa yuqorisidagi simulyatsiyadagi grafda uchta turli kesim hosil qilingan.

A kesim: Bu kesimda \(s\) va \(v_1\) cho‘qqilari S to‘plamida, qolgan cho‘qqilar esa T to‘plamida joylashgan. Bu kesimda S to‘plamidan chiqib ketadigan, quyilishdan manbaga yo‘nalgan qirralarning umumiy sig‘imi 3+4+7=14 ga teng. \(v_2 \rightarrow v_1\) qirrasining sig‘imini qo‘shmaymiz, chunki bu qirra teskari yo‘nalishda — quyilishdan manbaga qarab boradi. Demak, A kesim orqali mumkin bo‘lgan maksimal oqim 14 ga teng.

B kesim: B kesim orqali mumkin bo‘lgan maksimal oqim 3+4+3=10 ga teng.

C kesim: C kesim orqali mumkin bo‘lgan maksimal oqim 2+6=8 ga teng. Agar grafdagi boshqa barcha kesimlarni tekshirsak, umumiy sig‘imi bundan kichikroq kesimni topa olmas edik. Bu — minimal kesim. Sahifa yuqorisidagi maksimal oqimni topuvchi simulyatsiyani ishga tushirib ko‘rdingizmi? Unda maksimal oqim 8 ekanini ham bilasiz — maksimal oqim va minimal kesim teoremasi aynan shuni aytadi.

Maksimal oqim va minimal kesim teoremasiga ko‘ra, grafda minimal kesimni topish maksimal oqimni topish bilan bir xil, chunki minimal kesimning qiymati maksimal oqim qiymatiga teng bo‘ladi.

---

Maksimal oqim va minimal kesim teoremasining amaliy ahamiyati

Ford-Fulkerson kabi algoritm yordamida grafda maksimal oqimni topish minimal kesim qayerda ekanini tushunishga ham yordam beradi: minimal kesim qirralar to‘liq sig‘imga yetgan joyda bo‘ladi.

Minimal kesim tor joy joylashgan yerda bo‘ladi, shuning uchun agar oqimni maksimal chegaradan oshirmoqchi bo‘lsak (amaliy vaziyatlarda ko‘pincha shunday bo‘ladi), umumiy oqimni oshirish uchun grafdagi qaysi qirralarni o‘zgartirish kerakligini endi bilamiz.

Ko‘proq oqim o‘tishiga imkon berish uchun minimal kesimdagi qirralarni o‘zgartirish ko‘p vaziyatlarda juda foydali bo‘lishi mumkin:

• Transport oqimini yaxshilashga erishish mumkin, chunki shahar rejalashtiruvchilari endi qayerda qo‘shimcha yo‘laklar qurish, qayerda transport harakatini boshqa yo‘nalishga burish yoki qayerda svetoforlarni optimallashtirish kerakligini biladi.
• Ishlab chiqarishda, masalan, uskunalarni yangilash yoki resurslarni qayta taqsimlash orqali yaxshilanishlarni aynan tor joyga yo‘naltirib, yuqoriroq ishlab chiqarish hajmiga erishish mumkin.
• Logistikada tor joy qayerdaligini bilgan holda marshrutlarni o‘zgartirish yoki muhim nuqtalarda sig‘imni oshirish orqali ta’minot zanjirini optimallashtirish va tovarlarning omborlardan iste’molchilarga samaraliroq yetkazilishini ta’minlash mumkin.

Shunday qilib, minimal kesimni topish uchun maksimal oqim algoritmlaridan foydalanish tizimni yanada yuqori o‘tkazuvchanlikka erishish uchun qayerda o‘zgartirish mumkinligini tushunishga yordam beradi.

---

Maksimal oqim masalasining matematik tavsifi

Maksimal oqim masalasi nafaqat informatika mavzusi, balki matematika sohasiga tegishli matematik optimallashtirishning bir turi hamdir.

Agar buni matematik jihatdan yaxshiroq tushunmoqchi bo‘lsangiz, quyida maksimal oqim masalasi matematik atamalar bilan tavsiflangan.

Grafdagi bir cho‘qqidan (\(u\)) boshqa cho‘qqiga (\(v\)) boradigan barcha qirralarda (\(E\)) oqim (\(f\)) shu qirraning sig‘imidan (\(c\)) kichik yoki unga teng bo‘ladi:

\[ \forall (u,v) \in E: f(u,v) \leq c(u,v) \]

Bu, mohiyatan, qirradagi oqim shu qirraning sig‘imi bilan cheklanganini bildiradi.

Shuningdek, barcha qirralar (\(E\)) uchun \(u\) dan \(v\) ga bir yo‘nalishdagi oqim teskari yo‘nalishda, ya’ni \(v\) dan \(u\) ga manfiy oqim bo‘lishi bilan bir xil:

\[ \forall (u,v) \in E: f(u,v) = -f(v,u) \]

Quyidagi ifoda esa manba cho‘qqisi (\(s\)) va quyilish cho‘qqisidan (\(t\)) tashqari barcha cho‘qqilar (\(u\)) uchun oqimning saqlanishi bajarilishini ifodalaydi:

\[ \forall u \in V \setminus \{s,t\} \Rightarrow \sum_{w \in V} f(u,w) = 0 \]

Bu shunchaki cho‘qqiga kiradigan oqim miqdori shu cho‘qqidan chiqadigan oqim miqdoriga teng ekanini bildiradi (manba va quyilish cho‘qqilaridan tashqari).

Va nihoyat, \(s\) manba cho‘qqisidan chiqqan butun oqim \(t\) quyilish cho‘qqisiga borib tushishi kerak:

\[ \sum_{(s,u) \in E} f(s,u) = \sum_{(v,t) \in E} f(v,t) \]

Yuqoridagi tenglamaga ko‘ra, manba cho‘qqisidan chiquvchi qirralardagi barcha oqimni qo‘shsak, quyilish cho‘qqisiga kiruvchi barcha qirralardagi oqimni qo‘shganda chiqadigan yig‘indining xuddi o‘zini olamiz.

---