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
∑
𝑑
, har
qanday j uchun
∑
𝑑
va
∑
∑
, ya‘ni
qoʻshnilik matritsasining har qanday qatori yoki ustunidagi birlar soni
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.
