Maksimal oqim haqidagi masala. Maksimal oqim haqidagi masalaning qo`yilishi

Mavzu:Maximal oqim va minimal kesim haqidagi teorema .Maksimal oqimni topishning belgi qo’yish usuli.
Reja:

1. 
   Maksimal oqim haqidagi masala
   
2. 
   

Maksimal oqim haqidagi masala.
Maksimal oqim haqidagi masalaning qo`yilishi. Uchlar to`plami  va  dan olingan uchlar juftliklarini tutashtiruvchi   yoylar to`plamidan tashkil topgan G=( , ) tarmoq berilgan bo'lsin. Bu tarmoq simmetrik grafikdan iborat bo`lsin deb faraz qilamiz, ya’ni (i,j) yoy tarmokga karashli bo`lsa, (i,j) yoy xam unga karashli. Tarmoq uchlarini (a<sub>0</sub>,a<sub>1</sub>,a<sub>2</sub>......a<sub>n</sub>)deb nomerlab chiqamiz  ={a<sub>0</sub>,a<sub>1</sub>,a<sub>2</sub>......a<sub>n</sub>} U vaqtda (i,j) yoy (a<sub>i</sub>,a<sub>j</sub>) kabi xam yoziladi.
Xar bir  uch uning intensivligini ifodalovchi d(a<sub>i</sub>) son bilan xarakterlanadi. d(a<sub>i</sub>)>0 bo`lgan uchga manba (a_i-ishlab chiqarish punkti) deb, d(a_i)bo`lgan uchga yaqin a<sub>i</sub> - iste’mol punkti deb, d(a<sub>i</sub>)=0 bo`lgan uchlarga esa oralik uchlar deb aytiladi. Tarmoq yo`llari buylab manbalardan yig`inlarga biror bir jinsli moddaning (masalan, gaz, suyuqlik yoki boshqa biror resurs) oqimi kuzatilayotgan bo`lsin. Xar bir (a<sub>i</sub>,a<sub>j</sub>) yoyga b<sub>ij</sub>
son mos kuyilgan bo`lib, bu songa yoyning okimni o`tkazish kobilyati deyiladi. YOyning utkazish kobilyati deganda uning vakt birligi ichida utkazishi mumkin bulgan modda mikdorini tushunamiz.
Faraz qilaylik,  bo`lsin, ya’ni a₀ -yagona manba, a_n yagona yechim, a₁,a₂......a_n-1 oraliq uchlardir. Xar bir  yoydan vaqt birligida o`tgan modda mikdorini x<sub>ij</sub> deb belgilaymiz va uni yoy bo`ylab okim deb ataymiz. Agar tarmokda (i,j) yo`l, ya’ni (a<sub>i</sub>,a<sub>j</sub>) yoy mavjud bo`lmasa, unga mos oqim x_ij=0.
Tarmoqdagi a₀ mambadan a_n yiginga okim deb barcha (a_i,a_j) yoylar bo`ylab x<sub>ij</sub> oqimlar yig`indisiga aytiladi. Bu oqim  (1)
formula bo`yicha aniqlanadi. Masala tarmoqdagi maksimal oqimni topishdan iborat.
Agar simmetrik yoylarning utkazish qobilyatlari bir-biriga teng bo`lsalar bu yoylarni kirlarga almashtirish mumkin. Shunga asosan masalaning quyilishi aralash va orientirlanmagan graflar uchun xam o`rinlidir. Masalaning qo`yilishiga ko`ra xar bir oraliq
uchga boshqa uchlardan keladigan moddalar yigiindisi shu uchdan chiqadigan moddalar jamisiga teng, ya’ni

Bundan tashqari

Shunday qilib, qo'yilgan masalani matematik ko`rinishda (1) formula bilan aniqlangan v funksiyaning (2), (3) shartlarda maksimumini topishdan iborat deb qarash mumkin.
Maksimal oqim masalasini xal qilish algoritmini asoslashda kesim tushunchasi muxim rol o`ynaydi. Tarmoqning uchlar to`plami
ni shunday kesishmaydigan  to`plamlarga ajratamizki  bo`lsin.
a<sub>0</sub> ni a<sub>n</sub> dan ajratuvchi kesim deb barcha (a<sub>i</sub>, a<sub>j</sub>) yoylarning shunday to`plamiga aytiladiki, ular  uchdan chiqib
uchga kirishadi.
Xar bir  kesim b utkazish kobilyati bilan xarakterlanadi. Kesimning utkazish kobilyati.

formula yordamida xisoblanadi. Kesimning ta’rifidan kœrinib turibdiki, manbadan yiginga boruvchi istalgan yul  kesimning xech bulmaganda bitta yoyini uz ichiga oladi. SHuning uchun kandaydir kesimning barcha yoylarini olib tashlasak manbadan yiginga boradigan birorta xam yul mavjud bulmaydi. Yulning utkazish kobilyati shu yulga kiruvchi yoylarning utkazish kobilyatlarining eng kichigiga teng bulgani uchun okimning v kattaligi, ya’ni a₀ ni a_n bilan boglovchi barcha mumkin bulgan yullar buyicha olib utiladigan okim mikdori istalgan kesimning utkazish kobilyatidan oshmaydi:  . Demak, agar shunday okim topilsaki uning v* kattaligi biror  kesimning utkazish kobilyatiga teng bulsa, ya’ni  tenglik bajarilsa, shu okim maksimal va  minimal utkazish kobilyatli buladi.Maksimal okim xakidagi masalani echish algoritmi. Ford-Falkerson teoremasi.Teorema (Ford-Falkerson). Xar kanday tarmokda a₀ mambadan a_n yiginga maksimal okim mikdori a₀ ni a_n larni bir-biridan ajratuvchi kesimlarning minimal utkazish kobilyatiga teng.
Endi Fordning maksimal okimini topish algoritmining jadval kurinishni karaymiz. Dastlabki kadam. 
ulchovli jadvalga yoylarning utkazish kobilyatlarini yozib chikamiz, bunda n+1 -karalayotgan G=(V,E) tarmokdagi uchlar soni.
(a_i,a_j) yoyning utkazish kobilyati b_ij noldan katta bulsa va simmetrik yoy (a_j,a_i) ning utkazish kobilyati nolga teng bœlsa (i,j) katakka b_ij ni (j,i) katakka esa nolь yozamiz. Agarda b_ij=b_ji=0 bo`lsa (i,j) va (j,i) kataklarga xech narsa yozmaymiz.
Umumiy kadam. 1) a<sub>0</sub> dan a<sub>n</sub> ga utkazish kobilyati noldan katta bulgan yulni topamiz. Buning uchun a<sub>0</sub> ga mos ustunga * belgisi kuyamiz. a<sub>0</sub> katorda b<sub>0j</sub>>0 bulgan ustunlarni topib karalayotgan kator tepasiga 0 (nolь) rakami bilan belgi kuyamiz. Natijada musbat utkazish kobilyatiga ega bulgan barcha (a<sub>0</sub>,a<sub>j</sub>) yoylar ajratiladi. Ular a<sub>0</sub> dan a<sub>n</sub> ga boruvchi yulning dastlabki yoylari bulishadi. Keyin ustunlari belgilangan nomerli katorlarni karaymiz. Xar bir, masalan a<sub>i</sub> katorda, belgilangan ustunlar uchun b<sub>ij</sub>>0 bo`lgan elementlarni topamiz va ularni karalayotgan kator nomeri bilan nomerlaymiz. SHunday kilib, a₀ dan a_n ga boruvchi yulning keyingi yoylarini topgan bulamiz. Katorlarni karashni shu vaktgacha davom ettiramizki: a) yo a_n ustun belgilangan xolga kelamiz (bu xol a₀ dan a_n ga boruvchi musbat o‘tkazish kobilyati yo‘l topilganligi bildiradi); b) yoki yangi ustunlarni belgilash mumkin emasligi xakida xulosa kilamiz. (karalayotgan katorlar uchun belgilanmagan ustunlarda musbat elementlar mavjud emas). Bu xolda musbat utkazish kobliyatiga ega bo‘lgan a₀ dan a_n ga boruvchi yo‘l mavjud emas.
a)holda ustunlar belgilaridan foydalanib izlangan a₀ dan a_n ga μ yulni topamiz. Faraz kilaylik yo‘lning oxirgi uchi a_n k bilan bilan belgilangan bo‘lsin. SHu belgi yordamida a_n oldingi a_k uchni topamiz ( a_k katorni karaganda a_n ustun bilan yo‘ldagi eng oxirgi (a_k, a_n) yoy belgilangan edi). a_k qator a_n ustun kesishish nuktasidagi b_kn elementni minus belgi bilan belgilaymiz. Mos simmetrik element b_nk ni esa plyus belgisi bilan belgilaymiz. Natijada  va  sonlarni xosil kilamiz.
a_k kator karalgani uchun undan oldin, aytaylik r nomer bilan, a_k ustun belgilangan edi. SHuning uchun  elementdan a_k ustun bo‘ylab r katorgacha xarakat kilamiz va b_rk ni minus belgisi bilan, b_rk ni esa minus belgisi bilan belgilaymiz. Bu jarayonni a₀ katorga kelguncha va shu kator elementini minus ishorasi bilan va simmetrik elementni plyus ishorasi bilan belgilaguncha davom ettiramiz. Sungra 2-punktga o‘tamiz.
b) xolda yiginga mos a_n ustunni belgilash mumkin emas. SHu sababli noldan katta o‘tkazish kobilyatiga ega bo‘lgan a₀ dan a_n ga boshka yo‘l mavjud emas, demak umumiy kadam tugaydi. Jadvalning belgilangan ustunlarida joylashgan uchlar R to‘plamni tashkil etadi (a₀ manbadan bu uchlarga boradigan kandaydir yo‘l mavjud). Kolgan uchlar  to‘plamga karashli.  uchdan chikib  uchga kiruvchi yoylar minimal o‘tkazish kobilyatiga ega bo‘lgan kesim tashkil kilishadi va  bu erda b_ij berilgan tarmoq (i,j)
yoyning o‘tkazish kobilyatini ifodalaydi.
2) Topilgan μ yo‘lning o‘tkazish kobilyati θ ni topamiz. Yo‘lning o‘tkazish kobiliyati deganda vakt birligi ichida a₀ dan a_n ga μ yo‘l buyicha utkazish mumkin bulgan moddaning maksimal mikdorini tushunamiz. Yo‘lning o‘tkazish kobilyati shu yo‘lga kiruvchi yoylarning utkazish kobilyatlarining eng kichigiga teng:

3) Topilgan yul yoylarining va ularga simmetrik yoylarning kolgan o‘tkazish kobilyatlarini aniklaymiz. Buning uchun jadvalning
b_ij- elementlaridan θ ni ayiramiz, b_ij+ elementlarga esa θ
ni kushamiz. Bu amallarni bajargandan sung utkazish kobiliyatlari uzgargan dastlabki jadvalga uxshash yangi jadvalni xosil kilamiz. YAngi jadvalni xosil kilgandan sung umumiy kadamning 1-punktiga kaytamiz va uni a₀ dan a_n ga utkazish kobilyati noldan katta bulgan yo‘l mavjud bulmagan jadval xosil bulguncha davom ettiramiz. Xal qiluvchi kadam. Dastlabki jadvalning elementlaridan oxirgi kadamda xosil bulgan jadvalning mos elementlarini ayiramiz. Natijada musbat elementlari (a_i, a_j) yoyning mos x_ij okim miqdorlariga teng bulgan jadvalni xosil qilamiz. Tarmokdagi maksimal oqim esa a₀ qator a_n ustunning elementlari yigindisiga teng bo`ladi, ya’ni

Misol. quyida chizmada berilgan tarmoq uchun a₀ uchdan a_μ maksimal oqimni toping. YOy va qirralarga yozilgan sonlar ularning utkazish qobilyatlarini bildiradi.

Dastlabki qadam. 1-jadvalni tuzamiz.
1-jadval.

	(*)	(0)	(0)	(1)	(2)
ai aj	a0	a1	a2	a3	a4
a0		17	19-
a1	0		4	12
a2	0+	4		8	9-
a3		12	6		24
a4			0+	0

Birinchi qadam. μ ₁=(a₀-a₂-a₄)
yulni xosil qilamiz.
2) topilgan yo`lning o`tkazish qobilyatini aniklaymiz:

) Topilgan yo`l yoylari o`tkazish qobilyatlarini θ ₁=9 ga kamaytirib, simmetrik yoylarning utkazish qobilyatlarini esa 9 ga oshiramiz. Natijada 2-jadvalga ega bo`lamiz.