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.
-
- 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.
Do'stlaringiz bilan baham: |
