Mahmudova Dilnoza Avaz qizi guruh cal017 Variant №37

Lemma 1.

(G, s, t, c) kuchlar tarmog'i bo'lsin, S(S, T) kesma va f a oqim,

keyin: f(S, T) ≤ c(S, T).

Isbot.

Tarmoqdagi har bir (u, v) uchun bu o’rinli

f (u, v) ≤ c (u, v)

Shuning uchun

Ushbu lemma nima degani, siz tarmoq (C, S) orqali o'tadigan har qanday kesish har doim uning imkoniyatlari bilan bog'liqdir.

Endi quyidagi lemmani ko'rib chiqing:

Lemma 2.

T (f, S, T) elementlari kesimini, F (S, T) ni kesuvchi tarmoq T bo'lsin:

f= (S ∪ {v}, T \ {v})

Agar oqim yuqori kesma bilan chegaralangan bo'lsa, u holda v ∈ T uchini kiruvchi qo'shni u ∈ S bilan topa olmaymiz, chunki c (u, v) juda yuqori. V ga S ni intuitiv ravishda o'tkazish bu yangi kesmaning sig'imini kamaytiradi (umumiy sig'imi c (u, v) ni yo'qotadi) va shuning uchun uning mos keladigan kuchi biz boshlagan

f (S, T) dan osonroq bo'lishi mumkin.

Isbot.

C (S, T) har qanday kesma va v Tning elementi bo'lsin va v-ni T-dan olib, S-ga joylashtiramiz va endi S’= S ning bu yangi kesilgan C’ (S’, T’) qiymatini baholaylik.

∪ {v}, T’= T \ {v}. In (v) = {(u, v) ∈ E | u ∈ V} kiruvchi qirralarning yig'indisini v ga, va

Out (v) = {(v, w) ∈ E | w ∈ W} yig'indisini belgilang.

V dan chiqadigan qirralar, biz bilamizki, oqim orqali:

Biz (v) va Out (v) qismlarga bo'linamiz, bunda qirralarning so'nggi nuqtalari quyidagicha bo'ladi:

Keling, endi ushbu yangi kesmaning evaziga baho beraylik. V ni S ga o'tkazish v ning kesish qobiliyatiga v hissasini yo'qotishiga olib keladi, lekin v dan chiquvchi qirralarning hajmini oladi:

Ikkinchi tenglik InS (v) ∪InT (v) = In (v) va OutS (v) utOutT (v) = Out (v) dan kelib chiqadi va oxirgi tenglik oqimni saqlashdan kelib chiqadi.

Ushbu lemmani quyidagi C (S, T) kesmalarga qo'llashga e'tibor bering:

S = {s}, T = V \ {s}, bundan kelib chiqadi

S’ ⊂ V \ {s} uchun har qanday kesimning o 'zi biz boshlagan birinchi kesmaning oqimiga ga teng ekanligini bildiradi, ya'ni ({s}, V \ {s}). Ammo C ({s}, V \ {s}) kesim shunchaki manbani tark etadigan narsa

Shuning uchun (3), (4) va (5) dan foydalanib, quyidagi lemma olamiz:

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.

Ford-Fulkerson algoritmi

Ford-Fulkerson algoritmining oddiy g'oyasi quyidagicha:

1) boshlang'ich oqimidan 0 sifatida boshlang.

2) manbadan to cho'kishgacha bo'lgan yo'l bor.

           Ushbu yo'l oqimini oqimga qo'shing.

3) Qaytish oqimi.

1-cpp va 1-java fayllarida Ford-Fulkerson algoritmiga asoslanib grafning maksimal oqimini topis dasturi java va c++ dasturlash tillarida ishlangan.

4-rasm. 1-cppning natijasi.

5-rasm.1-javaning natijasi