1-ma’ruza. Graflar nazariyasi elementlari va o'tish algoritmlari. Grafni aniqlanishi orientirlangan va orientirlanmagan graflar. Lokal daraja. Yo`l va sikl. Grafni mashina xotirasida ifodalash usullari

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.