Bajardi: Toshturdiyev Shahzod Toshkent 2022 Graf tayanch daraxtini qurishda minimal element mezoni Reja


Download 13.72 Kb.
bet1/6
Sana30.07.2023
Hajmi13.72 Kb.
#1663715
  1   2   3   4   5   6
Bog'liq
Bajardi Toshturdiyev Shahzod Toshkent 2022 Graf tayanch daraxti-fayllar.org


Bajardi: Toshturdiyev Shahzod Toshkent 2022 Graf tayanch daraxtini qurishda minimal element mezoni Reja

O’zbekiston Respublikasi Axborot Texnologiyalari va Kommunikatsiyalarini Rivojlantirish Vazirligi



Muhammad al-Xorazmiy nomidagi

Toshkent Axborot Texnologiyalari Universiteti

Nurafshon Filiali


Mustaqil ish


Mavzu: Graf tayanch daraxtini qurishda minimal element mezoni.



Bajardi: Toshturdiyev Shahzod
Toshkent 2022
Graf tayanch daraxtini qurishda minimal element mezoni
Reja:
  1. Graflarda eng qisqa yo’lni aniqlash haqida


  2. Graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili


  3. Floyd – Uorshell algoritmi


  4. Ford – Belmann algoritmi


  5. Deykstra algoritmi





Graflarda eng qisqa yo’lni aniqlash haqida
Graflar nazariysida eng qisqa yo’lni aniqlash muhim klassik masalalaridan biri deb hisoblanadi. Uni hisoblash va echimlarni topish uchun bir qancha algoritmlari mavjud.
Eng qisqa yo’l masalasi (inglizchada – shortest path problem) – bu grafning ikkita tugun orasidagi eng qichik yo’l (masofa, zanjir, marshrut) topish masalasidir, qaysidaki yoylarning vaznlarining yig’indisi minimal qiymatga ega. Qisqa (oddiy) zanjir geodezik zanjir ham aytiladi.
Ushbu masalani adabiyotlarda bir nechta boshqa nomlanishi ham uchratish mumkin: minimal masofa masalasi, dilijans masalasi, qisqa masofa masalasi va boshqalar.
Grafda eng qisqa masofani topish masalasi yo’naltirilgan, yo’naltirilmagan va aralash graflarda echimini aniqlash mumkin.
A)

B)


Grafda eng qisqa masofani topish masalasi.
A) yo’naltirilmagan grafda, B) yo’naltirilgan grafda.
Masalani formal quyilishi:
G = (V, E). Yuklanishga ega bo'lgan graf berilgan. E (i, j) xar bir yoyning og'irligi berilgan - wij
Boshlang'ich tugun sÎ V va oxirgi tugun dÎ V berilgan.
Ular orasidagi qisqa masofali yo'lni aniqlash talab etiladi. Yo'l uzunligi (path length, path cost, path weight) – unga kiruvchi yoylar yuklanishlari yig'indisiga teng (3 formula).
(3)

Berilgan grafning eng qisqa
masofani topish masalasining formal qo’yilishi.
Eng qisqa yo'lni aniqlash masalasi har hil masalalarda berilishiga qarab quyidagicha talafuzlarga ega bo’lish mumkin:

Download 13.72 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6




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