Mahmudova Dilnoza Avaz qizi guruh cal017 Variant №37



Download 355.73 Kb.
bet4/7
Sana15.05.2021
Hajmi355.73 Kb.
1   2   3   4   5   6   7
Lemma 3.

(G, s, t, c) nuqtalar tarmog'i bo'lsin, C (S, T) har qanday kesma va F a oqimga teng bo'lsin, keyin:

f (S, T) = val (f)

Endi Lemma 1 va Lemma 3 ni birlashtirib, biz quyidagi aniqliklarni olamiz:

Tutashganlik 1. (G, s, t, c) kuchlar tarmog'i bo'lsin, C (S, T) har qanday kesma va F a oqim G ga teng bo'lsin, keyin:

val (f) ≤ c (S, T)

1-xulosa shuni ko'rsatadiki, har qanday kesishning hajmi kamida G.ning o'rtacha qiymatidir. Maks-oqim / Min-kesim teoremasida aytilishicha, minimallashtirilgan kesim mavjud (masalan, c (S, T) = val ( f)) lekin bu faqat tarmoq o'zi uchun maksimal quvvat zichligi bo'lganida yuz beradi! Shuning uchun har qanday oqim tarmog'ida (G, s, t, c) maksimal oqim qiymati tarmoqdagi minimal kesishning hajmiga teng bo'ladi.

Endi, yakuniy:

Maksimal oqim / Min-cut teoremasining isboti. Biz teoremaning 3 nuqtasi bir-biriga teng ekanligini ko'rsatmoqchimiz, shuning uchun

1 = ⇒ 2,2 = ⇒ 3 va 3 = ⇒ 1. 1 = ⇒ 2: f maksimal fl ow bo'lsin va Gf harakatsiz deb faraz qilaylik. Agar f ning maksimal tomoniga qarama-qarshi bo'lgan bo'lsa, biz valent (F) ni P bo'ylab kattalashtirishimiz mumkin.

2 = ⇒ 3: Gfda kattalashtiradigan yo'llar yo'q deylik. Biz C (S, T) kesmani c (S, T) = val (f) darajaga keltiramiz. S dan o'tish mumkin bo'lgan uchliklarning to'plamini belgilaymiz: Agar s dan vertex v gacha bo'lgan kengayadigan yo'l mavjud bo'lsa, v ∈ S keyin S = V \ S, shuning uchun t ∈ T va C (S, T) to'g'ri kesimdir. C (S, T) bo'yicha nima bor? (U, v) kesmani kesib o'tishni ko'rib chiqing, ya'ni u ∈ S, v ∈ T. Eslatib o'tamiz, cf (u, v) Gf qoldiq grafigidagi chekka sig'imini (u, v) anglatadi. Biz cf (u, v) = 0 ekanligini bilamiz, chunki aks holda s, v yo'l va v yo'llar S ga joylashtirilgan edi. Endi biz (u, v) chekka qayerdan kelishini bilishimiz kerak.

Agar (u, v) G ning qirrasi bo'lsa, unda cf (u, v) = 0 bo'lganligi sababli, c (u, v) (f (u, v) = 0, demak c (u, v) = f (u, v). Agar (u, v) G ning chekkasi bo'lmasa (ya'ni qoldiq grafikka qo'shilgan bo'lsa, unda f (v, u) = 0.



3. Shuning uchun bizda quyidagilar bor

3 = ⇒ 1: S (S, T) sig'imning kesimi bo'lsin (S, T) = val (f), f0 esa G ning maksimal oqim bo'lishi kerak, shuning uchun val (f) ≤ val (f’). Val (f) = c (S, T), c (S, T) ≤ val (f’) bo'lgani uchun. Va 1-songa ko'ra val (f’) ≤ c (S, T). Va shunday qilib val (f’) = c (S, T) = val (f).

Endi Ford-Fulkersonning optimalligi bitta chiziq isbotidir (hatto emas):

2 = ⇒ 1 Endi aniq bo'lish kerakki, Ford-Fulkerson shuningdek minimal quvvatni qisqartirish muammosini hal qiladi: Tarmoq mavjud bo'lsa, uning minimal quvvatini hisoblang, t kesilgan.



Quyidagi tarmoqni ko'rib chiqing:

3-rasm


Ford-Fulkerson yordamida maksimal qiymatni hisoblash uchun qancha vaqt ketadi? Xo'sh, algoritm har iteratsiyada 1 birlik oqimni ni yuborishi mumkin: BFSni bajaring, kattalashadigan yo'lni oching, evolyutsiyani 1 ga ko'paytiring. Shunday qilib, umuman olganda, O ((m + n) ∗ val (f)) bo'lishi mumkin. Edmonds va Karp tufayli amalga oshirilgan yaxshiroq natijalar, agar biz har iteratsiyada qaysi kattalashtirish yo'lini diqqat bilan tanlasak (aniqrog'i, eng ko'p ko'tariladigan yo'llar orasida eng ozi bor), u holda biz Ford- ni amalga oshira olamiz. Fulkerson O (nm2) da.

Ford-Fulkerson teoremasi asosida Ford-Fulkerson algoritmi kelib chiqqan.




Download 355.73 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2020
ma'muriyatiga murojaat qiling

    Bosh sahifa
davlat universiteti
ta’lim vazirligi
O’zbekiston respublikasi
maxsus ta’lim
zbekiston respublikasi
axborot texnologiyalari
o’rta maxsus
davlat pedagogika
nomidagi toshkent
guruh talabasi
pedagogika instituti
texnologiyalari universiteti
toshkent axborot
xorazmiy nomidagi
rivojlantirish vazirligi
samarqand davlat
haqida tushuncha
navoiy nomidagi
toshkent davlat
nomidagi samarqand
ta’limi vazirligi
Darsning maqsadi
vazirligi toshkent
Toshkent davlat
tashkil etish
kommunikatsiyalarini rivojlantirish
Ўзбекистон республикаси
Alisher navoiy
matematika fakulteti
bilan ishlash
Nizomiy nomidagi
vazirligi muhammad
pedagogika universiteti
fanining predmeti
таълим вазирлиги
sinflar uchun
o’rta ta’lim
maxsus ta'lim
fanlar fakulteti
ta'lim vazirligi
Toshkent axborot
махсус таълим
tibbiyot akademiyasi
umumiy o’rta
pedagogika fakulteti
haqida umumiy
Referat mavzu
fizika matematika
universiteti fizika
ishlab chiqarish
Navoiy davlat