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


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

Asosiy tushunchalar

  • Grafning qaysidir tuguni o’z-o’ziga zanjir bilan bog’lansa, bu sikl (yoki halqali) deb ataladi.
  • Halqasiz graf daraxt deyiladi.
  • Barcha mumkin bo’lgan yoylari berilgan graf to’liq deyiladi (masalan, n tuguni bo’lgan grafda n(n-1)/2 ta yoy mavjud bo’ladi).

Asosiy tushunchalar

  • Amaliy masalalarni yechishda odatda har bir yoy ma’lum vazn (og’irlik)ga (yoki uzunlikka) ega bo’lgan vaznli graflar (Weighted graph) qo’llaniladi. Bunday graflar tarmoq (to’r) deb ataladi.

Grafni tavsiflash

  • Graflarni tavsiflash uchun odatda ikki turdagi matritsalar qo’llaniladi - qo’shnilik matritsasi (vaznga ega bo’lmagan graflar uchun) va vaznli matritsa (vaznli graflar uchun).
  • N ta tugunli grafning qo’shnilik matritsasi (adjacency matrix)– bu N ga N o’lchamli matritsa hisoblanib, uning har bir (i,j) indeksli elementi i tugundan j tugunga yoy mavjud yoki mavjud emasligini ko’rsatuvchi mantiqiy qiymatlardan iborat bo’ladi.

Grafni tavsiflash

  • Vaznli graflar uchun tugunlar orasida bog’lanish bor yoki yo’qligini oddiy ko’rsatish yetarli emas. Bunday graflarni qayta ishlash uchun xotirada har bir yoyning vazni saqlash talab etiladi, masalan, biletning narxi yoki yo’l uzunligini. Buning uchun vazn matritsasi qo’llaniladi.
  • N ta tugundan iborat grafning vazn matritsasi – bu N ga N o’lchamli matritsa bo’lib, (i,j) indeksli har bir elementi i tugundan j tugungacha bo’lgan yoylarning “vazni”ga teng bo’lgan matritsa hisoblanadi.

Graflarning amaliy tadbiqlari: Prim-Kraskal masalasi

  • Masala. Tekislikda davlat xaritasi berilgan, unda aniq koordinataga ega n ta shahar mavjud. Barcha shaharlarni uzunligi eng qisqa bo’lgan telefon tarmog’i bilan bog’lash kerak.
  • Shaharlarni tugun (nuqta)lar orqali ifodalab olamiz. Telefon tarmog’i to’g’ridan to’g’ri emas, balki faqat telefon stantsiyalaridan tarqatiladi. Tarmoqda tsikl (xalqa) bo’lmaydi, umumiy uzunligi minimal bo’lgan qancha tarmoq talab etilishini aniqlash uchun telefon stantsiyasi o’zidan oldingilar bilan bog’langan deb faraz qilamiz.
  • Graflar nazariyasi nuqtai nazaridan bu masala quyidagicha bo’ladi:
  • n ta tugunli graf berilgan; yoylar uzunligi {dij}, i,j=1..n matritsada berilgan. Grafning barcha tugunlarini bog’lash mumkin bo’lgan yoylar to’plamini (u yoyilgan daraxt -spanning tree deyiladi) va ularning eng minimal uzunligini aniqlang.

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