-rasm. Yoʻnaltirilmagan grafda insidentlik matritsasi

91 
Qoʻshnilik roʻyxati. 
Qoʻshnilik roʻyxati - bu grafni uchlar roʻyxati 
("roʻyxatlar roʻyxati") toʻplami sifatida koʻrsatish usuli - grafning har bir 
uchi qoʻshni uchlar roʻyxatiga toʻgʻri keladi. Masalan, 1-rasmni biz 
quyidagi qoʻshnilik roʻyxati bilan tavsiflashimiz mumkin: 
a: {b, c, d, e} 
b: {a} 
c: {a, d} 
d: {a, c, e} 
e: {a, f} 
f: {e} 
Bu sodda graflarni aks ettirish uchun ham, grafni kenglik yoki 
chuqurlikda bosib oʻtish uchun asosiy algoritmlarni amalga oshirish 
uchun ham eng qulay usuldir, bu yerda siz hozirda koʻrib chiqilgan 
uchning "qoʻshnilarini" tezda olishingiz kerak. 
Koʻpgina masalalarni yechishda matritsalar bilan bir qatorda 
graflarni aks ettirish uchun qirralar roʻyxati (insidentlik roʻyxati) va 
uchlar roʻyxati (qoʻshnilik roʻyxat) ishlatiladi. Shunday qilib, -rasmda 
ushbu roʻyxatlar berilgan: 
5-jadval.
Qirralar roʻyxati
6-jadval.
Uchlar roʻyxati 

92 
Qirralarning roʻyxatida har bir oxirgi uch juft uchlar bilan 
ifodalanadi, qoʻshnilik roʻyxatida esa har bir uch uchun unga qoʻshni 
boʻlgan barcha uchlar koʻrsatiladi. Agar har bir ustunda ikkala birlikni 
tegishli uchlar (qatorlar) belgisi bilan almashtirsak va nollarni olib 
tashlasak qirralarning roʻyxati insidentlik matritsasining ixcham yozuvi 
deb taxmin qilishimiz mumkin boʻladi. Xuddi shunday agar har bir 
satrda boʻlgan birlar mos keladigan uchlar (ustun) belgisi bilan 
almashtirilsa va nollar olib tashlansa, qoʻshnilik matritsasidan uchlar 
roʻyxatini olish mumkin. 

Download 4,61 Mb.