O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VА KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
|
|
ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНА АЛ-ХОРАЗМИ, МИНИСТЕРСТВО ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И РАЗВИТИЯ СВЯЗИ РЕСПУБЛИКИ УЗБЕКИСТАН
|
TELEKOMMUNIKATSIYALAR FAKULTETI
Алгоритм лойиҳалаш
MUSTAQIL ISH
Mavzu: Graflarni eng arzon tayanch daraxtini qurishda Kruskal xasis algoritmi.
Topshirdi: Tulyaganov B.T.
Guruh: 044-20
Qabul qildi:
Toshkent – 2023
Reja :
1) Minimal daraxt daraxti
2) Kruskal Algoritmi
3) Kruskal algoritmini c++ da amalga oshirish
Minimal daraxt daraxti
Grafning umurtqa pog'onasi daraxt deb ataladi, undan ba'zi qovurg'alarni olib tashlash orqali olish mumkin. Grafda bir nechta magistral daraxtlar bo'lishi mumkin va ko'pincha ularning ko'pi bor.
Rasmda panjara shaklidagi grafikning magistral daraxtlaridan biri (qirralari ko'k rangda ta'kidlangan) ko'rsatilgan.
Og'irlashtirilgan grafikalar uchun magistral daraxtning og'irligi tushunchasi mavjud bo'lib, u magistral daraxtga kiritilgan barcha qirralarning og'irliklari yig'indisi sifatida aniqlanadi. Undan tabiiy ravishda minimal skelet daraxti - minimal mumkin bo'lgan vaznga ega bo'lgan daraxt daraxti tushunchasi kelib chiqadi.
Grafning minimal magistral daraxtini topish uchun ikkita asosiy algoritm mavjud: Prim algoritmi va Kruskal algoritmi. Ularning ikkalasi ham murakkablikka ega O(M log N), shuning uchun, ulardan birini tanlash sizning shaxsiy xohishingizga bog'liq. Ushbu ma'ruzada biz ikkalasini ham tahlil qilamiz.
|
