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

(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)

7-jadval. Qoʻshnilik matritsasi va ro’yxatining algoritmlarda bajarilishini taqqoslash

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. 
   2.1) Grafni uchlar qo’shniligi matritsasi orqali tasvirlang
   
4. 
   2.2) Grafni qo’shnilik ro’yxati orqali tasvirlash
   
5. 
   2.3) Grafning insidentlik matritsasi orqali tasvirlash
   

a ) b)



c)