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. Yoʻnaltirilmagan grafda 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. 
 
 
 
 
 
 
 
 
 
 
 
23-rasm. Yoʻnaltirilgan grafda qoʻshnilik matritsasi 
Insidentlik matritsasi. Insidentlik matritsasi - bu grafning elementlari (qirra - uch) 
orasidagi bogʻlanishlar koʻrsatiladigan grafni tasvirlash shakli. Matritsaning ustunlari qirralarga, 
satrlar uchlarga toʻgʻri keladi. Demak, matritsa kvadrat boʻlmaydi. Matritsa yacheykasidagi nolga 
teng boʻlmagan qiymat uch va qirra (ularning insidentligi) oʻrtasidagi munosabatni bildiradi. 
Graflar insidentlik matritsasini 
𝑛𝑥𝑚 oʻlchamdagi 𝐵 = [𝑏
𝑖,𝑗
] toʻrtburchaklar matritsasi 
sifatida aniqlaylik, bunda 
𝑏
𝑖,𝑗
elementi 1 ga teng, agar 
𝑒
𝑗
insident qirraning 
𝑣
𝑖
uchi boʻlsa, aks 
holda 0 boʻladi. B matritsasining satrlari insidentlik vektorlari deb nomlanadi va 
𝐵
𝑖
bilan 
belgilanadi. 23-rasmda 21-rasmdagi kabi bir xil G graf koʻrsatilgan va uning B insidentlik 
matritsasi koʻrsatilgan. 

---

 
24-rasm. Grafda insidentlik matritsasi 
Ta’rifdan koʻrinib turibdiki, insidentlik matritsasidagi birlarning umumiy soni graf 
qirralarining ikki baravariga teng, har qanday satrdagi birlar miqdori mos uchlar darajalariga teng, 
ustunlar esa ikkita birdan iborat. 
Shuning uchun matritsa satrlari orasida oddiy munosabat mavjud: har qanday satr 
elementlarini ikki modulli qoʻshish orqali qolgan satrlarning bir xil elementlarining qoʻshnilarini 
olish mumkin. Insidentlik vektori tushunchasidan foydalangan holda, 
𝐵
𝑖
= (∑ 𝐵
𝑗
) (mod 2), bu 
yerda 
1 ≤ 𝑗 ≤ 𝑛 va 𝑗 ≠ 𝑖. Shunday qilib, yuqoridagi matritsa uchun bizda: 𝐵
1
= 𝐵
2
⊕ 𝐵
3
⊕
𝐵
4
⊕ 𝐵
5
= [1,0,0,1,1,0,0] ⊕ [0,1,0,1,0,1,0] ⊕ [0,0,1,0,1,1,1] ⊕ [0,0,0,0,0,0,1] =
[1,1,1,0,0,00]. 
Bogʻlanmagan grafning insidentlik matritsasi, xuddi qoʻshnilik matritsasi singari, blok-
diagonali koʻrinishga keltirilishi mumkin, bu yerda har bir diogonal blok ba’zi bir bogʻlangan 
komponentlarning insidentlik matritsasi hisoblanadi. 
Grafda parallel qirralar boʻlmaganligi sababli, agar 
𝑣
𝑖
va 
𝑣
𝑗
uchlar qoʻshni boʻlsa, har qanday 
𝐵
𝑖
𝐵
𝑗
insidentlik vektorlari jufligi skalar koʻpaytmasi birga teng boʻladi va agar bu uchlar qoʻshni 
boʻlmasa, skalar koʻpaytma nolga teng boʻladi. Binobarin, 
𝐵𝐵
𝑇
koʻpaytma graflarning qoʻshnilik 
matritsasiga toʻgʻri keladigan mos darajalariga teng boʻlgan diagonal elementlar bundan mustasno. 
Yoʻnaltirilgan graf holatida tegishli ustundagi har bir uch chiquvchi x vertikal qatorida "−1" 
va kiruvchi y uch qatorida "1" qiymatiga ega; agar uch va qirra oʻrtasida hech qanday bogʻliqlik 
boʻlmasa, unda mos keladigan katak "0" qiymatiga ega boʻladi.