Identifikatsiyalash

Masala. Toʻrtta havo yoʻliga taqsimlash uchun 3 xil samolyot berilgan boʻlsin. Agar har bir xildagi samolyotlarning soni, bir oylik yuk tashish hajmining birligi va samolyotlarni ishlatish uchun ketgan xarajatlarning son qiymati quyidagi jadvaldagidek boʻlsa, samolyotlarni shunday taqsimlash kerakki, eng kam xarajat sarflab, har bir havo yoʻli boʻyicha mos ravishda 300, 200, 1000, va 500 birliklardan kam boʻlmagan yuk tashilsin.

Samolyotlar xili	Samolyotlar soni	Har bir havo yoʻli boʻyicha bir oylik yuk tashish hajmi				Har bir havo yoʻli boʻyicha samolyotlarni ishlatish uchun ketgan xarajat
		1	2	3	4	1	2	3	4
1 2 3	50 20 30	15 30 25	10 25 50	20 10 30	50 17 45	15 70 40	20 28 70	25 15 40	40 45 65
Yuk tashish birligi miqdori		300	200	1000	500

Masalaning matematik modeli qurilsin.

Echish. j-nomerli havo yoʻli boʻyicha yuk tashish uchun zarur boʻlgan i-xil samolyotlar sonini x_ij bilan belgilasak, shu yoʻllar boʻyicha yuk tashish uchun ketgan xarajatlar jadvalga asosan quyidagicha boʻladi:
Z₁=15x₁₁+70x₂₁+40x₃₁
Z₂=20x₁₂+28x₂₂+70x₃₂
Z₃=25x₁₃+15x₂₃+40x₃₃
Z₄=40x₁₄+45x₂₄+65x₃₄
Umumiy xarajat esa

ga teng boʻladi. Ikkinchi tomondan, har bir xavo yoʻli boʻyicha mos ravishda 300, 200, 1000 va 500 birliklardan kam boʻlmagan yuk tashilishi, hamda har bir xil samolyotdan shu yoʻllarning hammasiga 50, 20 va 30 tadan berkitilishi kerak boʻlganligi uchun quyidagi cheklanish shartlariga ega boʻlamiz:

2.2. Transport tarmoqlarida maksimal oqim va minimal qirqim masalasi.
Ford-Falkerson algoritmi.
2.2.1 Maksimal oqim va minimal qirqim toʻgʻrisida tushuncha.

Y uqoridagi mavzularda biz garflar toʻgʻrisidagi asosiy tushunchalar, graflarni ifodalash usullari, ikki tugun orasidagi uzatish funksiyasi, graflarda eng qisqa yoʻl masalasi kabi mavzular koʻrib oʻtildi. Endi yana bir muhim yoʻnalishlardan biri tarmoqlardagi oqim masalasini koʻrib chiqamiz. Amaliyotda koʻpincha turli xil tarmoqlar, masalan – transport tarmogʻi, aloqa tarmogʻi, elektr tarmogʻi va boshqa tarmoqlar bilan toʻqnash kelishga toʻgʻri keladi. Shuning uchun ham bunday tarmoqlarni matematik jihatdan oʻrganish muhim amaliy ahamiyatga egadir. Tarmoqlar nazariyasida grafli usullar katta rol oʻynaydi. Masalan, bizga quyidagi graf berilgan boʻlsin:

2.3.1-rasm. Transport tarmogʻini ifodalovchi graf.
Deylik, yuboruvchi w oluvchiga bir nechta fanni kanallar orqali joʻnatmoqchi boʻlsin. 2.3.1-rasmda berilgan grafning yoylaridagi berilgan sonlar mavjud kanallar boʻyicha yuborilishi mumkin boʻlgan fanlarning maksimal sonini bildiradi. yuboruvchi uchun har bitta kanalning oʻtkazish qobiliyatidan oshib ketmagan holda yuboriladigan fanlarning maksimal sonini bilish qiziq, albatta.
Yoʻnaltirilmagan grafning har bitta yoyiga uning oʻtkazish qobiliyati deb nomlanuvchi nomanfiy haqiqiy son qoʻyilgan tarmoqni deb nomlaymiz. Boshqacha soʻz bilan aytganda, tarmoqda juftlik boʻlib, – yoʻnaltirilmagan graf, – funksiya grafdagi yoylar toʻplamni akslantiruvchi nomanfiy haqiqiy sonlar toʻplami. Yoʻnaltirilgan graflar terminologiyasiga koʻra tarmoq uchun koʻrinishdagi yoylarning oʻtkazish qobiliyatlari summasini aniqlaganimizdek, tugun chiqishining yarimdarajasini ham aniqlash mumkin. Shu tushunchalarga asoslangan holda tugunlarning kirish yarimdarajasi ham aniqlanadi. Shunisi aniqki, tarmoqdan chiquvchi barcha tugunlarning yarimdarajasi kirish yarimdarajasi summasiga teng [8,9].
Faraz qilaylik, yoʻnaltirilgan grafda kirish yarimdarajasi nolga teng boʻlgan shunday yagona tugun hamda, xuddi shunday chiqish yarimdarajasi nolga teng boʻlgan tugun mavjud. Bu tugunlar mos ravishda tarmoqning kirishi va chiqishi deyiladi.
tarmoq berilgan boʻlsin. Tarmoq orqali, grafdagi yoydan oʻtadigan, hamda oqim deb nomlanuvchi va har bitta yoyga taqqoslanuvchi nomanfiy haqiqiy sonni, funksiyada quyidagi shartlarni qanoatlantiruvchi oqimni aniqlaymiz:

1. 
   ixtiyoriy yoy uchun shart bajarilsa;
   
2. 
   tarmoqda kirish va chiqishdan farqli ravishda, ixtiyoriy tugunnning chiqish yarimdarajasi uning kirish yarimdarajasiga teng boʻlsa.
   

Ushbu shartlar, oqimning ixtiyoriy yoyini oʻtkazish qobiliyatini oshirmasligini va ixtiyoriy tugunga kirib kelayotgan “oqim” undan chiqib ketayotgan “oqim”ga (kirish – chiqishdan farqli ravishda) tengligini bildiradi. Ma’lumki, kirishga insendent boʻlgan yoylardan oʻtuvchi oqim summasi, chiqishga insendent boʻlgan yoylardan oʻtuvchi oqim summasiga tengdir. Bu summa oqim kattaligi deyiladi. Bizni katta qiymat oluvchi maksimal oqim qiziqtiradi. Masalan, quyidagi 2.3.2 -rasmda grafda maksimal oqim 6 ga teng.




2.3.2 – rasm. Transport tarmogʻi.
tarmoq uchun qirqim tushunchasini aniqlaydigan boʻlsak, bunda grafning yoyi boʻladigan bunday toʻplam, da dan keluvchi ixtiyoriy yoʻnaltirilgan oddiy zanjir dan olingan yoydan iborat boʻladi. qirqimning oʻtkazish qobiliyati deb yoyga tegishli oʻtkazish qobiliyati summasiga aytiladi. Minimal qirqim deb oʻtkazish qobiliyati kichik qiymatni qabul qiluvchi qirqimga aytiladi. Masalan, 2.3.2 -rasmdagi , yoylar toʻplami qirqim hisoblanadi. Uning oʻtkazish qobiliyati 6 ga teng boʻlib maksimal oqim kattaligi bilan bir xil. tenglik uchun oʻrinli boʻlgan yoy toʻyingan deyiladi. Oqimdagi boʻlgan shartlarda barcha yoylar uchun yoy boshlangʻich deyiladi.
Bilamizki, oqimning ixtiyoriy kattaligi ixtiyoriy qirqimning oʻtkazish qobiliyatini oshirmaydi, maksimal oqim kattaligi esa minimal qirqimning oʻtkazish qobiliyatidan ortib ketmaydi. Bundan koʻrinadiki, bu ikkita son bir-biriga tengdir. Bu xulosaga mos keluvchi natijalar Ford-Falkerson teoremasida ham oʻz aksini topgan [9].
2.2.2. Ford-Falkerson teoremasi.
2.2.1.-Teorema. Maksimal oqim kattaligi minimal qirqimning oʻtkazish qobiliyatiga tengdir.
Isbot: oqim summasi ixtiyoriy qirqimning minimaliga teng, shu bilan birga minimal qirqimning oʻtkazish qobiliyatini oshirmaydi. Bundan, maksimal oqim minimal qirqimning oʻtkazish qobiliyatidan katta emasligi kelib chiqadi. Endi, maksimal oqimning minimal qirqimdan kichkina emasligini isbot qilish kerak. Oqim maksimal boʻlsin. Unda, tarmoqdagi qolgan ketuvchi yoʻllardan manbaga etib boʻlmaydi. Deylik, manbadan tarmoqning qolganiga yetkizuvchi tugunlar toʻplami, esa aksincha boʻlsin. U holda boʻlganligi uchun qirqim hisoblanadi. Bundan tashqari qolgan tarmoqda boʻlganligi uchun musbat oʻtkazish qobiliyatiga ega boʻlgan yoy mavjud emas, aks holda dan ga borish mumkin boʻlardi. Shu bilan birga, tarmoqqa kiruvchi oqim ixtiyoriy yoyning oʻtkazish qobiliyatiga teng, demak qirqimdan oʻtuvchi oqim ham uning oʻtkazish qobiliyatiga tengdir. Lekin, ixtiyoriy qirqimdan oʻtadigan oqim manbadagi oqim summasiga, ya’ni maksimal oqimga teng. Demak, maksimal oqim minimal qirqimning oʻtkazish qobiliyatidan kichik boʻlmagan minimal qirqim oʻtkazish qobiliyatiga teng. Teorema isbotlandi.