6-ma’ruza. Graflar nazariyasi elementlari va o'tish algoritmlari

25-rasm. Yoʻnaltirilmagan grafda insidentlik matritsasi




26-rasm. Orgrafda insidentlik matritsasi

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
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.

Amal	Qoʻshnilik roʻyxati	Qoʻshnilik matritsasi