Mahmudova Dilnoza Avaz qizi guruh cal017 Variant №37

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.