Quyida berilgan variantga mos Graf tuzilmasining qo'shnilik va vazn matritsasini ishlab chiqish

1-SAVOL

1. 
   Quyida berilgan variantga mos Graf tuzilmasining qo'shnilik va vazn matritsasini ishlab chiqish;
   

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.

2. 
   Berilgan GRAF tuzilmasining qo'shnilik va vazn matritsasini ekranga chiqarish funksiyasini dasturlash (C++ tilida);
   

Graflar

Graf – bu tugunlar va qirralar (tugunlar juftligini birlashtiruvchi) to’plamidan iborat bo’lgan abstrakt matematik ob’ektdir.

Grafning elementlari tarkibi va munosabatlar tuzilishi beriladi. Grafning tarkibiy qismlari bu uning tugunlari va qirralaridir.

Tarmoq

Bir nechta juft tugunlararo qirralardan iborat bo’lgan turlicha yo’llar to’plami mavjud bo’lishi mumkin. Yopiq yo’llar – sikllarning mavjud bo’lishi tarmoqlarga xos xususiyatdir.

Yonaltirilmagan graf yoki simmetrik bog’liqlik

Yonaltirilmagan graf yoki nosimmetrik bog’liqlik

qirra yoylar

Ilmoq – aynan bitta tugundan chiqib, yana shu tugunga kiruvchi qirra.