86
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 (
) =
.
toʻliq grafning qoʻshnilik matritsasi
faqat dioganal elementlari
birlardan iborat, qolgan elementlari nolga teng boʻladi. Buni
=
-
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:
87
Masalan, 22-rasmda
{ }
,
{ }
,
{ }
boʻlaklar va
unga qoʻshnilik matritsasi A boʻlgan uch qismli G graf koʻrsatilgan.
