Prim algoritmi Kraskal algoritmi



Download 244,82 Kb.
bet1/2
Sana21.05.2022
Hajmi244,82 Kb.
#606144
  1   2
Bog'liq
Prim algoritmi Kraskal algoritmi


5-MA’RUZA.
Mavzu: Graflar ustida algoritmlar
Reja:

  1. Minimal narxli daraxtlar skleti

  2. Prim algoritmi

  3. Kraskal algoritmi

Kalit so’zlar: Graf, minimal narxli daraxt, Prim algoritmi, Kraskal algoritmi
Minimal narxli daraxtlar skleti. G=(V, Ye) – bog’langan graf bo’lsin, unda har bir (v, w) qirra qirralar narxi deb ataluvchi c(v, w) raqam bilan belgilangan. G grafning daraxtlar skleti deb, shu grafning barcha V tugunlarini o’z ichiga olgan bo’sh daraxtga aytiladi. Daraxtlar skleti narxi shu daraxtga kiruvchi barcha qirralar yig’indisi sifatida hisoblanadi. Biz minimal narxli daraxtlar skletini topish masalasini ko’ramiz.
Misol. 1-rasmda graf va uning minimal narxli daraxtlar skleti keltirilgan.

1-rasm. Graf va uning daraxtlar skleti
Minimal narxli daraxtlar skletiga tipik misol qilib, kommunikasion tarmoqlarni olish mumkin. Bu yerda graf tugunlari shaharlarni, qirra – esa shaharlar orasida bo’lishi mumkin bo’lgan kommunikasion chiziqlar, qirralar narxini kommunikasoin liniyalarning narxi sifatida qarash mumkin. Bu holda minimal narxli daraxtlar skleti barcha shaharlarni birlashtiruvchi minimal narxli kommunikasion tarmoqlarni ifodalaydi.
- Tarmoqda ma’lumotni tarqatish uchun daraxtlar shakllantiriladi.
- uylar o’rtasida aloqa kabelini tortish masalasi (qirra narxi – uylar orasiga ketadigan kabel narxi).
- Ethernet standarti uchun sikllarni oldini oladigan Spanning Tree Protocol.
Prim algoritmi.
Ushbu algoritm Robert Prim tomonidan 1957 yili ishlab chiqilgan. Ungacha 1930 yili chex matematigi Voytek Yarnik (Vojtěch Jarník) tomonidan, keiynroq 1959 yilda Edgar Deykstra (Edsger Dijkstra) tomonidan ishlab chikilgan.
Minimal narxli daraxtlar skletini qurishning ikkita keng tarqalgan usuli mavjud. Ulardan biri Prim algoritmi. Bu algoritmda daraxtlar skleti «o’sadigan» ("vыrastayet") U qirralar to’plami quriladi. V={1, 2,..., n} bo’lsin. Avval U={1} bo’ladi. Algoritmning har bir qadamida minimal narxli qirra topiladi, undan keyin v qirra V\U to’plamdan U to’plamga o’tkaziladi. Bu jarayon U to’plam V to’plamga teng bo’lguncha takrorlanadi.
Misol





Download 244,82 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish