Yakuniy yozma (M. T. A). Ma’lumotlarning tarmoqli tuzilmalari: ta’riflar, asosiy tushunchalar

Yakuniy yozma (M. T. A). Ma’lumotlarning tarmoqli tuzilmalari: ta’riflar, asosiy tushunchalar

YAKUNIY YOZMA (M.T.A)

. Ma’lumotlarning tarmoqli tuzilmalari: ta’riflar, asosiy tushunchalar.
Juda ko’plab masalalarning (m-n, geometrik) yechimini olish uchun odatda qog’ozga inson, shahar, kimyoviy narsalarni anglatuvchi nuqtalar va ularni tutashtiruvchi (strelkali) chiziqlarni chizamiz. Natijada hosil bo’lgan chizma graf deb ataladi.
Граф - бу мураккаб чизиқсиз кўпбоғламли динамик тузилма бўлиб, мураккаб объектларнинг хусусиятлари ва муносабатларини акс эттиради
ko’rsatuvchi mantiqiy qiymatlardan iborat bo’ladi.

Vaznli graflar uchun tugunlar orasida bog’lanish bor yoki yo’qligini oddiy ko’rsatish yetarli emas. Bunday graflarni qayta ishlash uchun xotirada har bir yoyning vazni saqlash talab etiladi, masalan, biletning narxi yoki yo’l uzunligini. Buning uchun vazn matritsasi qo’llaniladi.

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.
Graflar uchun qo’shnilik va vazn matritsasi, misollar yordamida tavsiflab bering.
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).

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.

Vaznli graflar uchun tugunlar orasida bog’lanish bor yoki yo’qligini oddiy ko’rsatish yetarli emas. Bunday graflarni qayta ishlash uchun xotirada har bir yoyning vazni saqlash talab etiladi, masalan, biletning narxi yoki yo’l uzunligini. Buning uchun vazn matritsasi qo’llaniladi.

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.