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


Download 11.23 Kb.
bet1/4
Sana31.01.2024
Hajmi11.23 Kb.
#1832516
  1   2   3   4
Bog'liq
13-мавзу Graf

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.

Download 11.23 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling