Va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi

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.