Dots., t f. n. Boynazarov I. M. Ma’ruza rejasi Plan lecture

Ma’lumotlar tuzilmasi Data structures

13-mavzu: Ma’lumotlarning tarmoqli tuzilmalari. Graflar tushunchasi va unig ko’rinishlari.

Dots., t.f.n. Boynazarov I.M.

Ma’ruza rejasi Plan lecture

• Asosiy tushunchalar.
• Graflarni tafsiflash. Qo’shnilik matritsalari.
• Grafning amaliy masalalarga tadbiqi.

Asosiy tushunchalar

• Juda ko’plab masalalarning (m-n, geometrik) yechimini olish uchun odatda qog’ozga inson, shahar, kimyoviy narsalarni anglatuvchi nuqtalar va ularni tutashtiruvchi (strelkali) chiziqlarni chizamiz. Natijada hosil bo’lgan chizma graf deb ataladi.
• Graf – bu tugunlar va ularni bog’lovchi yoylar to’plami hisoblanadi.

Asosiy tushunchalar

• Nuqtalar tugunlar yoki cho’qqilar deyiladi, chiziqlar esa – qirralar yoki yoylar deb ataladi.
• Tugunlarga kirish darajasi – tugunga kiruvchi yoylar soni, chiqish darajasi – tugundan chiquvchi yoylar soni.
• Barcha tugunlar juftliklari orasida yoylar mavjud bo’lgan Graf – to’liq graf deyiladi.
• Ixtiyoriy (yoki yo’naltirilmagan) graf G bilan belgilanadi va G:=(V,E) juflik orqali aniqlanadi. Bu yerda V – tugunlarning bo’sh bo’lmagan to’plami, E – tartiblanmagan tugunlar juftliklari orasidagi yoylar (yo’llar) to’plami.

Graflarning turlari

• Agar yoylar yo’nalishga ega bo’lsa (bir tomonlama harakat mavjud bo’lgan avtomobil yo’li), bunday graflar yo’naltirilgan graf yoki orgraf deb nomlanadi.
• Ikkita i va j (qo’shni bo’lmagan) tugunlarni tutashtiruvchi yoylar ketma-ketligi zanjir deb ataladi.
• Yo’naltirilgan graflarda bunday ketma-ketlik “yo’l” deyiladi.

Graflarning turlari

• Agar grafning ixtiyoriy tugunlar juftligi orasida zanjir mavjud bo’lsa, bunday graf bog’langan deyiladi.
• Agar graf bog’lanmagan bo’lsa, u holda uni k ta bog’langan komponentlarga ajratish mumkin, bu komponentlar k-bog’langan deyiladi.