graflar nazariyasi elementlari

PDF 30 pages 861.1 KB Free download

30 pages

FaylHub.uz

Download via Telegram

Size 861.1 KB

File type PDF

Pages 30

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

1 / 30

4-ma’ruza: graflar nazariyasi elementlari. grafni to‘lik aylanib chiqish algoritmlari. graflar nazariyasi elementlari. ma’ruzachi: m.tojiyev 4 graf qachon ishlatiladi? real hayotdagi juda ko’p tizimlar graphlarga asoslangan bo’ladi. masalan facebook ijtimoiy tarmog’idagi do’stlik aloqalari undirected graph’ga asoslangan. siz facebookdagi do’stingiz uchun ham do’st hisoblanasiz ya’ni do’stlik ikki tomonlama bog’langan. twitter va instagram tarmoqlaridagi do’stlik (yoki kuzatish – follow) esa bir tomonlama bog’lanishga ega. siz kuzatadigan odamlar sizni kuzatmasligi mumkin. demak twitter va instagramdagi following – directed graph hisoblanadi. shuningdek, xaritalarni graphga aylantirish mumkin. chorrahalarni (ko’chalarning bog’lanishlarni) node deb oladigan bo’lsak, ko’chalarning o’zi edge bo’ladi. kartani graph’ga aylantirgach, siz bir nuqtadan boshqasiga eng qisqa yo’lni hisoblash imkoniga ega bo’lasiz. graflarda algoritmlarni qo'llash  kartografik tizimlar  xaritadagi eng yaxshi yo'nalishni qidiring 3 graflarni dasturlarda qo‘llash  turli xil dasturlar: kompyuter o‘yinlari uchun. 4 graflarda algoritmlarni qo'llash  tarmoqlarda yoʻl-yoʻriq 5 ijtimoiy tarmoq 6 qidiruv tizimlari graflarda algoritmlarni qo'llash  avtomatik iz (simlar) bosilgan …

2 / 30

ataydilar, o‘z navbatida bu uch shu qirralarning xar biriga insidentdir. 3 va 5 uchlar yakkalangan, deyiladi, ular ko‘pi bilan sirtmoqlarga ega bo‘lishi mumkin. j i a1 2 4 3 5 e f g h d k c b ta’rif. bo‘sh bo‘lmagan x uchlar to‘plami va qirralar to‘plamidan tuzilgan tartiblangan g=(x,u) ba’zi adabiyotlarda g=(v,e) juftlik oddiy graf deb ataladi. petersen nomi bilan atalgan graf. graflar quyidagi xossalarga: chekli (qirralari va uchlari soni chekli), barcha qirralari yo‘naltirilmagan, sirtmoqlari va karrali qirrali yo‘q. bunday graflarga quyidagilar misol bo‘la oladi: graflar turlari graflar(graphs) yoʻnaltirilmagan grafiklar (undirected graphs) qirralar yo’nalishga ega emas(edges) yoʻnaltirilgan graflar (directed graphs) qirra– yoy(arcs, edges) yo’nalishga ega (1, 2) va (2, 1) – bir xil qirralar (1, 3) va (3, 1) – turli xil qirralar! asosiy atamalar tugun (vertex, node) qirra (edge, link) qo’shni tugunlar (adjacent vertices) (4, 6) qirralar insedent (incident) yo’l (path) - bu grafdagi cho'qqilar (tugunlar) ketma-ketligi bo'lib, …

3 / 30

tlar yoki qiymatlarga ega. masalan, transport tarmog'ini vaznli graf ko’rinishida modellashtirish mumkin. bu yerda qirralar shaharlar orasidagi yo'llar yoki temir yo'llarni, og'irliklar esa ular orasidagi masofa yoki vaqtni ifodalaydi. to'liq graf(complete graph) - bu har bir aniq tugunlari juftligi qolgan tugun bilan bog'langan graf. boshqacha qilib aytganda, to'liq graf har bir tugun grafdagi boshqa har bir tugun (uch) bilan bog'langan grafdir. toʻliq yoʻnaltirilmagan grafdagi qirralar soni: grafning to'yinganligi d (density): n ta uchi va m qirrali g grafning toʻyinganlik zichligi d quyidagicha aniqlanadi: to'liq graf d = 1 to'yinganligiga ega qirralari kam bo'lgan siyrak graf past to'yinganlik zichligiga ega, ko'p qirralari bo'lgan zich graf esa yuqori to'yinganlik zichligiga ega.to'yinganlik zichligi graflarning xossalari va xatti-harakatlarini tahlil qilishda foydali o'lchovdir, chunki u grafning umumiy zichligini bitta raqamda ushlaydi. to’yingan graf (dense graph) - bu qirralarning soni maksimal bo’lishi mumkin bo'lgan graf hisoblanadi. to’yingan graflar turli muammolarni hal qilish uchun ishlatilishi mumkin, jumladan: …

4 / 30

sob-kitoblardan qochish uchun ularning siyrakligidan foydalanadi. boshqa tomondan, zich graflar saqlash va qayta ishlash uchun ko'proq xotira va hisoblash resurslarini talab qiladi. siyrak graf bilan hal qilinadigan muammolar siyrak graflar odatda ko'plab sohalarda real muammolarni modellashtirish va hal qilish uchun ishlatiladi, jumladan: ijtimoiy tarmoqlar: ijtimoiy tarmoqlarda odamlar yoki guruhlar o'rtasidagi munosabatlarni ifodalash uchun siyrak grafdan foydalanish mumkin. graf tuzilishini tahlil qilish orqali biz ijtimoiy hodisalar, masalan, axborot tarqalishi yoki ta'sir qilish haqida tushunchaga ega bo'lishimiz mumkin. transport tarmoqlari: transport tarmoqlarida shaharlar, aeroportlar yoki boshqa transport markazlari oʻrtasidagi aloqalarni ifodalash uchun siyrak grafdan foydalanish mumkin. graf tuzilishini tahlil qilish orqali biz marshrutlarni optimallashtirishimiz, sayohat vaqtini qisqartirishimiz va transport samaradorligini oshirishimiz mumkin. siyrak graf bilan hal qilinadigan muammolar internet va aloqa tarmoqlari: internet va aloqa tarmoqlarida veb-saytlar, serverlar va aloqa qurilmalari o'rtasidagi aloqalarni ko'rsatish uchun siyrak grafdan foydalanish mumkin. graf tuzilishini tahlil qilib, biz ma'lumotlar uzatishni optimallashtirishimiz, tarmoqdagi tiqilib qolishni kamaytirishimiz va …

5 / 30

aflarning xotirada namoyishi ▪ grafning xotiradagi namoyishi (uni saqlash formati) grafdagi operatsiyalarning hisoblash murakkabligini va talab qilinadigan xotira miqdorini belgilaydi ▪ grafiklarni xotirada ifodalashning asosiy yo‘llari: ❑qo‘shnilik matritsasi (adjacency matrix) – to‘yingan graflar uchun samarali ❑qo‘shnilik ro’yhati (adjacency list) – siyrak graflar uchun samarali qo'shnilik matritsasi ikki o’lchamli massiv bo'lib, unda satrlar va ustunlar graf tugunlarini ifodalaydi va har bir katakda ikkita tugun orasidagi qirra og'irligini ifodalovchi qiymat mavjud. vaznsiz graf uchun qiymat 0 yoki 1 bo'lishi mumkin. qo'shni matritsaning fazoviy murakkabligi o(n2), bu yerda n - grafdagi tugunlar soni. qo‘shnilik matritsasi qo’shnilik matritsasi ▪ a matrisa qo’shnilik matrisasi (adjacency matrix) – uning o’lchami n × n elementdan iborat va ▪ talab qiladigan xotira 𝑂(|𝑉2|) ▪ grafikda qirra (𝑖, 𝑗) mavjudligini tezda aniqlash mumkin ▪ o(1) vaqt murakkabligida 𝑎𝑖𝑗 matrisa elementiga murojaat qilish mumkin to'yingan graflar uchun samarali qiymat (| e| ≈ | v|2) qo’shnilik matritsasi 12 ▪ qo’shnilik matritsasi …

Want to read more?

Download all 30 pages for free via Telegram.

Download full file

About "graflar nazariyasi elementlari"

4-ma’ruza: graflar nazariyasi elementlari. grafni to‘lik aylanib chiqish algoritmlari. graflar nazariyasi elementlari. ma’ruzachi: m.tojiyev 4 graf qachon ishlatiladi? real hayotdagi juda ko’p tizimlar graphlarga asoslangan bo’ladi. masalan facebook ijtimoiy tarmog’idagi do’stlik aloqalari undirected graph’ga asoslangan. siz facebookdagi do’stingiz uchun ham do’st hisoblanasiz ya’ni do’stlik ikki tomonlama bog’langan. twitter va instagram tarmoqlaridagi do’stlik (yoki kuzatish – follow) esa bir tomonlama bog’lanishga ega. siz kuzatadigan odamlar sizni kuzatmasligi mumkin. demak twitter va instagramdagi following – directed graph hisoblanadi. shuningdek, xaritalarni graphga aylantirish mumkin. chorrahalarni (ko’chalarning bog’lanishlarni) node deb oladigan bo’lsak, ko’chalarning o’zi edge b...

This file contains 30 pages in PDF format (861.1 KB). To download "graflar nazariyasi elementlari", click the Telegram button on the left.

Tags: graflar nazariyasi elementlari PDF 30 pages Free download Telegram