Va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi



Download 194.14 Kb.
bet1/3
Sana13.04.2021
Hajmi194.14 Kb.
  1   2   3

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI

VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Algoritmlarni loyihalash fanidan

Mustaqil ishi



Guruh: CAL-020

Bajardi : Ergashboyev Fayzulloh

Yo`naltirilmagan grafga ta`rif bering va misolda ifodalab ko`rsating

Yo’naltirilmagan graflar- (a,b) U juftlikni tashkil etuvchi a va b uchlarning joylashish tartibidan bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash mumkin .

Agar (a,b) juftlik uchun uni tashkil etuvchilarning joylashish tartibi ahamiyatsiz, ya’ni (a,b) = (b,a) bo‘lsa, (a,b) juftlikka yo‘naltirilmagan(oriyentirlanmagan) qirra (yoki, qisqacha, qirra) deyiladi.Barcha qirralari yo'naltirilmagan graf- yo'naltirilmagan grafik deb nomlanadi.Boshqacha qilib aytganda, yo'naltirilmagan grafikning chekkalari yo'nalishni o'z ichiga olmaydi .Agar G = (V,U) grafda U kortej faqat qirralardan iborat bo‘lsa, u holda yo‘naltirilmagan (oriyentirlanmagan) graf, qisqacha, orgraf deb ham atalad



Misol

Facebookning barcha foydalanuvchilarining yo'naltirilmagan grafigini tasavvur qilaylik, V qirralari foydalanuvchilarni va E qirralari do'stlikni anglatadi. Boshqacha aytganda: agar A va B foydalanuvchilari Facebook-dagi do'stlar bo'lsa, A va B cho'qqilari orasida chekka joy bor. Ikkala foydalanuvchi o'rtasidagi aloqa darajasini aniqlash qiyin.



Rasmiy ravishda, biz ikkita tugun orasidagi eng qisqa masofani boshqarilmagan, o'lchanmagan grafikda ko'rishimiz kerak.

Ushbu yo'naltirilmagan A va C grafikdagi ikkita vertikalni ko'rib chiqaylik.

1. A → B → C va
2. A → G → F → E → D → C

Shubhasiz, ijtimoiy tarmoqdagi ikki kishi o'rtasidagi aloqa darajasini ko'rishga harakat qilganda, biz eng kichik yo'ldan borishni xohlaymiz.

Hozircha hammasi yaxshi.

Davom etishdan oldin, ushbu muammoning murakkabligini ko'rib chiqaylik. Yuqorida ta'kidlab o'tilganidek, 2017 yil 3-choragida Facebookda 2,07 milliard foydalanuvchiga ega. Demak, bizning jadvalimizda 2,07 milliardga yaqin tugun va kamida (2,07 milliard - 1) chekka (har bir kishining kamida bitta do'sti bo'lsa) bo'ladi.

Bu muammoni hal qilish uchun juda katta miqyosda. Bunga qo'shimcha ravishda, biz grafikda berilgan manba verteksidan maqsad verteksiga o'tish uchun bir nechta yo'llar bo'lishi mumkinligini ko'rdik va biz muammoni eng qisqa yo'l bilan hal qilishni istaymiz.

Muammoni hal qilish uchun ikkita klassik grafikli algoritmlarni ko'rib chiqamiz:

1. Chuqur birinchi qidiruv va
2. Nonni birinchi qidirish.


Download 194.14 Kb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2020
ma'muriyatiga murojaat qiling

    Bosh sahifa
davlat universiteti
ta’lim vazirligi
maxsus ta’lim
O’zbekiston respublikasi
zbekiston respublikasi
axborot texnologiyalari
o’rta maxsus
guruh talabasi
nomidagi toshkent
davlat pedagogika
texnologiyalari universiteti
xorazmiy nomidagi
toshkent axborot
pedagogika instituti
haqida tushuncha
rivojlantirish vazirligi
toshkent davlat
Toshkent davlat
vazirligi toshkent
tashkil etish
matematika fakulteti
ta’limi vazirligi
samarqand davlat
kommunikatsiyalarini rivojlantirish
bilan ishlash
pedagogika universiteti
vazirligi muhammad
fanining predmeti
Darsning maqsadi
o’rta ta’lim
navoiy nomidagi
haqida umumiy
Ishdan maqsad
moliya instituti
fizika matematika
nomidagi samarqand
sinflar uchun
fanlar fakulteti
Nizomiy nomidagi
maxsus ta'lim
Ўзбекистон республикаси
ta'lim vazirligi
universiteti fizika
umumiy o’rta
Referat mavzu
respublikasi axborot
таълим вазирлиги
махсус таълим
Alisher navoiy
Toshkent axborot
Buxoro davlat