yo'naltirilgan graflar asoslari

DOCX 30 стр. 53,9 КБ Бесплатная загрузка

30 стр.

FaylHub.uz

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

Размер 53,9 КБ

Тип файла DOCX

Страницы 30

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

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

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

1 / 30

$o‘zbekiston respublikasi oliy ta’lim fan va innovatsiya vazirligi toshkent axborot texnalogiyalari unversiteti nukus filiali mustaqil ish mavzu: yo'naltirilgan va yo'naltirilmagan graflar o'quvchi: ism joyi 2024-2025-o'quv yili 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 anglatadi va $ e $ yo'nalishli qirralar (edges) to'plami hisoblanadi. har bir qirrasi $ (u, v) $ ko'rinishda bo'lib, u qirrasi $ u $ tugunidan $ v $ tuguniga yo'nalganligini bildiradi. har bir qirra boshlanish tuguni va tugash tuguniga …$

2 / 30

$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 $ n \times n $ o'lchovli matritsa, bu erda matritsaning har bir elementi yo'nalishli qirrani bildiradi. agar $ (i, j) $ elementi 1 bo'lsa, tugun $ i $ dan $ j $ ga yo'nalish mavjudligini bildiradi. - **qo'shnilik ro'yxati …$

3 / 30

$ydigan, 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 bir uch oralig'ida qirralar mavjud bo'lgan grafdir. qirralarning soni $n(n-1)/2$ ga teng. - **tsiklik graf**: $c_n$ bilan ifodalanadi va $n$ uchli tsikli o'z ichiga oladi. - **yulduz graf**: $s_n$ bilan ifodalanadi va bitta markaziy uch …$

4 / 30

$rralar 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, qo'llanilish sohasi kengligidan dalolat beradi. 3. yo'naltirilgan graflarda yo'l va zanjir 3. yo'naltirilgan graflarda yo'l va zanjir mavzusida quyidagi ma'lumotlar taqdim etiladi: yo'naltirilgan graflar nazariyasida yo'l va zanjir tushunchalari muhim rol o'ynaydi, chunki ular graflarning strukturasini tahlil qilishda va ularni tadqiq qilishda …$

5 / 30

qilariga 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, ijtimoiy tarmoqlardagi muloqot modelini tahlil qilish, kompyuter tarmoqlarida ma'lumot uzatish va boshqa ko'plab sohalarda yo'naltirilgan graflar yordamida tizimlarning samaradorligini oshirish mumkin. yo'naltirilgan graflarda ikki cho'qqi o'rtasidagi eng qisqa yo'lni topish masalasi mashhur masalalardan biri bo'lib, dijkstra algoritmi yoki bellman-ford algoritmi kabi usullar yordamida …

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

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

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

О "yo'naltirilgan graflar asoslari"

o‘zbekiston respublikasi oliy ta’lim fan va innovatsiya vazirligi toshkent axborot texnalogiyalari unversiteti nukus filiali mustaqil ish mavzu: yo'naltirilgan va yo'naltirilmagan graflar o'quvchi: ism joyi 2024-2025-o'quv yili 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 tugunla...

Этот файл содержит 30 стр. в формате DOCX (53,9 КБ). Чтобы скачать "yo'naltirilgan graflar asoslari", нажмите кнопку Telegram слева.

Теги: yo'naltirilgan graflar asoslari DOCX 30 стр. Бесплатная загрузка Telegram