grafa o`tish algoritimi

DOCX 1 стр. 225,8 КБ Бесплатная загрузка

1 стр.

FaylHub.uz

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

Размер 225,8 КБ

Тип файла DOCX

Страницы 1

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

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

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

1 / 1

grafa o`tish algoritimi reja: 1. asosiy tushuncha 2. grafa o`tish algoritimi 3. floyd algoritmi 4. deykstra algoritmi asosiy tushuncha. qandaydir masalani xal etishga kirishishdan avval buning uchun eng yaxshi uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi. boshqacha qilib aytganda, biz doimo maqsadi ba’zi bir zaruriy natijaga erishishdan iborat, amallar ketma-ketligi bilan berilgan turli-tuman qoidalarga duch kelamiz. bunday amallarning ketma-ketligi algoritm deb ataymiz. matematikada algoritmning murakkabligi, xal etish masalalari va ularni ishlab chiqish prinsiplarini o‘rganadigan maxsus “algoritmlar nazariyasi” bo‘limi xam mavjud. algoritmlar nazariyasi – algoritmlarning umumiy xossalari, qonuniyatlari va ularni tasvirlanishining turli-tuman formal modellarini o‘rganish bilan shug'ullanadi. algoritm tushunchasini formallashtirish asosida ularning samaradorligi taqqoslash, ularning ekvivalentligi tekshirish, qo‘llanilish sohasini aniqlash mumkin. graflar nazariyasining asosiy masalasi berilgan nuqtalar va ularni tutashtiruvchi chiziqlarning xossalaridan tashkil topadi. bunday talqinda chiziqlarnig to’g’ri chiziq yoki kesma, yoylardan yoki egri chiziqlardan iborat bo’lishi hamda bu chiziqlar qaerda joylashishi, uzun yoki qisqa bo’lishi muhim emas. shunisi muhimki …

2 / 1

ri ham topildi. l.eyler tomonidan e’lon qilingan tarixiy ilmiy ish yuz yildan kuproq vaqt mobaynida graflar nazariyasi bo’yicha yagona ilmiy ish bo’lib keldi. xix-asrning o’rtalarida graflar nazariyasi bilan bog’liq tadqiqotlar g.kirxgof (1924–1887, olmon fizigi) va a.keli (1821–1895, ingliz matematigi) ishlarida paydo bo’ldi. “graf” iborasi d.kyonig (1884–1944, venger matematigi) tomonidan 1936– yilda graflar nazariyasiga bag’ishlangan dastlabki darsliklarda uchraydi. graflar nazariyasi bo’yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo’llaniladi. ulardan ba’zilari quyidagilar: boshqotirmalarni hal qilish; qiziqarli o’yinlar; yo’llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish va hakazo. avvalo grafning abstrakt matematik tushuncha sifatidagi ta’rifini keltiramiz. ixtiyoriy nuqtalarning qandaydir usulda bog’lanishidan tashkil topgan to’plamni qaraymiz. ushbu to’plamni uchlar to’plami va uning elementlarini esa uchlar deb ataymiz. to’plamning va elementlaridan tuzilgan ko’rinishidagi barcha juftliklar to’plamini (to’plamning o’z-o’ziga dekrat ko’paytmasini) deb belgilaymiz. graf deb shunday juftlikga aytiladiki, bu erda va ko’rinishidagi juftliklar bo’lib, to’plamning elementlaridan tuzilgandir. grafni lotin alifbosining harfi bilan belgilaymiz. grafga ta’rif …

3 / 1

xirgi uch deb hisoblanadi. shuningdek qirrani uchdan chiquvchi va uchga boruvchi qirra deyiladi. qirra yo’naltirilgan bo’lgan holda ham, yo’naltirilmagan holda ham qirra va uchlarga intsidient deb ataladi. grafni yo’naltirilmagan deyiladi, agar uning barcha qirralari yo’naltirilmagan bo’lsa (1.1.a–rasm), yo’naltirilgan deyiladi agar barcha qirralari yo’naltiriligan bo’lsa (1.1.b– rasm). 1.1.a–rasm 1.1.b–rasm. ham yo’naltirilgan, ham yo’naltirilmagan qirralarga ega bo’lgan graf aralash graf deyiladi. misol sifatida, shaxarning xaritasini graf sifatida olsak, unda ko’chalarni qirra deb, chorrahalarni esa uchlar sifatida olish mumkin. bunda faqat bir tomonlama harakat mavjud ko’chalarni yo’nalishga ega qirra deb olsak, u holda ikki tomonlama harakat mavjud ko’chalarni hech qanday yo’nalish orqali belgilab bo’lmaydi. hech bir qirraga intsidient bo’lmagan uch yakkalangan uch deyiladi. agar grafning ikkita uchini tutashtiruvchi qirra bor bo’lsa, u holda bunday uchlar qo’shni uchlar deyiladi, aks holda esa qo’shni bo’lmagan uchlar deyiladi.faqat yakkalangan uchlardan tashkil topgan grafni nol graf deyiladi va orqali belgilanadi. ikkita chetki ya’ni boshlang’ich va oxirgi qirralari …

4 / 1

lan belgilanadi. ravshanki, grafning qirralar soni ta bo’ladi. grafni tekislikda tasvirlaganda qirralarning barcha kesishish nuqtalari uchlardan iborat bo’lsa bunday graf tekis graf deyiladi (1.5–rasm). 1.4–rasm 1.5–rasm ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni va qirralar soni ga qarab belgilanadi va bu holda grafni graf deb ataymiz. agar va graflarning uchlari to’plamlari, va to’plamlar orasida uchlarning qo’shnilik munosabatini saqlaydigan o’zaro bir qiymatli moslik o’rnatilgan bo’lsa, u holda va graflar izomorf graflar deb ataladi (1.4–rasm). barcha izomorf graflar bir xil hossalarga ega bo’ladi. bog’lamli yo’naltirilmagan tsiklga ega bo’lmagan graf daraxt deyiladi. hususiy holda daraxt sirtmoq va karrali qirralarga ega bo’lmaydi. teorema 1.1. daraxtda ixtiyoriy ikki uch yagona zanjir bilan bog’langan bo’ladi. lokal darajalar. agar grafni uni tashkil etuvchi qirralari soni sanoqli bo’lsa, chekli graf, aksincha bo’lsa, cheksiz graf deb ataymiz. yo’naltirilmagan graf bo’lsin. bitta uchga intsidient bo’lgan qirralar soni uning lokal darajasi deyiladi va uni (1.2) kabi belgilaymiz. biror uchning …

5 / 1

(1.3) ga ko’ra esa (1.5) (1.4) formuladan ko’rinib turibdiki, chap tomon har doim juft son bo’ladi. yuqoridagi formulalardan ko’rish mumkinki, yo’naltirilmagan grafda barcha uchlar lokal darajalar yig’indisi qirralar sonining ikki baravariga teng juft son bo’ladi, chunki qirralarni sanaganda har bir qirra o’zi intsidient bo’lgan uchlarda ikki marta qatnashadi. shunga ko’ra asrdayoq l.eyler tomonidan quyidagicha tasdiq isbotlangan. lemma–1. ixtiyoriy yo’naltirilmagan grafda barcha uchlar darajalari yig’indisi qirralar sonining ikki baravariga teng. 2.2 . eng qisqa yo’llar masalalarining turlari. yo’l tarmoqlari atlasi (karta) qismi berilgan bo’lib, undan a va b nuqtalar orasidagi “eng yahshi” marshrutni topish kerak bo’lsin. “eng yahshi” marshrutni ko’p faktorlar belgilashi mumkin, masalan, tezlik cheklangan holda marshrutni o’tish vaqti, o’tish kerak bo’lgan shaharlar soni va boshqalar. biz masalani eng qisqa yo’llar faktori bo’yicha yechamiz. masalaning modeli turlar yordamida tuziladi. uzluksiz g turni har bir qirrasiga uning uzunligiga teng qiymat berilgan ko’rinishida tuzamiz. bunday turda masofa qirralar yig’indisiga teng bo’ladi. masalaning …

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

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

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

О "grafa o`tish algoritimi"

grafa o`tish algoritimi reja: 1. asosiy tushuncha 2. grafa o`tish algoritimi 3. floyd algoritmi 4. deykstra algoritmi asosiy tushuncha. qandaydir masalani xal etishga kirishishdan avval buning uchun eng yaxshi uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi. boshqacha qilib aytganda, biz doimo maqsadi ba’zi bir zaruriy natijaga erishishdan iborat, amallar ketma-ketligi bilan berilgan turli-tuman qoidalarga duch kelamiz. bunday amallarning ketma-ketligi algoritm deb ataymiz. matematikada algoritmning murakkabligi, xal etish masalalari va ularni ishlab chiqish prinsiplarini o‘rganadigan maxsus “algoritmlar nazariyasi” bo‘limi xam mavjud. algoritmlar nazariyasi – algoritmlarning umumiy xossalari, qonuniyatlari va ularni tasvirlanishining turli-tuman formal modellarini o‘rganish bilan s...

Этот файл содержит 1 стр. в формате DOCX (225,8 КБ). Чтобы скачать "grafa o`tish algoritimi", нажмите кнопку Telegram слева.

Теги: grafa o`tish algoritimi DOCX 1 стр. Бесплатная загрузка Telegram