yo'naltirilmagan graflar

PPTX 20 стр. 249,2 КБ Бесплатная загрузка

20 стр.

FaylHub.uz

Скачать через Telegram

Размер 249,2 КБ

Тип файла PPTX

Страницы 20

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

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

Хотите читать дальше?

Скачайте все 20 страниц бесплатно через Telegram.

Скачать полный файл

О "yo'naltirilmagan graflar"

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...

Этот файл содержит 20 стр. в формате PPTX (249,2 КБ). Чтобы скачать "yo'naltirilmagan graflar", нажмите кнопку Telegram слева.

Теги: yo'naltirilmagan graflar PPTX 20 стр. Бесплатная загрузка Telegram