Toshpulatov Jasurbekning "Algoritmlarni loyihalash"

Tarmoqlar va chegaralar usuli:
Faraz qilaylik C=[c_ij] matritsaning elementlari savdogarni i shahardan j shaharga borishidagi xarajatlari bo`lsin. Har bir shahardan bir martadan o`tuvchi n ta (i, j ) tartiblashtirilgan juftligini t sikl deb ataymiz.
t=[(i₁,j₁),( i₂,j₂),...,( i_n-1,j_n-1),( i_n,j_n)
Har bir ( i, j ) juftlik marshrutning kommunikatsiyasini tashkil
qiladi. U holda t sikl uchun marshrutning elementlari kommunikatsiyalar
bo`yicha quyidagi yig`indi orqali aniqlanadi:

Agar C matritsaninig i nchi qator elementlaridan yoki j nchi ustun elementlaridan ularning eng kichigini ayirsak, matritsaning harbir qatorida va ustunida hech bo`lmasa bittadan nol hosil bo`ladi va yangi hosil bo`ladigan matritsa C matritsaning xossalariga ega bo`ladi. Yangi matritsa keltirilgan matritsa deyiladi. C matritsaning elementlari nomanfiyligi aniq. Keltirilgan matritsani hosil qilish uchun tanlanadigan element eng kichik element bo`lgani uchun uning elementlari ham nomanfiydir. Eng kichik elementlar yig`indisini h^k bilan belgilaymiz, k –

keltirishning tartib nomeri. Keltirilgan matritsa uchun t siklidagi
harajatlarni z1(t) bilan belgilasak z(t)= h¹+z¹(t) ifoda hosil bo`ladi. Bu
yerdagi 1 h berilgan matritsa uchun t sikldagi harajatlarning quyi
chegarasi deyiladi. Hamma sikllar to`plamini o`zaro kesishmaydigan qism to`plamlarga ajratishni uchlarga ega bo`lgan daraxt ko`rinishida tasvirlash mumkin. Uchlarga bir-biriga o`tish mumkin bo`lgan ( i, j ) va mumkin bo`lmagan (i, j) shaharlar juftliklarini joylashtiriladi. (i, j) dan o`tuvchi shox i shahardan j shaharga o`tish mumkin bo`lmagan barcha
marshrutlarni o`z ichiga oladi. Masalan, (k, l) uchdan o`tuvchi shox i
shahardan j ga o`tish mumkin bo`lgan barcha marshrutlarni o`z ichiga
oladi, lekin k dan l ga o`tish mumkin emasligini ko`rsatadi.