Samarqand davlat universiteti raqamli texnologiyalar fakulteti dasturiy injiniring yo

Qo’shnilik matritsasi. 1 dan n gacha raqamlangan G grafning qo'shnilik matritsasi kvadrat kattalikdagi A matritsasi bo'lib, unda a [i][j] elementining qiymati 1 ga teng bo'lsa, grafning i- va j- uchlari qo’shni bo‘ladi, aks holda qiymati nolga teng bo‘ladi. Bunday matritsa binar matritsa deb ham ataladi. Oddiy graf uchun asosiy diagonal elementlari 0 ga teng bo‘ladi.

Qo'shnilik matritsasi orgrafni tavsiflash uchun ham, yo'naltirilmagan grafni tasvirlash uchun ham mos keladi. Yo'naltirilmagan graf uchun elementlarning qiymatlari asosiy diagonalga nisbatan nosimmetrikdir.

Qo'shnilik matritsadan foydalanish faqat qirralari ko'p bo'lmagan hamda murakkab bo‘lmagan graflar uchun afzalroqdir, chunki u har bir element uchun bitta bit saqlashni talab qiladi. Agar graf murakkab bo'lsa, unda xotiraning katta qismi nollarni saqlashga sarflanadi, ammo murakkab graflarda qo'shnilik matritsasi grafni xotirada ixchamroq ifodalaydi va taxminan bit xotiradan foydalanadi. Ushbu kattalik qo'shnilik ro'yxatlariga qaraganda yaxshiroq (pastga qarang).


3-rasm. Yo’naltirilmagan grafda qo’shnilik matritsasi


4-rasm. Orgrafda qo’shnilik matritsasi
Qo'shnilik matritsasini amalga oshirish uchun massivlar massivi qo'llaniladi: vektorlar vektori (vector>) yoki kaliti uchlar soni, qiymati esa vektori. Agar grafni kengaytirish kerak bo'lmasa, u holda vektorni array (massiv) bilan almashtirish kerak.