minimal og`irlikdagi karkas daraxtlar qurish algoritmi

PPTX 34 sahifa 633,8 KB Bepul yuklash

34 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 633,8 KB

Fayl turi PPTX

Sahifalar 34

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 34

mavzu:grafdagi daraxtlar. grafning tayanch daraxti. minimal og’irlikdagi karkas daraxtlar qurish algoritmi. prim algoritmi. kruskal algoritmi. grafdagi daraxtlar. grafning tayanch daraxti. minimal og’irlikdagi karkas daraxtlar qurish algoritmi. prim algoritmi. kruskal algoritmi. ma’ruzachi: tojiyev ma’ruf reja: 1. grafdagi daraxtlar. 2.grafning tayanch daraxti 3. minimal og’irlikdagi karkas daraxtlar qurish algoritmi 4. prim algoritmi. kruskal algoritmi. keling, bir nechta atamalarga to’xtab o’taylik. graflar nazariyasi nuqtai nazaridan daraxt asiklik bog'langan grafdir. daraxtlar to'plami o'rmon (forest) deb ataladi. bog'langan grafning kengayuvchi daraxt - bu grafning barcha uchlarini o'z ichiga olgan va daraxt bo'lgan graf osti grafdir. grafning kengayuvchi o'rmoni - bu grafning barcha uchlarini (tugun) o'z ichiga olgan o'rmon. graf v va e ikkita to'plamdan iborat bo'lib, bunda v - chekli bo'sh bo'lmagan qirralar to'plami va e - chekli bo'sh bo'lmagan qirralar to'plami. qirralar grafdagi tugunlardan boshqa narsa emas. ikki qo'shni uchlari qirralar bilan birlashtirilgan. har qanday graf g = {v, e} sifatida belgilanadi. g = …

2 / 34

'ich nuqta sifatida ishlatiladigan ildiz deb ataladigan yagona qirra mavjud. daraxtlar ierarxik munosabatlarni modellashtirish uchun ishlatilishi mumkin, masalan, fayl tizimining tuzilishi yoki kompaniyaning tashkiloti. daraxtlar ikkilik yoki ikkilik bo'lmagan bo'lishi mumkin. ikkilik daraxtda har bir tugun ko'pi bilan ikkitadan bolaga ega bo'lsa, ikkilik bo'lmagan daraxtda har bir tugun istalgan sonli bolalarga ega bo'lishi mumkin. ikkilik daraxtlar izlash va saralash kabi muammolarni hal qilishda, shuningdek, ifodalarni ifodalash va daraxtlarni tahlil qilish uchun ishlatilishi mumkin. daraxt - bu bir yoki bir nechta tugunlarning cheklangan to'plamidir, shuning uchun - 1.ildiz deb ataladigan maxsus belgilangan tugun mavjud. 2.qolgan tugunlar n>=0 ajralgan t 1 , t 2 , t 3 , …, t n toʻplamlarga boʻlinadi, bunda t 1 , t 2 , t 3 , …, t n ildizning pastki daraxtlari deyiladi. daraxt tushunchasi quyidagi rasmda ifodalanadi. prim algoritmi yopuvchi daraxt - qoplama daraxti yo'naltirilmagan bog'langan grafikning pastki grafigi. minimal oraliq daraxt - minimal …

3 / 34

cha berilgan: birinchidan, biz tasodifiy tanlangan cho'qqi bilan mstni ishga tushirishimiz kerak. endi biz yuqoridagi bosqichdagi daraxtni yangi uchlari bilan bog'laydigan barcha qirralarni topishimiz kerak. topilgan qirralardan minimal chekkani tanlang va uni daraxtga qo'shing. minimal kenglikdagi daraxt hosil bo'lguncha 2-bosqichni takrorlang. prim algoritmining ilovalari - prim algoritmidan tarmoqni loyihalashda foydalanish mumkin. u tarmoq davrlarini yaratish uchun ishlatilishi mumkin. bundan tashqari, elektr simlarini yotqizish uchun ham foydalanish mumkin. prim algoritmiga misol keling, misol yordamida prim algoritmining ishlashini ko'rib chiqamiz. misol yordamida primerning algoritmini tushunish osonroq bo'ladi. aytaylik, vaznli grafik - 1-qadam - birinchidan, yuqoridagi grafikdan cho'qqini tanlashimiz kerak. keling, b ni tanlaymiz. 2-qadam - endi biz b cho'qqisining eng qisqa chetini tanlashimiz va qo'shishimiz kerak. b cho'qqisining og'irligi 10 bo'lgan b dan c gacha bo'lgan ikkita qirrasi va og'irligi 10 ga teng bo'lgan b dan d gacha bo'lgan ikkita qirrasi bor. qirralar orasida bd qirrasi bor. minimal vazn. shunday qilib, uni …

4 / 34

araxt cho‘qqisini va chekka cho‘qqisini bog‘laydigan “e” chekkasini tanlang. 4-qadam: tanlangan chekka va cho'qqilarni minimal kenglikdagi t daraxtiga qo'shing 5-qadam: chiqish prim algoritmining murakkabligi keling, prim algoritmining vaqt murakkabligini ko'rib chiqaylik. prim algoritmining ishlash vaqti grafik uchun ma'lumotlar strukturasidan foydalanishga va qirralarning tartiblanishiga bog'liq. quyidagi jadvalda ba'zi variantlar ko'rsatilgan vaqtning murakkabligi minimal chekka og'irligi uchun ishlatiladigan ma'lumotlar tuzilishi vaqtning murakkabligi qo'shnilik matritsasi, chiziqli qidiruv o(|v| 2 ) qo'shnilar ro'yxati va ikkilik to'p o(|e| log |v|) qo'shnilar ro'yxati va fibonachchi to'plami o(|e|+ |v| log |v|) prim algoritmini qo'shnilik matritsasi yoki qo'shnilik ro'yxatining grafik tasviri yordamida oddiygina amalga oshirish mumkin va minimal og'irlikdagi chekka qo'shish uchun og'irliklar qatorini chiziqli qidirish kerak bo'ladi. bu o(|v| 2 ) ish vaqtini talab qiladi. algoritmning ichki halqasida minimal og'irlik qirralarini topish uchun to'pni amalga oshirish orqali uni yanada yaxshilash mumkin. primer algoritmining vaqt murakkabligi o(e logv) yoki o(v logv), bu yerda e - raqam. qirralarning, v …

5 / 34

n ular doimo yo'naltirilgan ildiz tugun grafikda ildiz deb ataladigan yagona tugun yo'q. daraxtlarda ildiz (ota-ona) tugun deb ataladigan noyob tugun mavjud. loop shakllanishi tsikl hosil bo'lishi mumkin. hech qanday tsikl bo'lmaydi. o'tish grafiklarni o'tkazish uchun biz kenglik-birinchi qidiruv (bfs) va chuqurlik-birinchi qidiruv (dfs) dan foydalanamiz . biz daraxtni tartibda, oldindan buyurtma berish yoki buyurtmadan keyin o'tish usullaridan foydalangan holda kesib o'tamiz. ilovalar tarmoq grafigida eng qisqa yo'lni topish uchun ishlatiladi. o'yin daraxtlari, qaror daraxtlari uchun daraxt ishlatiladi. tugun munosabatlari grafikda tugunlar boshqa tugunlar bilan istalgan sonli ulanishga ega bo'lishi mumkin va ota-ona va bolalarning qat'iy munosabatlari mavjud emas. daraxtda har bir tugun (ildiz tugunidan tashqari) ota-ona tuguniga va nol yoki undan ortiq tugunlarga ega. odatda uchun ishlatiladi grafiklar odatda ijtimoiy tarmoqlar, transport tarmoqlari va kompyuter tarmoqlari kabi murakkab tizimlar yoki munosabatlarni modellashtirish uchun ishlatiladi. daraxtlar odatda fayl tizimlari, tashkilot sxemalari va oila daraxtlari kabi ierarxik tuzilishga ega bo'lgan ma'lumotlarni …

Ko'proq o'qimoqchimisiz?

Barcha 34 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"minimal og`irlikdagi karkas daraxtlar qurish algoritmi" haqida

mavzu:grafdagi daraxtlar. grafning tayanch daraxti. minimal og’irlikdagi karkas daraxtlar qurish algoritmi. prim algoritmi. kruskal algoritmi. grafdagi daraxtlar. grafning tayanch daraxti. minimal og’irlikdagi karkas daraxtlar qurish algoritmi. prim algoritmi. kruskal algoritmi. ma’ruzachi: tojiyev ma’ruf reja: 1. grafdagi daraxtlar. 2.grafning tayanch daraxti 3. minimal og’irlikdagi karkas daraxtlar qurish algoritmi 4. prim algoritmi. kruskal algoritmi. keling, bir nechta atamalarga to’xtab o’taylik. graflar nazariyasi nuqtai nazaridan daraxt asiklik bog'langan grafdir. daraxtlar to'plami o'rmon (forest) deb ataladi. bog'langan grafning kengayuvchi daraxt - bu grafning barcha uchlarini o'z ichiga olgan va daraxt bo'lgan graf osti grafdir. grafning kengayuvchi o'rmoni - bu grafning barcha ...

Bu fayl PPTX formatida 34 sahifadan iborat (633,8 KB). "minimal og`irlikdagi karkas daraxtlar qurish algoritmi"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: minimal og`irlikdagi karkas dar… PPTX 34 sahifa Bepul yuklash Telegram