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: