6-ma’ruza. Graflar nazariyasi elementlari va o'tish algoritmlari

22-rasm. Grafni qo’shnilik matritsasi orqali tasvirlash

Qoʻshnilik matritsasining bir xil analogi Kirxgof matritsasi _{ }, n tartibli kvadrat matritsa sifatida aniqlangan, uning elementlari

Qoʻshnilik matritsasi _{ } va _{ } Kirxgof matritsasi oʻrtasidagi bogʻliqlik, _{ } shaklga ega, bu yerda _{ }, ya’ni bu diagonali elementlari mos keladigan uchlar darajalariga teng boʻlgan matritsa. Kirxgof matritsasining muhim xususiyati (har qanday satr va har bir ustun elementlari yigʻindisi nolga teng boʻlgan boshqa har qanday matritsa kabi) matritsaning barcha elementlarining algebraik qoʻshimchalari bir-biriga teng boʻlishidir.
Izomorf graflar faqat mos mavhum graf uchlarini belgilashda (raqamlashda) farq qilganligi sababli, ularning qoʻshnilik matritsalarini (Kirxgof matritsalari) bir-biridan satrlar va ustunlarni biroz almashtirish orqali olish mumkinligi aniq boʻladi.
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).