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.
22-rasm. Grafni qoʻshnilik matritsasi orqali tasvirlash
Qoʻshnilik matritsasining bir xil analogi Kirxgof
matritsasi
, n tartibli kvadrat matritsa sifatida aniqlangan, uning elementlari
{
𝑑
Qoʻshnilik matritsasi
va Kirxgof matritsasi oʻrtasidagi
bogʻliqlik,
𝐷
shaklga
ega,
bu
yerda
𝐷 𝑑 𝑑
𝑑
𝑑
, ya‘ni bu diagonali elementlari
mos keladigan uchlar darajalariga teng boʻlgan matritsa. Kirxgof
matritsasining muhim xususiyati (har qanday satr va har bir ustun
elementlari yigʻindisi nolga teng boʻlgan
boshqa har qanday matritsa
kabi) matritsaning barcha elementlarining algebraik qoʻshimchalari bir-
biriga teng boʻlishidir.
Izomorf graflar faqat mos mavhum graf uchlarini belgilashda
(raqamlashda) farq qilganligi sababli, ularning qoʻshnilik
matritsalarini
(Kirxgof matritsalari) bir-biridan satrlar va ustunlarni biroz almashtirish
orqali olish mumkinligi aniq boʻladi.
1 dan n gacha raqamlangan G grafning qoʻshnilik matritsasi
kvadrat kattalikdagi A matritsasi boʻlib, unda a [i][j] elementining
qiymati 1 ga teng boʻlsa, grafning i- va j- uchlari qoʻshni boʻladi, aks
holda qiymati nolga teng boʻladi.
Bunday matritsa binar matritsa deb
88
ham ataladi. Oddiy graf uchun asosiy diagonal elementlari 0 ga teng
boʻladi.
Qoʻshnilik
matritsasi
orgrafni
tavsiflash
uchun
ham,
yoʻnaltirilmagan
grafni
tasvirlash
uchun
ham
mos
keladi.
Yoʻnaltirilmagan graf uchun elementlarning
qiymatlari asosiy
diagonalga nisbatan nosimmetrikdir.
Qoʻshnilik matritsadan foydalanish faqat qirralari koʻp boʻlmagan
hamda murakkab boʻlmagan graflar uchun afzalroqdir, chunki u har bir
element uchun bitta bit saqlashni talab qiladi. Agar graf murakkab
boʻlsa, unda xotiraning katta qismi nollarni saqlashga sarflanadi, ammo
murakkab graflarda qoʻshnilik matritsasi
grafni xotirada ixchamroq
ifodalaydi va taxminan
bit xotiradan foydalanadi. Ushbu kattalik
qoʻshnilik roʻyxatlariga qaraganda yaxshiroq (pastga qarang).
