Mahmudova Dilnoza Avaz qizi guruh cal017 Variant №37

Maksimal oqim / minimal qisqartirish teoremasi:

(G, s, t, c) tarmog'imiz oqim bo'lib, chap f esa tarmoqdagi kuchlanish bo'lsin. Quyidagi narsa tengdir:

1. f maksimal darajaga ko'tarildi.

2. Gf-da kengayadigan yo'llar yo'q.

3. C (S, T) kesma mavjud, bunda c (S, T) = val (f).

Kesish nima?

Bekor qilish: (G, s, t, c) kuchlanishli tarmoq bo'lsin, G-da kesilgan kesma V ning S va T ikkita to'plamga bo'linishi shunday bo'ladi:

1. S ∪T = V

2. S ∩T = ∅

3. s ∈ S va t ∈ T

Quyida C (S, T) kesmaning misoli, bu yerda S = {s, c, d} va T = {a, b, t}.

1-rasm

C (S, T) deb belgilangan kesmaning c (S, T) hajmi u ∈ S bilan qirralarning sig'imlarining yig'indisidir (u, v)

va v ∈ T. Ya'ni:

(1)

Yuqoridagi misolda c (S, T) = 23, biz (a, c) chekkasini hisoblamaymiz, chunki a ∈ T, c ∈ S. Bu kesish qobiliyatining aniqlanishi tabiiydir va bu biz kesmadagi oqimni ham shunga o'xshash tarzda yechish mumkin. Demak, C (S, T) sig'im bilan kesishgan bo'lsa (S, T) va a oqim f, S dan T gacha qancha f kesib o'tadi? Intuitiv ravishda, bu S-dan T minusga qaytib kelgan har qanday oqim bo'lsa kerak. Va bu aniq.

F (C, T) bilan belgilangan C (S, T) kesmaning egri qiymati quyidagicha aniqlanadi:

Yana, agar oldingi misolni ko'rib chiqsak, quyida qayta ishlangan: f (S, T), qizil qirralarni tushirishdan tashqari, ko'k qirralarning ustiga yuborilgan qarz miqdori teng bo'ladi.

2-rasm

Imkoniyatlarni cheklash orqali f (u, v) ≤ c (u, v), ∀ (u, v) ∈ E. Ushbu faktdan va yuqorida (1) va (2) dan foydalanib, quyidagi lemma hosil bo'lishini bilib olamiz: