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

7-jadval.
Qoʻshnilik matritsasi va roʻyxatining algoritmlarda bajarilishini taqqoslash 
Amal 
Qoʻshnilik roʻyxati 
Qoʻshnilik matritsasi 
(x,y) qirraning mavjudligini tekshirish 
O(|V|+|E|) 
O(1) 
Qirraning darajasini hisoblash 
O(1) 
O(|V|) 
Sodda grafilar uchun xotiradan foydalanish 
O(|V|+|E|) 
O(|V|
2
) 
Graflarda oʻtish 
O(|V|+|E|) 
O(|V|
2
) 
Mavzu yuzasidan savollar: 
1. Graflarning umumiy ta’rifini bering. 
2. Grafning eng asosiy tushunchalariga toʻxtalib oʻting 
3. Qoʻshnilik roʻyxati va qoʻshnilik matritsasini hosil qilish jarayonini tushuntirib bering 
4. Insidentlik matritsasi qanday hosil qilinadi? 
5. Graflar qoʻllaniladigan sohalarni sanang. 
Mustaqil ishlash uchun masalalar: 
Quyida berilgan graflar boʻyicha berilgan vazifalarni hal qiling: 
1) Berilgan grafning barcha tushunchalarini keltiring (uchlar, qirralar, grafning yoʻnalishga 
ega yoki yoʻqligi boʻyicha aniqlanishi, yakkalangan uch mavjudligi, regular yoki regular 
emasligi va hokazo). 
2) Grafni mashina xotirasida tasvirlash 

---

3) Grafni uchlar qoʻshniligi matritsasi orqali tasvirlang 
4) Grafni qoʻshnilik roʻyxati orqali tasvirlash 
5) Grafning insidentlik matritsasi orqali tasvirlash 
a) b) 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
c)
 
 
 
 
d)
 
 
 
 
 
e) 

f) 
 
 
 
 
 
 
 
g)