yo'naltirilmagan graflar

PPTX 20 sahifa 249,2 KB Bepul yuklash

20 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 249,2 KB

Fayl turi PPTX

Sahifalar 20

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 20

11-ma'ruza yo'naltiril magan graflar 11-ma'ruza yo'naltiril magan graflar reja 1. yo'naltirilmagan graflar. 2. yo'nalishi aniqlanmagan daraxtlarni ko'ruvdan o'tkazish algoritmi. 3. minimal narxli daraxtlar skeleti. yo'naltirilmagan graflar yo'naltirilmagan graf g=(v, e) – bu tugunlar va ularni birlashtirib turuvchi yoylar dan tashkil topgan tuzilma xisoblanadi. undagi ixtiyoriy yoy teskarisi bilan teng va u yo'naltirilmagan yoy deyiladi. agar bo'lsa, u xolda u va v tugunlar qo'shni deyiladi va e yoy esa intsident deyiladi. tugunlarning chiqish darajasi deb u bilan qo'shni tugunlar soniga aytiladi. chiqish darajasi 0 ga teng bo'lgan tugunlar izolyatsiyalangan tugun deyiladi. yo'naltirilgan graflarda ilmoqli yoy bo'lishi mumkin, yo'naltirilmagan graflarda esa bunday yoy bo'lmaydi. yo'nalishi aniqlanmagan daraxtlarni ko'ruvdan o'tkazish algoritmi grafni ko'rikdan o'tkazish (graph traversal) – bu berilgan tugundan boshlab barcha tugunlarni ko'rib chiqish protsedurasidir. ikkita usuli mavjud: tubiga qarab(depth-first search – dfs) eniga qarab(breadth-first search – bfs) . yo'naltirilmagan graflarni ko'ruvdan o'tkazishda ma'lumotlarni saqlash uchun bironta konteyner, navbat yoki stekdan foydalaniladi …

2 / 20

'ladi, agar xar bir to'g'ri yoylarni belgilab olinsa. 1 2 3 4 5 6 7 8 1 navbat: 1 2 1 1 4 5 5 2 3 4 5 6 7 8 4 2 3 5 7 6 8 tubiga qarab ko'rishda stek qo'llanilishi agar oraliq tuzilma sifatida stek qo'llanilsa, grafni tubiga qarab ko'riladi. 1 2 3 4 6 7 5 8 graf: 1 5 8 7 6 4 3 2 tubiga qarab qo'ruv daraxtini yaratsa xam bo'ladi, agar xar bir to'g'ri va teskari yoylarni belgilab olinsa. 1 2 3 4 5 6 7 8 1 1 1 5 5 7 6 4 4 3 1 stek: 2 3 4 5 6 7 8 minimal narxli daraxtlar skeleti minimal narxli skeletni topish masalasi ko'pincha quyidagicha xolatlarda uchraydi: masalan, n ta shaxar mavjud va ular orasiga yo'llarni shunaqa qurish kerakki, istalgan shaxardan ixtiyoriy boshqasiga bevosita yoki bilvosita borish mumkin bo'lsin va …

3 / 20

$(u,v) yoylar v\u tanlanmagan tugunlar izox {} {a,b,c,d,e,f,g} dastlab daraxt tugunlar to'plami bo'sh {d} (d,a) = 5 v (d,b) = 9 (d,e) = 15 (d,f) = 6 {a,b,c,e,f,g} ilk tugun sifatida d olindi. unga tegishli yoylar a,b,e,f tugunlarga olib boradi. ularning minimal yoyligini tanlaymiz. ya'ni a {a,d} (d,b) = 9 (d,e) = 15 (d,f) = 6 v (a,b) = 7 {b,c,e,f,g} {a,d,f} (d,b) = 9 (d,e) = 15 (a,b) = 7 v (f,e) = 8 (f,g) = 11 {b,c,e,g} {a,b,d,f} (b,c) = 8 (b,e) = 7 v (d,b) = 9 tsikl (d,e) = 15 (f,e) = 8 (f,g) = 11 {c,e,g} (d,b)yoy tanlansa xalqa xosil bo'ladi. shuning uchun uni tanlay olmaymiz. {a,b,d,e,f} (b,c) = 8 (d,b) = 9 tsikl (d,e) = 15 tsikl (e,c) = 5 v (e,g) = 9 (f,e) = 8 tsikl (f,g) = 11 {c,g} {a,b,c,d,e,f} (b,c) = 8 tsikl (d,b) = 9 tsikl (d,e) = 15 …$

4 / 20

bittasi tanlanadi., masalan ad keyingi kichikroq yoy 5 - ce. yoyi xisoblanadi. uni tanlanganda xalqa xosil bo'lmaydi. vazni 6 ga teng bo'lgan df yoyi tanlanadi. algoritmga misol tasvir izox ab va be yoylar vazni 7. ab ni ixtiyoriy tanlaymiz, bd yoy tanlanmaydi, chunki abd xalqa xosil bo'lishi mumkin. vazni 7 bo'lgan be yoy tanlanadi. bc yoy olinmaydi, chunki bce xalqa, de xam olinmaydi, chunki deba xalqa, fe xam olinmaydi, chunki febad xalqa. vazni 9 bo'o'lgan eg yoy qo'shiladi va algoritm tugullanadi. minimal narxli daraxt aniqlandi. kruskal algoritm samaradorligi algoritm boshlanishidan avval yoylarni vazni bo'yicha saralab chiqish talab etiladi. buning uchun o(e × log(e)) vaqt talab etiladi. qolgan vaqt yoylarni daraxtga qo'shish uchun sarflanadi. kruskal algoritmida vaqt asosan saralashga sarflanishi sababli samaradorlikni o(e × log(e)) deb olish mumkin. mustaqil ish: boruvka algoritmi va samaradorligi nazorat savollari: 1. yo'naltirilmagan graf tushunchalari, qo'shnilar, intsident yoy, xalqa 2. graflarni ko'ruvdan o'tkazish algoritmlari va dasturini …

5 / 20

Ko'proq o'qimoqchimisiz?

Barcha 20 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"yo'naltirilmagan graflar" haqida

11-ma'ruza yo'naltiril magan graflar 11-ma'ruza yo'naltiril magan graflar reja 1. yo'naltirilmagan graflar. 2. yo'nalishi aniqlanmagan daraxtlarni ko'ruvdan o'tkazish algoritmi. 3. minimal narxli daraxtlar skeleti. yo'naltirilmagan graflar yo'naltirilmagan graf g=(v, e) – bu tugunlar va ularni birlashtirib turuvchi yoylar dan tashkil topgan tuzilma xisoblanadi. undagi ixtiyoriy yoy teskarisi bilan teng va u yo'naltirilmagan yoy deyiladi. agar bo'lsa, u xolda u va v tugunlar qo'shni deyiladi va e yoy esa intsident deyiladi. tugunlarning chiqish darajasi deb u bilan qo'shni tugunlar soniga aytiladi. chiqish darajasi 0 ga teng bo'lgan tugunlar izolyatsiyalangan tugun deyiladi. yo'naltirilgan graflarda ilmoqli yoy bo'lishi mumkin, yo'naltirilmagan graflarda esa bunday yoy bo'lmaydi. yo'nalishi...

Bu fayl PPTX formatida 20 sahifadan iborat (249,2 KB). "yo'naltirilmagan graflar"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: yo'naltirilmagan graflar PPTX 20 sahifa Bepul yuklash Telegram