Reja: Maksimal oqim muammosi. Qoldiq tarmoq. Kengaytirilgan (ortib boruvchi) yo'l. Ford-Fulkerson algoritmi

Mavzu 14. Maksimal oqim bo'yicha topshiriqlar
Reja:
1. Maksimal oqim muammosi. Qoldiq tarmoq. Kengaytirilgan (ortib boruvchi) yo'l. Ford-Fulkerson algoritmi.
2. Minimal xarajatlarning maksimal oqimi muammosi (MaPMiS). Qaror algoritmi.
3. Transport to'plamlari.
https://studfiles.net/preview/2674898/pagepage/

1. Maksimal oqim muammosi. Qoldiq tarmoq. Kengaytirilgan (ortib boruvchi) yo'l. Ford-Fulkerson algoritmi.

https://www.youtube.com/watch?v=u9NigdVHUr0
https://www.youtube.com/watch?v=jejpJw0cqms

Maksimal oqim muammosi.

Tarmoq bu g = (v, e) yo'naltirilgan o'lchov grafigi bo'lib, uning musbat qirralari c (e) dir, bunda bitta bitta uchi bor - manba (S) va bitta bitta vertex - drenaj (T).
S va T ga teng bo'lmagan tovushlar ichki deyiladi,
Og'irlik re6ra s (e) - qovurg'aning o'tkazish qobiliyati.
Oqim f funktsiyasi bo'lib, u cheklangan qatorlarni haqiqiy sonlar to'plamiga olib boradi.
F funktsiyasi qanoatlantiradi:
1. Har qanday chekka e € E uchun: 0 <= f (e) <= c (e)
2. Barcha v ∈ V, v <> S, v = T: div + (v) = div_ (v), bu erda
• div + - barcha qirralar bo'ylab oqim, ya'ni e = (u, v) div + (v) =, e = (u, v) kiruvchi oqimning qiymati.
• div_ - chiquvchi oqim hajmi div_ (v) =,
Oqim xususiyati: div_ (S) = div + (T)
Div_ (S) = div + (T) qiymati tarmoqdagi oqimning qiymati deb ataladi.
Maksimal oqim muammosi.
Boshqa oqim qiymatidan past bo'lmagan oqimni toping (maksimal qiymatli oqim)
Qoldiq tarmoq.
G tarmog'iga ruxsat berilsin va unda oqim boshlansin, qoldiq tarmoq V ning ko'p qirralari va ko'plab kamonlari bilan aniqlangan yo'naltirilgan grafikdir:
1. agar G tarmog'ida chekka (u, v) bo'lsa va uning chetidagi oqim c (e) dan kam bo'lsa, qoldiq tarmoqda e ((u, v) vazni c (e) -f (e) - tekis qovurg'alar
2. Agar oqim va e = (u, v) qirralari bo'lsa va bu chetidan o'tadigan oqim> 0 bo'lsa, qoldiq tarmoqda f (e) og'irligi bo'lgan (=, u, v) chekka bor - qarama-qarshi qirralar.
Kengaytirilgan (ortib boruvchi) yo'l.
Agar qoldiq tarmoqda S dan T ga yo'naltirilgan yo'l mavjud bo'lsa, u holda asl tarmoqda bu yo'l bo'ylab oqim ko'payishi mumkin. Bunday holda, to'g'ri qirralar bo'ylab o'tish - bu asl tarmoqning ma'lum bir chetida oqimning ko'payishi va yaqinlashayotgan tomon bo'ylab oqimning pasayishi.
Ford-Fulkerson algoritmi
1. f (e) = 0 oqimini boshqaring
2. Qoldiq tarmog'ini yarating
3. Qoldiq tarmoqda S dan T gacha bo'lgan yo'nalishni toping
4. Agar yo'l topilgan bo'lsa, unda ushbu yo'l bo'ylab oqimni oshiring va 2-bosqichga o'ting. Aks holda, algoritmning oxiri. Oqim maksimal darajada.

2. Minimal xarajatlarning maksimal oqimi muammosi (MaPMiS). Qaror algoritmi.

Tarmoq mavjud bo'lsin va S (e) narxi har bir chekkada belgilanadi. Chegaradan o'tish qiymati S (e) * f (e). Tarmoq oqimi qiymati - barcha qirralarning oqimining umumiy qiymati
MaPMiS-ning vazifasi bunday maksimal oqimni topishdir, uning qiymati boshqa har qanday oqim oqimidan oshmaydi. (kelajakda faqat maksimal oqimlar ko'rib chiqiladi)
Qoldiq tarmog'ini qurishda biz nafaqat qovurg'alarning tarmoqli kengligini, balki ularning narxini ham hisobga olamiz. To'g'ri qirralar uchun xarajat asl qirraning narxiga teng. Kutish uchun: xarajat asl chekkaning narxiga teskari.
Algoritm:
1. Maksimal oqimni yarating
2. Xarajatlarni hisobga olgan holda qoldiq tarmoqni yarating
3. Qoldiq tarmoqda manfiy qiymatga ega yo'naltirilgan tsiklni toping
4. Agar tsikl topilsa, u holda oqim uning ortishi bilan ortadi. Aks holda, oxir. Oqim - MaPMiS
Transport tarmog'ini aniqlash.
3. Transport tarmog'i
https://www.youtube.com/watch?v=TCP1nsRHUNo

Ford-Fulkerson teoremasining muhim natijasi transport tarmog'ida maksimal oqimni qurish algoritmi hisoblanadi.

Algoritm:
1-qadam. Biz i = 0 ni o'rnatdik. D transport tarmog'idagi har qanday ruxsat etilgan oqim bo'lsin (masalan, to'liq, siz nol oqim bilan boshlashingiz mumkin :).
2-qadam. D va oqim tarmog'idan foydalanib, biz sonlarning grafigini tuzamiz.
Qadam 3. Biz oddiy zanjirni topamiz, bu yuklangan digrafdan minimal yo'l. Agar bu zanjirning uzunligi cheksizlikka teng bo'lsa, unda oqim maksimal bo'ladi va algoritm tugallanadi. Aks holda, biz zanjir bo'ylab oqimni maksimal ruxsat etilgan qiymatga ko'paytiramiz, shunday qilib ruxsat etilgan oqimning 1 sharti saqlanib qoladi (har qanday yoy uchun, x yoyi bo'ylab oqim deb atalgan miqdor shartni qondiradi). Ko'rsatilgan miqdorning mavjudligi, ishlatilishi va ishlatilishi tufayli biz uning mavjudligini aniqlaymiz. Natijada, D transport tarmog'idagi oqim o'zgaradi, ya'ni. oqimdan biz oqimga o'tdik va shu bilan birga. Belgilab qo'ying va 2-bosqichga o'ting.
 
 
AMALIY QISM:
Maksimal oqim muammosi.
Berilgan transport tarmog'i uchun ma'lum bir vaqt ichida S shahridan t-tgacha etkazib berilishi mumkin bo'lgan tovarlarning maksimal oqimini aniqlang. Yo'lning barcha qismlarining sig'imi ma'lum deb hisoblanadi.
1-bosqich
Belgilash tartibidan boshlaylik. Resursni belgilash S Keyinchalik, manba bilan boshq bilan bog'langan uchlarini ko'rib chiqamiz. Bu V1, V2,. Keling, tarmoq bo'ylab boshlang'ich nol oqimini o'tkazib yubormaylik, o'tkazuvchanlik qiymatidan keyin har bir kamon yaqinidagi boshlang'ich oqim qiymatini belgilang.
Biz S vertexiga qaraymiz

, buning uchun biz V1, V3 uchlarini belgilaymiz

Biz V1 uchiga qaraymiz, v2 uchlarini belgilaymiz
Keling, V2 uchini ko'rib chiqaylik, V4 va V7 uchlarini belgilang
Keling, V4 uchini ko'rib chiqamiz, V5 va V6 uchlarini belgilaymiz
Biz V6 uchiga qaraymiz, T uchini belgilaymiz
Oqim o'zgarishini sozlang:
f1 = 4
S => V1 => V2 => V4 => V6 => T
V4V6 yoyi to'yingan bo'ladi
 
 
2-bosqich.
Biz S uchiga qaraymiz, buning uchun V1, V3 uchlarini belgilaymiz

Biz V1 uchiga qaraymiz, v2 uchlarini belgilaymiz

Keling, V2 uchini ko'rib chiqaylik, V4 va V7 uchlarini belgilang
Keling, V4 uchini ko'rib chiqaylik, V5 uchlarini belgilang
Biz V5 cho'qqisiga qaraymiz, V6 cho'qqisini belgilaymiz
Biz V6 uchiga qaraymiz, T uchini belgilaymiz
Oqim o'zgarishini sozlang:
F2 = 6
S => V1 => V2 => V4 => V5 => V6 => T
Ark V1V2 to'yingan bo'ladi
 
 

(S +; 23)

(V2 +; 6)

 
3-bosqich.

Biz S uchiga qaraymiz, buning uchun V1, V3 uchlarini belgilaymiz
Biz V3 cho'qqisiga qaraymiz, V4 cho'qqisini belgilaymiz
Biz V4 uchiga qaraymiz, V5, V2 uchlarini belgilaymiz
Biz V5 cho'qqisiga qaraymiz, V6 cho'qqisini belgilaymiz
Biz V6 uchiga qaraymiz, T uchini belgilaymiz
Oqim o'zgarishini sozlang:
F3 = 1
S => V3 => V4 => V5 => V6 => T
V5V6 yoyi to'yingan bo'ladi
 
 
 
4-bosqich.
Biz S uchiga qaraymiz, buning uchun V1, V3 uchlarini belgilaymiz
Biz V3 cho'qqisiga qaraymiz, V4 cho'qqisini belgilaymiz
Keling, V4 uchini ko'rib chiqaylik, V2 uchlarini belgilang
Biz V2 cho'qqisiga qaraymiz, V7 cho'qqisini belgilaymiz
Biz V7 uchiga qaraymiz, T uchini belgilaymiz
Oqim o'zgarishini sozlang:
F4 = 10
S => V3 => V4 => V2 => V7 => T
 
 
 
5-bosqich.
Biz S uchiga qaraymiz, buning uchun V1, V3 uchlarini belgilaymiz
Biz V3 cho'qqisiga qaraymiz, V4 cho'qqisini belgilaymiz
Keling, V4 uchini ko'rib chiqaylik, V5 uchlarini belgilang
Biz V5 cho'qqisiga qaraymiz, V7 cho'qqisini belgilaymiz
Biz V7 uchiga qaraymiz, T uchini belgilaymiz
Oqim o'zgarishini sozlang:
F5 = 8
S => V3 => V4 => V5 => V7 => T
V5V7 yoyi to'yingan bo'ladi
 
 
 
6-bosqich
Biz S uchiga qaraymiz, buning uchun V1, V3 uchlarini belgilaymiz
Biz V3 cho'qqisiga qaraymiz, V4 cho'qqisini belgilaymiz
Keling, V4 uchini ko'rib chiqaylik, V5 uchlarini belgilang
 
 
 
F = 0 + 6 + 1 + 10 + 8 + 4 = 29
 
L: 8 + 7 + 4 + 10 = 29
(V1V2), (V4V6), (V5V6), (V5V7)
 
Xulosa
 
Diskret matematikaning jadal rivojlanishi kompyuter texnologiyalarining rivojlanishi, axborotni qayta ishlash va uzatish vositalarini yaratish zaruriyati, shuningdek, tabiatda cheklangan tuzilmalar bo'lgan kompyuterlarda turli xil modellarning taqdimoti bilan bog'liq.

Transport tarmog'i - bu cheklangan G (V, E) diagrammasi bo'lib, uning har bir yoyi manfiy bo'lmagan (c) raqam bilan bog'langan va boshq sig'imi deb nomlangan va u erda:

1) bitta manba yoki tarmoqning boshi deb ataladigan bitta kamon ichiga kiradigan aniq bir vertex;
2) yoylardan chiqmaydigan aniq bitta verteks; bu vertex tarmoqning cho'kishi yoki oxiri deb nomlanadi.
Foydalanilgan adabiyotlar ro'yxati
1. A.M. Allaverdiev, I.V. Platonov “Amaliy matematika. Grafika nazariyasining elementlari »M.2000
2. Amaliy matematikadan ma'ruzalar I.V. Platonik
3. V.N. Nefedov, V.A. Osipova "Diskret matematika kursi" M. 1992 yil
4. S.V. Sudoplatov, E.V. Ovchinnikova "Diskret matematikaning elementlari" M. 2002 yil
https://megalektsii.ru/s16942t6.html