Ma’lumotlar tuzilmasi va algoritmlar fanining maqsad va vazifasini izohlab bering

N ta tugundan iborat grafning vazn matritsasi – bu N ga N o’lchamli matritsa bo’lib, (i,j) indeksli har bir elementi i tugundan j tugungacha bo’lgan yoylarning “vazni”ga teng bo’lgan matritsa hisoblanadi.

74. Graflar uchun qo’shnilik va vazn matritsasi, misollar yordamida tavsiflab bering.

• 
  Amaliy masalalarni yechishda odatda har bir yoy ma’lum vazn (og’irlik)ga (yoki uzunlikka) ega bo’lgan vaznli graflar (Weighted graph) qo’llaniladi. Bunday graflar tarmoq (to’r) deb ataladi.
  

• 
  Graflarni tavsiflash uchun odatda ikki turdagi matritsalar qo’llaniladi - qo’shnilik matritsasi (vaznga ega bo’lmagan graflar uchun) va vaznli matritsa (vaznli graflar uchun).
  
• 
  N ta tugunli grafning qo’shnilik matritsasi (adjacency matrix)– bu N ga N o’lchamli matritsa hisoblanib, uning har bir (i,j) indeksli elementi i tugundan j tugunga yoy mavjud yoki mavjud emasligini ko’rsatuvchi mantiqiy qiymatlardan iborat bo’ladi.
  

75. Graflarda “zanjir” va “yo’l” tushunchalari, eng qisqa yo’lni topish algoritmlari.

• 
  Agar yoylar yo’nalishga ega bo’lsa (bir tomonlama harakat mavjud bo’lgan avtomobil yo’li), bunday graflar yo’naltirilgan graf yoki orgraf deb nomlanadi.
  
• 
  Ikkita i va j (qo’shni bo’lmagan) tugunlarni tutashtiruvchi yoylar ketma-ketligi zanjir deb ataladi.
  

Yo’naltirilgan graflarda bunday ketma-ketlik “yo’l” deyiladi.

• 
  Agar grafning ixtiyoriy tugunlar juftligi orasida zanjir mavjud bo’lsa, bunday graf bog’langan deyiladi.
  
• 
  Agar graf bog’lanmagan bo’lsa, u holda uni k ta bog’langan komponentlarga ajratish mumkin, bu komponentlar k-bog’langan deyiladi.
  
• 
  Grafning qaysidir tuguni o’z-o’ziga zanjir bilan bog’lansa, bu sikl (yoki halqali) deb ataladi.
  
• 
  Halqasiz graf daraxt deyiladi.
  
• 
  Barcha mumkin bo’lgan yoylari berilgan graf to’liq deyiladi (masalan, n tuguni bo’lgan grafda n(n-1)/2 ta yoy mavjud bo’ladi).
  

76. Graf tuzilmasida qisqa yo’larni aniqlash uchun Floy-Uorshel algoritmi va uning qo’llanilishiga doir misol keltiring.
77. Graf tuzilmasida qisqa yo’lni aniqlash uchun Deykstr algoritmi va uning qo’llanilishiga doir misol keltiring.
Eng qisqa yo'lni topish misolini ko'rib chiqing. Shaharni bog'laydigan yo'llar tarmog'i berilgan. Ba'zi yo'llar bir tomonlama. Shahar markazidan mintaqadagi har bir shaharga olib boradigan eng qisqa yo'llarni toping.
Ushbu muammoni hal qilish uchun siz Dijkstra algoritmidan foydalanishingiz mumkin - 1959 yilda Gollandiyalik olim E. Dijkstroy tomonidan ixtiro qilingan grafikalardagi algoritm. Grafikning uchidan boshqalarigacha bo'lgan eng qisqa masofani topadi. Faqat salbiy og'irliksiz chizmalar uchun ishlaydi.
Aytaylik, siz birinchi cho'qqidan qolgan barcha masofalarga eng qisqa masofani topmoqchisiz.
Doira uchlarini, chiziqlar esa ularning orasidagi yo'llarni (grafikning chetlarini) ko'rsatadi. Doiralarda vertikallarning raqamlari, qirralarning tepasida ularning og'irligi - yo'l uzunligi ko'rsatilgan. Qiymat har bir verteks yonida qizil rang bilan belgilanadi - bu tugundan 1 verteksgacha bo'lgan eng qisqa yo'lning uzunligi.

1-tugunning qiymati 0 ga teng, qolgan uchlari etiketkalari esa erishib bo'lmaydigan ko'p sonli (ideal holda cheksizlik). Bu 1-tugundan boshqa cho'qqilargacha bo'lgan masofalar hali noma'lum ekanligidan dalolat beradi. Grafikning barcha uchlari ko'rinmas deb belgilangan.