Бажарди: Yusufjonov O’tkir Toshkent – 2023 Ketma-ketliklar, to‘plamlar, daraxtlar, graflarni ifodalash usullari

edgeCount=1

while edgeCount<=Е and includedCount<=N-1 do

parent1=FindRoot(edge[edgeCount].start)

parent2=FindRoot(edge[edgeCount].end)

if parent1/parent2 then

edge[edgeCount] ni MOD ga qo’shish

includedCount= includedCount=1

Union(parent1,parent2)

Enf if

edgeCount= edgeCount+1

end while
Algoritmning asosiy sikli edgeCount o’zgaruvchisining qiymati grafdagi tomonlar soni bilan tеnglashishi yoki includedCount o’zgaruvchisining qiymati MOD ni shakllantirish uchun еtarlicha tomonlar qo’shilganini ko’rsatgunga qadar ishlaydi (N tugunli garfning MOD i N-1 ta tomonga ega bo’lishi kеrak) .

Bog'langan og'irlikdagi yo'naltirilmagan grafikdagi minimal kengayuvchi daraxt (yoki minimal oraliq daraxt ) bu grafikning mumkin bo'lgan minimal og'irlikka ega bo'lgan kengayuvchi daraxti bo'lib, bu erda daraxtning og'irligi uning qirralari og'irliklarining yig'indisidir.
Kruskal algoritmi og'irlikdagi bog'langan yo'naltirilmagan grafikning minimal oraliq daraxtini qurish uchun samarali algoritmdir . Shuningdek, algoritm Shtayner muammosi uchun ba'zi bir taxminlarni topish uchun ishlatiladi ^[1] .
Algoritm 1956 yilda Jozef Kraskal ( ing. ) tomonidan tasvirlangan , bu algoritm 1926 yilda Otakar Boruvka ^[en] tomonidan taklif qilingan Boruvka algoritmi bilan deyarli bir xil .
Dastlab, joriy qirralar to'plami bo'sh qilib o'rnatiladi. Keyin, iloji bo'lsa, quyidagi operatsiya amalga oshiriladi: mavjud to'plamga qo'shilishi unda tsikl paydo bo'lishiga olib kelmaydigan barcha qirralardan minimal og'irlikning chekkasi tanlanadi va allaqachon mavjud to'plamga qo'shiladi. . Bunday chekkalar qolmaganda, algoritm tugallanadi. Berilgan grafikning barcha cho'qqilari va topilgan qirralari to'plamini o'z ichiga olgan pastki grafigi uning minimal og'irligi bo'lgan daraxtdir . Algoritmning batafsil tavsifini adabiyotlarda topish mumkin
Kruskal algoritmi haqiqatan ham minimal vaznli daraxtni topadi, chunki bu grafik matroid uchun Rado-Edmonds algoritmining ^[3] alohida holati bo'lib , mustaqil to'plamlar qirralarning asiklik to'plamidir.

Ustun asos elementlari (B)

Dastlabki bosqichda biz aniqlagan asosiy elementlarni jadvalga o'tkazamiz:
B₁ = x₄;
B2 = x 5;
B3 = x 6;
Cb ustun elementlari
Ushbu ustundagi har bir katak mos keladigan qatordagi asosiy o'zgaruvchiga mos keladigan koeffitsientga teng.
Cb₁ = 0;
Cb₂ = 0;
Cb₃ = 0;

Maqsad funksiyasi qiymati

Maqsad funksiyasining qiymatini elementlar bo'yicha Cb ustunini P ustuniga ko'paytirib, mahsulotlarning natijalarini qo'shib hisoblaymiz.
Maksimal qiymat _P = (Cb₁ * P₀₁) + (Cb₁₁ * P₂ + (Cb₂₁ * P₃ = (0 * 149) + (0 * 194) + (0 * 531) = 0;
Har bir boshqariladigan o‘zgaruvchi bo‘yicha ballarni o‘zgaruvchi ustunidagi qiymatni Cb ustunidagi qiymatga elementlar bo‘yicha ko‘paytirish, mahsulotlar natijalarini yig‘ish va shu o‘zgaruvchi yordamida ularning yig‘indisidan maqsad funksiya koeffitsientini ayirish yo‘li bilan hisoblaymiz.
Max_x1 = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1) ) - k_x1 = ((0 * 3) + (0 * 4) + (0 * 9) ) - 110 = -110;
Max_x2 = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2) ) - k_x2 = ((0 * 3) + (0 * 4) + (0 * 9) ) - 110 = -110;
Max_x3 = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3) ) - k_x3 = ((0 * 1) + (0 * 1) + (0 * 9) ) - 82 = -82;
Max_x4 = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4) ) - k_x4 = ((0 * 1) + (0 * 0) + (0 * 0) ) - 0 = 0;
Max_x5 = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5) ) - k_x5 = ((0 * 0) + (0 * 1) + (0 * 0) ) - 0 = 0;
Max_x6 = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6) ) - k_x6 = ((0 * 0) + (0 * 0) + (0 * 1) ) - 0 = 0;

Ustun asos elementlari (B)
Oldingi iteratsiyaning hisob-kitoblari natijalari uchun biz o'zgaruvchini x5 bazasidan olib tashlaymiz va uning o'rniga x1 ni qo'yamiz. Boshqa barcha hujayralar o'zgarishsiz qoladi.
Cb ustun elementlari
Ushbu ustundagi har bir katak mos keladigan qatordagi asosiy o'zgaruvchiga mos keladigan koeffitsientga teng.
Cb1 = 0;
Cb2 = 110;
Cb3 = 0;
O'zgaruvchan o'zgaruvchilarning qiymatlari va P ustuni
(Oldingi iteratsiya ma'lumotlari dastlabki ma'lumotlar sifatida olinadi)
Barcha kataklarni faqat asosga kiritilgan o'zgaruvchiga mos keladigan nol bilan to'ldiring:
(Ruxsat elementi o'zgarishsiz qoladi)
x1,1 = 0;
x3.1 = 0;
Biz ruxsat beruvchi elementi bo'lgan qatorni oldingi jadvaldan joriy jadvalga o'tkazamiz, uning qiymatlarini ruxsat beruvchi elementga elementlar bo'yicha ajratamiz:
Р2 = Р2 / х 2,1 _{= 194}/ 4 = 48,5;
х_2,1 = х_2,1 / х_2,1 = 4/4 = 1;
х_2,2 = х_2,2 / х_2,1 = 4/4 = 1;
х_2,3 = х_2,3 / х_2,1 = 1/4 = 0,25;
х_2,4 = х_2,4 / х_2,1 = 0/4 = 0;
х_2,5 = х_2,5 / х_2,1 = 1/4 = 0,25;
х_2,6 = х_2,6 / х_2,1 = 0/4 = 0;
Qolgan bo'sh katakchalar, ballar qatori va Q ustunidan tashqari, ruxsat elementiga nisbatan to'rtburchaklar usuli yordamida hisoblanadi:
P1 = (P1 * x_2,1) - (x_1,1 *P2) / x_2,1 = ((149 * 4) - (3 * 194)) / 4 = 3.5;
Р3 = (Р3 * х_2,1) - (х 3,1 * Р2) / х_2,1 = ((531 * 4) - (9 * 194)) / 4 = 94.5;
x_1,1 = ((x_1,1 * x_2,1) - (x_1,1 * x_2,1)) / x_2,1 = ((3 * 4) - (3 * 4)) / 4 = 0;
х_1,3 = ((х_1,3 * х_2,1) - (х_1,1* х_2,3)) / х_2,1 = ((1 * 4) - (3 * 1)) / 4 = 0.25;
х_1,4 = ((х_1,4* х_2,1) - (х_1,1* х_2,4)) / х_2,1 = ((1 * 4) - (3 * 0)) / 4 = 1;
х_1,5 = ((х_1,5* х_2,1) - (х_1,1* х_2,5)) / х_2,1 = ((0 * 4) - (3 * 1)) / 4 = -0.75;
х_1,6 = ((х_1,6 * х_2,1) - (х_1,1* х_2,6)) / х_2,1 = ((0 * 4) - (3 * 0)) / 4 = 0;
х_3,1 = ((х_3,1 * х_2,1) - (х_3,1* х_2,1)) / х_2,1 = ((9 * 4) - (9 * 4)) / 4 = 0;
х_3,3 = ((х_3,3 * х_2,1) - (х_3,1* х_2,3)) / х_2,1 = ((9 * 4) - (9 * 1)) / 4 = 6.75;
х_3,4 = ((х_3,4 * х_2,1) - (х_3,1* х_2,4)) / х_2,1 = ((0 * 4) - (9 * 0)) / 4 = 0;
х_3,5 = ((х_3,5* х_2,1) - (х_3,1* х_2,5)) / х_2,1 = ((0 * 4) - (9 * 1)) / 4 = -2.25;
х_3,6 = ((х_3,6 * х_2,1) - (х_3,1* х_2,6)) / х_2,1 = ((1 * 4) - (9 * 0)) / 4 = 1;
Maqsad funksiyasi qiymati
Maqsad funksiyasining qiymatini elementlar bo'yicha Cb ustunini P ustuniga ko'paytirib, mahsulotlarning natijalarini qo'shib hisoblaymiz.
maksimal qiymat _P = (Cb₁ * P₀₁) + (Cb₁₁ * P₂ + (Cb₂₁ * P₃ = (0 * 3.5) + (110 * 48.5) + (0 * 94.5) = 5335;

Cb₁ = 82; Cb₂ = 110; Cb₃ = 0;
х_2,3 = 0; х_3,3 = 0;
_Р1 =_Р1 / х_1,3 = 3,5 / 0,25 = 14;
х_1,1 = х_1,1 / х_1,3 = 0 / 0,25 = 0;
х_1,2 = х_1,2 / х_1,3 = 0 / 0,25 = 0;
х_1,3 = х_1,3 / х_1,3 = 0,25 / 0,25 = 1;
х_1,4 = х_1,4 / х_1,3 = 1 / 0,25 = 4;
х_1,5 = х_1,5 / х_1,3 = -0,75 / 0,25 = -3;
х_1,6 = х_1,6 / х_1,3 = 0 / 0,25 = 0;
Qolgan bo'sh katakchalar, ballar qatori va Q ustunidan tashqari, ruxsat elementiga nisbatan to'rtburchaklar usuli yordamida hisoblanadi:
P2 = (P2 * x_1,3) - (x 2,3 * P1) / x_1,3 = ((48.5 * 0.25) - (0.25 * 3.5)) / 0.25 = 45;
Р3 = (Р3 * х_1,3) - (х_3,3 * Р1) / х_1,3 = ((94.5 * 0.25) - (6.75 * 3.5)) / 0.25 = 0;
х_2,1 = ((х_2,1 * х_1,3) - (х_2,3* х_1,1)) / х_1,3 = ((1 * 0.25) - (0.25 * 0)) / 0.25 = 1;
х_2,2 = ((х_2,2 * х_1,3) - (х_2,3*х_1,2)) / х_1,3 = ((1 * 0.25) - (0.25 * 0)) / 0.25 = 1;
х_2,3 = ((х_2,3 * х_1,3) - (х_2,3* х_1,3)) / х_1,3 = ((0.25 * 0.25) - (0.25 * 0.25)) / 0.25 = 0;
х_2,5 = ((х_2,5 * х_1,3) - (х_2,3* х_1,5)) / х_1,3 = ((0.25 * 0.25) - (0.25 * -0.75)) / 0.25 = 1;
х_2,6 = ((х_2,6 * х_1,3) - (х_2,3* х_1,6)) / х_1,3 = ((0 * 0.25) - (0.25 * 0)) / 0.25 = 0;
х_3,1 = ((х_3,1 * х_1,3) - (х_3,3* х_1,1)) / х_1,3 = ((0 * 0.25) - (6.75 * 0)) / 0.25 = 0;
х_3,2 = ((х_3,2 * х_1,3) - (х_3,3*х_1,2)) / х_1,3 = ((0 * 0.25) - (6.75 * 0)) / 0.25 = 0;
х_3,3 = ((х_3,3 * х_1,3) - (х_3,3* х_1,3)) / х_1,3 = ((6.75 * 0.25) - (6.75 * 0.25)) / 0.25 = 0;
х_3,5 = ((х_3,5 * х_1,3) - (х_3,3* х_1,5)) / х_1,3 = ((-2.25 * 0.25) - (6.75 * -0.75)) / 0.25 = 18;
х_3,6 = ((х_3,6 * х_1,3) - (х_3,3* х_1,6)) / х_1,3 = ((1 * 0.25) - (6.75 * 0)) / 0.25 = 1;
maksimal qiymat  _P = (Cb₁ * P₀₁) + (Cb₁₁ * P₂ + (Cb₂₁ * P₃ = (82 * 14) + (110 * 45) + (0 * 0) = 6098;
Har bir boshqariladigan o‘zgaruvchi bo‘yicha ballarni o‘zgaruvchi ustunidagi qiymatni Cb ustunidagi qiymatga elementlar bo‘yicha ko‘paytirish, mahsulotlar natijalarini yig‘ish va shu o‘zgaruvchi yordamida ularning yig‘indisidan maqsad funksiya koeffitsientini ayirish yo‘li bilan hisoblaymiz.
Max_x1 = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1) ) - k_x1 = ((82 * 0) + (110 * 1) + (0 * 0) ) - 110 = 0;
Max_x2 = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2) ) - k_x2 = ((82 * 0) + (110 * 1) + (0 * 0) ) - 110 = 0;
Max_x3 = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3) ) - k_x3 = ((82 * 1) + (110 * 0) + (0 * 0) ) - 82 = 0;
Max_x4 = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4) ) - k_x4 = ((82 * 4) + (110 * -1) + (0 * -27) ) - 0 = 218;
Max_x5 = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5) ) - k_x5 = ((82 * -3) + (110 * 1) + (0 * 18) ) - 0 = -136;
Max_x6 = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6) ) - k_x6 = ((82 * 0) + (110 * 0) + (0 * 1) ) - 0 = 0;
Boshqariladigan o'zgaruvchilarning baholari orasida salbiy qiymatlar mavjud bo'lganligi sababli, joriy jadval hali optimal echimga ega emas. Shuning uchun biz bazaga eng kichik salbiy bahoga ega o'zgaruvchini kiritamiz.
Bazisdagi o'zgaruvchilar soni doimo doimiy bo'ladi, shuning uchun qaysi o'zgaruvchini bazadan olib tashlashni tanlash kerak, buning uchun biz Q ni hisoblaymiz.
Q ustunining elementlari P ustunidagi qiymatlarni asosga kiritilgan o'zgaruvchiga mos keladigan ustunning qiymatiga bo'lish yo'li bilan hisoblanadi:
Q1 = P1 / x_1,5 = 14 / -3 = -4,67;
Q2_{= P2 / x 2,5} = 45/1 = 45;
_{Q3 = P3 / x 3,5 = 0 / 18 = 0};

Javob:
F* = 12218

X* = (0; 0; 149)