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.
