Mahmudova Dilnoza Avaz qizi guruh cal017 Variant №37


Download 249.86 Kb.
bet1/3
Sana05.06.2020
Hajmi249.86 Kb.
  1   2   3

Mahmudova Dilnoza Avaz qizi guruh CAL017

Variant № 37

  1. Ford va Falkerson teoremasi.

  2. Matritsalar bilan ishlash algoritmlari.

  3. Rekursiv algoritmlarning murakkabligini baxolashning asosi nimada?

Javoblar

1.Kompyutershunoslik va optimallashtirish nazariyasida maksimal oqim minimallashtirilgan kesish teoremada, oqim tarmog'ida, manbadan to quyilishiga oqadigan oqimning maksimal miqdori minimal kesishda qirralarning umumiy og'irligiga teng, ya'ni. qirralarning eng kichik massasi, agar ular olib tashlansa, suvni quyilishidan uzib qo'yadi.

Maksimal oqim minema teoremasi chiziqli dasturlar uchun ikki tomonlama teoremaning alohida holati bo'lib, Menger teoremasini va Kig-Egervari teoremasini olish uchun ishlatilishi mumkin.



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:

Download 249.86 Kb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2020
ma'muriyatiga murojaat qiling