yo'naltirilgan va yo'naltirilmagan graflar nazariyasi

DOCX 47 pages 80.4 KB Free download

Page preview (5 pages)

Scroll down 👇
1 / 47
o‘zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi __universiteti kurs ishi mustaqil ish referat diplom ishi diqqat !!! diqqat !!! diqqat !!! https://seller.soff.uz/account/register/tqrzkf3dtl - ushbu havola link orqali siz ham sotuvchi bo’ling, document joylang va daromad qiling, shu mening linkim orqali ro'yxatdan o'tganlarga 20-30 ta tayyor mustaqil va kurs ishlari beraman, xoxlagan fanidan! ishni boshlab olish uchun yaxshi taklif bu! @soff_seller yo'naltirilgan va yo'naltirilmagan graflar reja: 1. yo'naltirilgan graflar asoslari 2. yo'naltirilmagan graflar asoslari 3. yo'naltirilgan graflarda yo'l va zanjir 1. yo'naltirilgan graflar asoslari ## yo'naltirilgan graflar asoslari yo'naltirilgan graflar matematika va informatika sohalarida keng qo'llaniladigan, yo'nalishli bog'lanishlarning to'plamini ifodalovchi strukturalardir. nazariyaning asosiy maqsadi yo'nalishli bog'lanishlar bo'yicha o'zaro aloqalarni o'rganishdir. yo'naltirilgan graf (inglizcha: directed graph yoki digraph) bu ko'rsatilgan yo'nalishga ega bo'lgan qirralar bilan bog'langan tugunlar to'plamidan iborat. ### tugunlar va qirralar yo'naltirilgan graf \( g = (v, e) \) ko'rinishida ifodalanadi. bu yerda \( v \) tugunlar (vertexlar) to'plamini …
2 / 47
lishi bo'lmaydi, ya'ni \( (u, v) \) va \( (v, u) \) bir xil qirralar hisoblanadi. yo'naltirilgan graflarda esa har ikkalasi alohida-alohida qirralar sifatida qaraladi. ### yo'naltirilgan grafning xususiyatlari 1. **chiqish darajasi (out-degree):** ma'lum bir tugundan chiqayotgan qirralar soni. 2. **kirish darajasi (in-degree):** ma'lum bir tugunga kirayotgan qirralar soni. 3. **sirkulyar graf:** agar yo'naltirilgan grafda biror tugundan boshlab yo'lni kuzatib yana o'sha tugunga qaytib kelish mumkin bo'lsa, bunday graf sirkulyar hisoblanadi. ### qo'llanilish sohalari yo'naltirilgan graflar ko'plab fanlar va amaliy sohalarda qo'llaniladi: - **ko'rsatkichlar va tashkilar:** tashkilot strukturasi, projektdagi jarayonlar va vazifalar ketma-ketligi uchun ishlatiladi. - **internet va tarmoqlar:** web sahifalari o'zaro bog'langanligi, ip marshrutlash yo'nalishlarini ifodalash. - **ma'lumotlar bazasida:** majburiyliklar va bog'lanishlarni ta'riflash uchun. - **ko'dalash teoriyasi:** turing mashinalari modelini tuzishda. ### yo'naltirilgan graflar tasviri yo'naltirilgan grafning tasviri odatda matritsalar yoki ro'yxatlar yordamida amalga oshiriladi: - **qo'shnilik matritsasi (adjacency matrix):** tugunlar soni \( n \) bo'lgan graf uchun \( …
3 / 47
ari va to'ldiruvchi jihatlariga bir nazar tashlashga xizmat qiladi. 2. yo'naltirilmagan graflar asoslari yo'naltirilmagan graflar matematikada va informatika sohalarida muhim mavzudir. bu graflar yo'nalish bo'lmagan qirralar to'plami bilan aniqlanadi. ya'ni har bir qirra ikki uchni bog'laydigan, ammo ularga yo'nalish bermaydigan elementdan iborat. bunday graflar ko'plab foydalanish holatlariga ega, jumladan, tarmoq bilimlari, algoritmlar implementatsiyasi va boshqalar. keling, ushbu mavzuning asosiy jihatlarini ko'rib chiqamiz: 1. **graf tushunchasi**: yo'naltirilmagan graf $g = (v, e)$, bu yerda $v$ uchlar to'plami, $e$ esa qirralar to'plami. har bir qirra $e \in e$ ikki uchni bog'laydi, ya'ni $e = \{u, v\}$ bo'lib, bu erda $u, v \in v$. 2. **uchlar va qirralar soni**: grafning parametrlaridan biri bu uchlar soni, $|v|$, va qirralar soni, $|e|$. $n$-uchli yo'naltirilmagan grafda qirralar maksimal soni $n(n-1)/2$ bo'lishi mumkin, ya'ni graf to'liq graf bo'lganda shunday bo'ladi. 3. **alohida graf turlari**: - **to'liq graf**: $k_n$ bilan ifodalanadigan to'liq graf, bu $n$ uch va har …
4 / 47
teng bo'lsa, bu eylier teoremasidan kelib chiqadi. 7. **matritsalar orqali tasvirlash**: - **alohida matritsa**: $n \times n$ o'lchamli bo'lib $a_{ij}=1$, agar $i$ va $j$ uchi orasida qirra mavjud bo'lsa, aks holda $a_{ij}=0$. - **hodisal matritsa**: $m \times n$ matritsa, bu yerda $m$ qirralar soni, $n$ uchlar soni. $m_{ij}=1$, agar $i$-qirra $j$-uchga ulanib tursa. 8. **o'lish imkoniyatlari**: - har bir ulash kpligining quyi chegarasi - ya'ni faqat linear grafiklar: bu holatda $|e|=|v|-1$. 9. **eylier hamda gamilton graflar**: - **eylier sikli mavjud**: graf eylier siklga ega bo'lishi uchun barcha uchlarining gradusi juft bo'lishi kerak. - **gamilton tsikli**: har bir uch faqat bir marta tekshirilishi kerak va boshlang'ich nuqtaga qaytishi kerak. 10. **bipartit graflar**: - bunday graf ikki to'plam uchidan tashkil topadi va qirralar faqat bu to'plamlarning a'zolari orasida mavjud bo'ladi. yo'naltirilmagan graflar nazariyasi asoslari ko'plab murakkab matematik va amaliy masalalarni hal etishda foydalaniladi. bu masalalarning ko'pchiligi real dunyodagi muammolarni ifodalashda ahamiyatli bo'lib, …
5 / 47
yo'l mavjud bo'lishi mumkin. bu holda a dan b ga, b dan esa c ga yo'nalgan qirrani olamiz. **zanjir** (chain) esa ko'pincha yo'l bilan bir xil ma'noga ega bo'lsa-da, matematik nuqtai nazardan u yo'naltirilgan graflarda biroz farqli ta'rifga ega bo'lishi mumkin. zanjirda graflarning cho'qqilariga takroriy kirib chiqishni taqiqlovchi qoida yo'q. ya'ni, zanjirda biror cho'qqi bir nechta marta uchrashi mumkin. zanjirga misol qilib, agar a -> b -> a -> c kabi yo'l mavjud bo'lsa, bu zanjir deb ataladi, chunki a nuqtasida ikki marta kesishamiz. yo'naltirilgan graflar nazariyasida yana bir muhim tushuncha - bu **tsikl**dir. tsikl bu zanjirning o'ziga tutashgan bir ko'rinishi bo'lib, unda boshlang'ich cho'qqiga qaytiladi. misol uchun, a -> b -> c -> a yo'l tsikl bo'ladi, chunki u a dan boshlanib yana a ga qaytadi. yo'naltirilgan graflar ko'p hollarda real hayotni aks ettiruvchi modellarda qo'llanilib, ko'plab amaliy va nazariy masalalarni yechishda samarali vosita hisoblanadi. masalan, transport tarmoqlari optimizatsiyasi, …

Want to read more?

Download all 47 pages for free via Telegram.

Download full file

About "yo'naltirilgan va yo'naltirilmagan graflar nazariyasi"

o‘zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi __universiteti kurs ishi mustaqil ish referat diplom ishi diqqat !!! diqqat !!! diqqat !!! https://seller.soff.uz/account/register/tqrzkf3dtl - ushbu havola link orqali siz ham sotuvchi bo’ling, document joylang va daromad qiling, shu mening linkim orqali ro'yxatdan o'tganlarga 20-30 ta tayyor mustaqil va kurs ishlari beraman, xoxlagan fanidan! ishni boshlab olish uchun yaxshi taklif bu! @soff_seller yo'naltirilgan va yo'naltirilmagan graflar reja: 1. yo'naltirilgan graflar asoslari 2. yo'naltirilmagan graflar asoslari 3. yo'naltirilgan graflarda yo'l va zanjir 1. yo'naltirilgan graflar asoslari ## yo'naltirilgan graflar asoslari yo'naltirilgan graflar matematika va informatika sohalarida keng qo'llaniladigan, yo'nalishl...

This file contains 47 pages in DOCX format (80.4 KB). To download "yo'naltirilgan va yo'naltirilmagan graflar nazariyasi", click the Telegram button on the left.

Tags: yo'naltirilgan va yo'naltirilma… DOCX 47 pages Free download Telegram