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



Download 355.73 Kb.
bet3/7
Sana15.05.2021
Hajmi355.73 Kb.
1   2   3   4   5   6   7
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:




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