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.
