graflar

PPT 29 стр. 2,5 МБ Бесплатная загрузка

29 стр.

FaylHub.uz

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

Размер 2,5 МБ

Тип файла PPT

Страницы 29

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

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

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

1 / 29

slayd 1 © tuit, kafedra spp 9-mavzu: graflar. uning ko'rinishlari va ustida amal bajarish algoritmlari reja: asosiy tushunchalar va graf turlari graflarni ifodalash usullari graflarni ko'ruvdan o'tkazish eng qisqa yo'lni aniqlash masalasi * © tuit, kafedra spp asosiy tushunchalar va graf turlari graf - bu murakkab chiziqsiz ko'pbog'lamli dinamik tuzilma bo'lib, murakkab ob'ektlarning xususiyatlari va munosabatlarini aks ettiradi. matematik nazariyada va informatikada graf — bu tugunlar(uchlar)dan iborat bo'lgan bo'sh bo'lmagan to'plam va tugunlarni birlashtiruvchi yoylar majmuidir. ob'ektlar tugun yoki graf uzellari ko'rinishida va munosabatlar yoy yoki yo'naltirilgan qirralar kabi ifodalanadi. «graf» tushunchasini 1-marta 1936 yil vengriya matematigi denni kyonig kiritgan. lekin graflar nazariyasi bo'yicha 1-ish leonard eylerga tegishli bo'lgan va u 1736 yilda bajarilgan edi. © tuit, kafedra spp graf turlari ixtiyoriy tugundan boshqa bironta tugunga murojaat mavjud bo'lsa, u xolda bunday graf yo'naltirilmagan graf deyiladi (1-rasm). agar graf tugunlari o'zaro bog'langan bo'lsa-yu, lekin bu yoylar orqali munosabat faqat bir …

2 / 29

ugunlar ketma-ketligidir. yo'l: (10, 8, 3, 5) © tuit, kafedra spp graflarni ifodalash usullari xalqa(cycle) – bu boshi va oxiri tutashuvchi tugundan iborat yo'l xisoblanadi: (4, 6, 7, 8, 3, 4) tugun darajasi (vertex degree) – bu undan chiquvchi yoylar soni xisoblanadi. deg(7) = 2, deg(1) = 3 © tuit, kafedra spp g(v, e) grafda uning barcha tugunlari darajalari yig'indisi – juft , grafning qirralari sonining ikkilanganiga teng. tugunlar juft(toq) deyiladi, agar ularning darajalari – juft(toq) qiymatli bo'lsa. ixtiyoriy grafda toq tugunlar soni – juft bo'ladi toq sonli toq tugunlardan iborat grafni chizib bo'lmaydi. © tuit, kafedra spp graflarni ifodalash usullari to'liq graf (complete graph) – bu istalgan tugunlari qo'shni bo'lgan graf xisoblanadi. (barcha tugunlar o'zaro birlashtirilgan) grafni to'ldiruvchisi bu aynan bir tugunlar va aynan bir qirralardan tashkil topgan va mavjud grafni to'liq bo'lishini ta'minlovchi grafga aytiladi. grafni to'ldiruvchisi to'liq, yo'naltirilmagan grafda qirralar soni: a b c d a b …

3 / 29

aydigan masofani aniqlash algoritmi © tuit, kafedra spp deykstra algoritmi vaznga ega graflarda a punktdan b punktgacha bo'lgan eng qisqa masofani aniqlash algoritmini ko'rib chiqamiz. © tuit, kafedra spp deykstra algoritmi g = (v, e) graf berilgan bo'lsin. undagi barcha yoylar manfiy bo'lmagan vaznga ega. (barcha (u, v)ϵe tugunlar uchun (u, v) ≥ 0 ). a tugundan boshlab grafdagi boshqa tugunlargacha bo'lgan qisqa masofalarni aniqlash talab etiladi. deykstra algoritmida a tugundan boshlab yoylar orqali xar bir tugungacha bo'lgan vaznlar yig'indisi xisoblanadi va kam vaznga ega bo'lgan qiymatlar qisqa yo'l sifatida tugunda belgilab boriladi.algoritm barcha tugunlar ko'rib chiqilganda to'xtatiladi. © tuit, kafedra spp deykstra algoritmi-initsializatsiya dastlab a tugundan boshqa tugunlargacha bo'lgan masofa vaznlarini cheksiz ∞ deb tugunda belgilab olamiz, ya'ni metka qo'yib chiqamiz. bu xali a tugundan ko'rilayotgan tugungacha bo'lgan qisqa masofa aniqlanmaganligini bildiradi. a tugun metkasini 0 deb belgilaymiz. barcha tugunlar xali tashrif buyurilmagan deb olinadi. © tuit, kafedra spp …

4 / 29

$buyurilgan tugun sifatida belgilanadi 2-qadam 1 – 2: 7 1 – 3: 9 1 – 6:11 1 – 4: 20 1 – 5:20 unknown-0.unknown o-® yee (1, 2) u (2, 1) — ogho u toke pe6po (1, 3) u (3, 1) — pashble ayru! 4 g å = = n i i m v 1 2 ) deg( n(n— 1) \e| = o(v i?) p=®=09, p>05 76 le| = o(iv|) 27 d=—= 0.33, d<05 76 _ 2m ~ n(n —1)$

5 / 29

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

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

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

О "graflar"

slayd 1 © tuit, kafedra spp 9-mavzu: graflar. uning ko'rinishlari va ustida amal bajarish algoritmlari reja: asosiy tushunchalar va graf turlari graflarni ifodalash usullari graflarni ko'ruvdan o'tkazish eng qisqa yo'lni aniqlash masalasi * © tuit, kafedra spp asosiy tushunchalar va graf turlari graf - bu murakkab chiziqsiz ko'pbog'lamli dinamik tuzilma bo'lib, murakkab ob'ektlarning xususiyatlari va munosabatlarini aks ettiradi. matematik nazariyada va informatikada graf — bu tugunlar(uchlar)dan iborat bo'lgan bo'sh bo'lmagan to'plam va tugunlarni birlashtiruvchi yoylar majmuidir. ob'ektlar tugun yoki graf uzellari ko'rinishida va munosabatlar yoy yoki yo'naltirilgan qirralar kabi ifodalanadi. «graf» tushunchasini 1-marta 1936 yil vengriya matematigi denni kyonig kiritgan. lekin graflar n...

Этот файл содержит 29 стр. в формате PPT (2,5 МБ). Чтобы скачать "graflar", нажмите кнопку Telegram слева.

Теги: graflar PPT 29 стр. Бесплатная загрузка Telegram