1-ma’ruza. Graflar nazariyasi elementlari va o'tish algoritmlari. Grafni aniqlanishi orientirlangan va orientirlanmagan graflar. Lokal daraja. Yo`l va sikl. Grafni mashina xotirasida ifodalash usullari

22-rasm. Grafni qoʻshnilik matritsasi orqali tasvirlash 
Qoʻshnilik matritsasining bir xil analogi Kirxgof matritsasi 
𝐾 = [𝑘
𝑖,𝑗
], n tartibli kvadrat 
matritsa sifatida aniqlangan, uning elementlari 
𝑘
𝑖,𝑗
= {
−1, 𝑎𝑔𝑎𝑟 𝑣
𝑖
𝑣𝑎 𝑣
𝑗
𝑞𝑜
′
𝑠ℎ𝑛𝑖𝑙𝑎𝑟 𝑏𝑜
′
𝑙𝑠𝑎,
0, 𝑎𝑔𝑎𝑟 𝑣
𝑖
𝑣𝑎 𝑣
𝑗
𝑞𝑜
′
𝑠ℎ𝑛𝑖𝑙𝑎𝑟 𝑏𝑜
′
𝑙𝑚𝑎𝑠𝑎,
𝑑𝑒𝑔𝑣
𝑖
𝑎𝑔𝑎𝑟 𝑖 = 𝑗.
Qoʻshnilik matritsasi 
𝐴 va 𝐾 Kirxgof matritsasi oʻrtasidagi bogʻliqlik, 𝐾 = 𝐷 − 𝐴 shaklga 
ega, bu yerda 
𝐷 = 𝑑𝑖𝑎𝑔 (𝑑𝑒𝑔 𝑣
1
, 𝑑𝑒𝑔 𝑣
2
, … , 𝑑𝑒𝑔 𝑣
𝑛
), 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 
nxn 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 
n
2
bit 
xotiradan foydalanadi. Ushbu kattalik qoʻshnilik roʻyxatlariga qaraganda yaxshiroq (pastga 
qarang).