• GURUH
  • 1. Graflarda eng qisqa yo’lni aniqlash haqida
  • Masalani formal quyilishi
  • Va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiya universitut




    Download 97.65 Kb.
    bet1/3
    Sana20.11.2022
    Hajmi97.65 Kb.
    #31013
      1   2   3
    Bog'liq
    Ma\'lumotlar tuzilmasi
    Informatika 00f9987, 2-sem maruza (7), elektrod potensial, Informatika va AT 2-dars, 01 O`zbekistonda inson huquqlari va erkinliklari kafolatinin 6 бет, 4-sinf texnologiya darsining 1 ta mavzusiga krassvord tuzish, Belbog’li kurash va Milliy kurash reja, Basketbol sport turining tarixi va rivojlanishi, Elektr yuritma asoslari. Xoshimov O.O, Nanoo’lchamli klasterlar va kristallar. Nanotexnologiyalar., Mamarajabov Muhammadali Botir o’g’li, 1

    O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI
    VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
    MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
    TEXNOLOGIYA UNIVERSITUT

    Mustaqil ish

    Mavzu: Graflarda eng qisqa yo’lni aniqlash masalalari. Graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili.

    GURUH:220-21
    BAJARDI: Turaev S
    TEKSHIRDI: Raxmanov A
    Tashkent-
    Reja:

    1. Graflarda eng qisqa yo’lni aniqlash haqida

    2. Graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili


    1. 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 vaznilarining 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. (rasm 11.)

    A)



    B)
    Rasm 11. 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)

    Rasm 12. 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 97.65 Kb.
      1   2   3




    Download 97.65 Kb.

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    Va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiya universitut

    Download 97.65 Kb.