Laboratoriya mashg’uloti . Graflar bilan ishlovchi sodda algoritmlar.Graflarni tasvirlash.
Ishdan maqsad: Talabalarda graflar bilan ishlash algoritmlari haqida ko’nikmalar hosil qilish
va ular bilan ishlashni o’rganish.
Nazariy qism:
Deykstra algoritmi
Eng qisqa masofani aniqlash misolini ko’rib chiqaylik. Shahar viloyatlarini birlashtiruvchi
avtomobil yo’llari tarmog’I berilgan bo’lsin. Ba’zi yo’llar bir tomonlama. Shahar markazidan har bir
viloyatga eng qisqa yo’lni topishimiz zarur.
Keltirilgan masalani yechishda Deykstraning algoritmidan foydalanishimiz mumkin. Algoritm
graflarga asoslangan bo’lib, u 1959 yil niderlandiyalik olim E. Deykstra tomonidan yaratilgan. U grafning
bitta uchidan boshqa uchlarigacha eng qisqa masofani aniqlaydi, bunda grafning quvurg’alari manfiy
og’irlikka ega bo’lmasligi lozim. Bizdan birinchi uchdan qolganlariga borishning qisqa masofasini toppish
talab qilinsin.
Doiralar shaklida uchlar, chiziqlar shaklida ular orasidagi yo’l (grafning qovurg’alari) tasvirlangan.
Doiralar ichida uchlarning nomerlari, qovurg’alar ostida ularning og’irligi – yo’l uzunligi berilgan. Har
bir uchning yonida qizil belgi bilan shu uchga birinchi uchdan eng qisqa masofa uzunligi belgilangan.
Tadbiqi
1–uchning belgisi 0 ga teng deb hisoblanadi, qolgan uchlarning belgilari yetib bo’lmas darajada
juda katta sonlardan iborat. Bu 1–uchdan boshqalarigacha bo’lgan masofa hali noma’lumligiki ko’rsatadi.
Grafning barcha uchlari ko’rilmagan deb belgilanadi.
Birinchi qadam
Minimal belgiga 1–uch ega. Uning qo’shnilari 2, 3 va 6 uchlar. Uchning qo’shnilarini navbat bilan
ko’rib chiqamiz. 1–uchning birinchi qo’shnisi 2–uch, chunki ungacha bo’lgan masofa minimal. 1–uch
orqali ungacha bo’lgan masofa 1–uchgacha bo’lgan qisqa masofaning summasiga teng, 1–dan 2–ga
boruvchi uning belgisi va qovurg’asi uzunligiga, ya’ni 0+7=7. Bu 2–uchning joriy belgisidan (10000)
kichik, shu sababdan ham 2–uchning yangi belgisi 7 ga teng.
Shunga mos ravishda qolgan qo’shnilar (3 va 6 uchlar) uchun ham yo’l uzunligini aniqlaymiz. 1-
uchning barcha qo’shnilari ko’rib chiqildi. 1-uchgacha joriy minimal masofa yakuniy hisoblanadi va qayta
ko’rib chiqilmaydi. 1-uch ko’rib chiqildi deb belgilanadi.
Ikkinchi qadam
Birinchi qadam takrorlanadi. Ko’rib chiqilmagan uchlardan “yaqini”ni topamiz. Bu 2-uch belgisi 7
ga teng. Yana tanlangan uchning qo’shnilari belgilarini kamaytirishga harakat qilamiz, bunda ularga 2-
uch orqali o’tamiz. 2- uchning qo’shnilari 1, 3 va 4 uchlar.
1-uch ko’rib chiqilgan, shu sababdan 3-uch ko’rib chiqilmagan va uchlar ichida minimal belgiga
ega. Agar unga 2 orqali borilsa, u holda bu yo’lning uzunligi 17 (7+10=17)ga teng bo’ladi. Ammo 3-
uchning joriy belgisi 9 ga teng, ya’ni 9<17, shu sababdan belgi o’zgarishsiz qoladi.
2-ucning yana bir qo’shnisi 4-uch. Agar unga 2-uch orqali borsak, u holda bunday yo’lning uzunligi
22 (7+15=22) ga teng. 22<10000 dan bo’lganligi sabab, 4-uchning belgisini 22 ga tenglaymiz.
2-uchning barcha qo’shnilari ko’rib chiqildi, endi uni ko’rib chiqilgan sifatida belgilaymiz.
Uchinchi qadam
3-uchni tanlab algoritmning qadamini takrorlaymiz. Uni “qayta ishlab chiqish”dan so’ng quyidagi
natijaga ega bo’lamiz.
To’rtinchi qadam
Beshinchi qadam
Oltinchi qadam
Shu tarzda 1-uchdan 5-uchga eng qisqa masofa 1 – 3 – 6 – 5 uchlari orqali bo’ladi. Shu yo’l orqali
biz 20 ga teng minimal og’irlik yig’amiz.
Minimal masofa haqida xulosaga keladigan bo’lsak. Har bir uch uchun yo’l uzunligini bilamiz va
endi uchlarni oxirdan ko’rib chiqamiz. Yakuniy uchni ko’rib chiqamiz (bu holatda 5-uch). U bilan
bog’langan barcha uchlarni ham ko’rib chiqamiz, yakuniy uch yo’li uzunligidan mos qovurg’aning
og’irligini ayirgan holda yo’l uzunligini topamiz. Bizda 5-uch yo’l uzunligi 20. U 6 va 4 uchlar bilan
bog’langan. 6- uch uchun 20-9=11 og’irlikka ega bo’lamiz (mos tushdi). 4-uch uchun 20-6=14 og’irlikka
ega bo’lamiz (mos tushmadi). Agar natijada biz ko’rilayotgan uchning (joriy holda 6-uch) yo’l uzunligiga
mos qiymatga ega bo’lsak, u holda yakuniy uchga o’tish aynan o’sha uchdan amalga oshirilgan bo’ladi.
Bu uchni qidirilayotgan yo’lda belgilan qo’yamiz.
6-uchga qaysi qovurg’a orqali kelganimizni aniqlaymiz. Va shu holda toki boshiga
chiqmagunimizcha davom qildiramiz.
Agar bunday kuzatish natijasida bizda qaysidir qadamda bir nechta uchlar uchun bu qiymat mos
tushsa, u holda ulardan ixtiyoriy birini olish mumkin – bir necha yo’llar bir xil uzunlikka ega bo’ladi.
