Prim algoritmi Kraskal algoritmi



Download 261,7 Kb.
bet1/3
Sana31.12.2021
Hajmi261,7 Kb.
#252533
  1   2   3
Bog'liq
5-лекция


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.


Download 261,7 Kb.

Do'stlaringiz bilan baham:
  1   2   3




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