-rasm. Yoʻnaltirilmagan grafda qoʻshnilik matritsasi

89 
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 
va 
. Shunday qilib, yuqoridagi 
matritsa uchun bizda: 
. 

90 
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. 

Download 4,61 Mb.