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

Qoʻshnilik matritsasi. Qoʻshnilik matritsasini n-tartibli 
𝐴 = [𝑎
𝑖
, 𝑎
𝑗
] nosimmetrik kvadrat 
matritsa sifatida aniqlaymiz, unda 
𝑎
𝑖,𝑗
elementlar 1 ga teng, agar grafda {
𝑣
𝑖
, 𝑉
𝑗
} qirrasi boʻlsa, 
ya’ni 
𝑣
𝑖
va 
𝑣
𝑗
qoʻshni boʻlsa, 0 ga teng, agar bunday qirra mavjud boʻlmasa. 
Ta’rifdan kelib chiqadiki, har qanday i uchun ∑
𝑎
𝑖,𝑗
𝑛
𝑗=1
= 𝑑(𝑣
𝑖
), har qanday j uchun 
∑
𝑎
𝑖,𝑗
𝑛
𝑖=1
= 𝑑(𝑣
𝑗
) va ∑
∑
𝑎
𝑖,𝑗
𝑛
𝑗=1
𝑛
𝑖=1
= 2𝑚, ya’ni qoʻshnilik matritsasining har qanday qatori yoki 
ustunidagi birlar soni grafning tegishli vertikal darajasiga teng va ularning umumiy soni uning 
qirralarining ikki baravariga teng. 
Misol sifatida –rasmda berilgan 
𝐺 grafning A qoʻshnilik matritsasini 𝑑𝑒𝑔𝑣
𝑖
darajalar ketma-
ketligini yozamiz.
21-rasm. Grafni qoʻshnilik matritsasi orqali tasvirlash 
Graflarning ayrim turlarining qoʻshnilik matritsalarini qarab chiqaylik. Boʻsh graf 
𝑂
𝑛
qoʻshnilik matritsasi faqat nollardan iborat, ya’ni A (
𝑂
𝑛
) = 
0
𝑛
.
𝐾
𝑛
toʻliq grafning qoʻshnilik matritsasi faqat dioganal elementlari birlardan iborat, qolgan 
elementlari nolga teng boʻladi. Buni 
𝐴(𝐾
𝑛
) = 1
𝑛
- 
𝐼
𝑛
deb yozamiz. Agar graf bogʻlanmagan boʻlsa 
𝑠 komponentlarga ega boʻlsa, unda satrlar va ustunlarni qayta tartibga solish orqali uning 
qoʻshnilik matritsasisini blok-diagonal shaklga keltirilishi mumkin: 

---

Bu yerda har bir 
𝐴
𝑖𝑖
diagonal bloki 
𝑠
𝑖
komponentining qoʻshnilik matritsasi. 
𝑘-qismli graf 
holatida qoʻshnilik matritsasini blokli shaklga keltirish mumkin, agar asosiy diagonal boʻylab faqat 
"nol" bloklar kelsa: 
Masalan, 22-rasmda 
{𝑣1, 𝑣2}, {𝑣3, 𝑣4, 𝑣5}, {𝑣6, 𝑣7} boʻlaklar va unga qoʻshnilik matritsasi 
A boʻlgan uch qismli G graf koʻrsatilgan.