graflar

DOCX 7 sahifa 240,9 KB Bepul yuklash

7 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 240,9 KB

Fayl turi DOCX

Sahifalar 7

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 7

6-laboratoriya mashg’uloti graflar. umumiy ma’lumotlar graf - bu abstrakt obyekt bo’lib, uchlar to'plami (tugunlar) va qirralarning to'plami - uchlar juftliklari orasidagi bog'lanishlardan tashkil topadi (ulanishlar). graf mavzusi juda keng. graflar diskret matematikaning o'rganish mavzusidir (bu yerda graf tushunchasining aniqroq ta'rifi berilgan). graf murakkab tuzilgan ma'lumotni tavsiflash uchun ishlatiladi va shuning uchun katta amaliy ahamiyatga ega. matematikada graflar paydo bo'lishiga eyler asarlari yordam berdi. graflar bilan qayerda uchrashamiz? ehtimol, ular bilan qayerda uchrashmasligimizni aytish osonroq. ya’ni biz graflarda juda ko’p holatda uchratamiz. misol qilib quyidagilarni keltirishimiz mumkin: · lokal yoki global tarmoq modeli · algoritmlarning blok-sxemasi · elektr sxemalar · oila daraxti (shajara) · metro xaritasi · ma'lumotlar bazasi modeli · aqlli xaritalar va boshqa ko'plab narsalar. ushbu darsda butun graflar nazariyasini olish mumkin emas. shuning uchun qisqacha ma’lumotlarni keltirib o’tamiz. g graf - g: = (v, e) tartiblangan juftlik, bu yerda v - uchlarning (yoki tugunlarning) bo'sh bo'lmagan to'plami, e …

2 / 7

jacent ikkita uch o’rtasida aloqa mavjud bo’lganini bildiruvchi atama insidentlik intsidentnost incident on uchga nisbatan qirra haqida daraja stepen degree uchga tutashgan qirralarning soni asosiy tushunchalar grafdagi marshrut - bu har bir uch (oxirgisidan tashqari) ketma-ketlikdagi keyingi uchga qirra bilan bog'langan uchlarning cheklangan ketma-ketligi. yo'l - bu qirralarning takrorlanmagan yo'lidir. oddiy zanjir - bu uchlarni takrorlamaydigan marshrut (bu oddiy zanjirda takrorlanadigan qirralarning yo'qligini anglatadi) orgrafdagi yo'naltirilgan marshrut (yoki yo'l) - bu har bir element oldingi va keyingi qismga tushadigan uchlar va yoylarning cheklangan ketma-ketligi. birinchi va oxirgi uchlar bir-biriga to'g'ri keladigan zanjirlar sikl deb ataladi (1-rasmda acd va acde sikllar) yo'lning (yoki siklning) uzunligi uni tashkil etuvchi qirralarning soni deyiladi agar uning qirralari takrorlanmasa, yo'l (yoki sikl) oddiy deb nomlanadi; agar u sodda bo'lsa va undagi tepaliklar takrorlanmasa u elementar deb nomlanadi. graf turlari yo'naltirilgan graf - (qisqacha orgraf) - qirralari yo'naltirilgan graf (4-rasm pastga qarang). yo'naltirilmagan graf - uchlar …

3 / 7

lashtirishingiz va std-da mavjud bo'lgan turli xil konteynerlardan foydalanishingiz mumkin. qo’shnilik matritsasi 1 dan n gacha raqamlangan g grafning qo'shnilik matritsasi kvadrat kattalikdagi a matritsasi bo'lib, unda a [i][j] elementining qiymati 1 ga teng bo'lsa, grafning i- va j- uchlari qo’shni bo‘ladi, aks holda qiymati nolga teng bo‘ladi. bunday matritsa binar matritsa deb ham ataladi. oddiy graf uchun asosiy diagonal elementlari 0 ga teng bo‘ladi. qo'shnilik matritsasi orgrafni tavsiflash uchun ham, yo'naltirilmagan grafni tasvirlash uchun ham mos keladi. yo'naltirilmagan graf uchun elementlarning qiymatlari asosiy diagonalga nisbatan nosimmetrikdir. qo'shnilik matritsadan foydalanish faqat qirralari ko'p bo'lmagan hamda murakkab bo‘lmagan graflar uchun afzalroqdir, chunki u har bir element uchun bitta bit saqlashni talab qiladi. agar graf murakkab bo'lsa, unda xotiraning katta qismi nollarni saqlashga sarflanadi, ammo murakkab graflarda qo'shnilik matritsasi grafni xotirada ixchamroq ifodalaydi va taxminan bit xotiradan foydalanadi. ushbu kattalik qo'shnilik ro'yxatlariga qaraganda yaxshiroq (pastga qarang). 3-rasm. yo’naltirilmagan grafda qo’shnilik matritsasi 4-rasm. …

4 / 7

agar uch va qirra o'rtasida hech qanday bog'liqlik bo'lmasa, unda mos keladigan katak "0" qiymatiga ega bo‘ladi. 5-rasm. yo’naltirilmagan grafda insidentlik matritsasi 5-rasm. orgrafda insidentlik matritsasi qo’shnilik ro'yxati qo’shnilik ro'yxati - bu grafni uchlar ro'yxati ("ro'yxatlar ro'yxati") to'plami sifatida ko'rsatish usuli - grafning har bir uchi qo'shni uchlar ro'yxatiga to'g'ri keladi. masalan, 1-rasmni biz quyidagi qo'shnilik ro'yxati bilan tavsiflashimiz mumkin: a: {b, c, d, e} b: {a} c: {a, d} d: {a, c, e} e: {a, f} f: {e} bu sodda graflarni aks ettirish uchun ham, grafni kenglik yoki chuqurlikda bosib o'tish uchun asosiy algoritmlarni amalga oshirish uchun ham eng qulay usuldir, bu yerda siz hozirda ko'rib chiqilgan uchning "qo'shnilarini" tezda olishingiz kerak. qo’shnilik matritsalarini taqqoslash amal qo’shnilik ro’yxati qo’shnilik matritsasi (x,y) qirraning mavjudligini tekshirish o(|v|+|e|) o(1) qirraning darajasini hisoblash o(1) o(|v|) sodda grafilar uchun xotiradan foydalanish o(|v|+|e|) o(|v|2) graflarda o’tish o(|v|+|e|) o(|v|2) 7 image4.png image5.png image8.png image9.png image12.png image13.png …

5 / 7

Ko'proq o'qimoqchimisiz?

Barcha 7 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"graflar" haqida

6-laboratoriya mashg’uloti graflar. umumiy ma’lumotlar graf - bu abstrakt obyekt bo’lib, uchlar to'plami (tugunlar) va qirralarning to'plami - uchlar juftliklari orasidagi bog'lanishlardan tashkil topadi (ulanishlar). graf mavzusi juda keng. graflar diskret matematikaning o'rganish mavzusidir (bu yerda graf tushunchasining aniqroq ta'rifi berilgan). graf murakkab tuzilgan ma'lumotni tavsiflash uchun ishlatiladi va shuning uchun katta amaliy ahamiyatga ega. matematikada graflar paydo bo'lishiga eyler asarlari yordam berdi. graflar bilan qayerda uchrashamiz? ehtimol, ular bilan qayerda uchrashmasligimizni aytish osonroq. ya’ni biz graflarda juda ko’p holatda uchratamiz. misol qilib quyidagilarni keltirishimiz mumkin: · lokal yoki global tarmoq modeli · algoritmlarning blok-sxemasi · elektr s...

Bu fayl DOCX formatida 7 sahifadan iborat (240,9 KB). "graflar"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: graflar DOCX 7 sahifa Bepul yuklash Telegram