• TOSHKENT-2024 Mustaqil ish Mavzu: Graflarni eniga va bo’yiga aylanishi (tekshirish) Reja
    		•

    Eng qisqa masofani aniqlash misolini ko’rib chiqaylik. Shahar viloyatlarini birlashtiruvchi avtomobil yo’llari tarmog’I berilgan bo’lsin. Ba’zi yo’llar bir tomonlama




    Download 0,79 Mb.
    bet1/6
    Sana19.05.2024
    Hajmi0,79 Mb.
    #243966
      1   2   3   4   5   6
    Bog'liq
    Navoiyeva Vasila


    O‘ZBEKISTON RESPUBLIKASI
    RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
    MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI NURAFSHON FILIALI



    “Kompyuter injiniringi” fakulteti


    Guruh nomi: 210-22.
    F.I.SH: Navoiyeva Vasila
    Fan: Algoritmlarni loyihalash


    TOSHKENT-2024
    Mustaqil ish

    Mavzu: Graflarni eniga va bo’yiga aylanishi (tekshirish)




    Reja
    Kirish
    Nazariy qism 

    1. Graflar haqida

    2. Deykstra algoritmi va Bellman-Ford algoritmi haqida

    3. Graflarni eniga va bo’yiga aylanishi



    Kirish
    Eng qisqa masofani aniqlash misolini ko’rib chiqaylik. Shahar viloyatlarini birlashtiruvchi avtomobil yo’llari tarmog’I berilgan bo’lsin. Ba’zi yo’llar bir tomonlama. Shahar markazidan har bir viloyatga eng qisqa yo’lni topishimiz zarur.
    Keltirilgan masalani yechishda Deykstraning algoritmidan foydalanishimiz mumkin. Algoritm graflarga asoslangan bo’lib, u 1959 yil niderlandiyalik olim E. Deykstra tomonidan yaratilgan. U grafning bitta uchidan boshqa uchlarigacha eng qisqa masofani aniqlaydi, bunda grafning quvurg’alari manfiy og’irlikka ega bo’lmasligi lozim. Bizdan birinchi uchdan qolganlariga borishning qisqa masofasini toppish talab qilinsin.
    Graf – bu tugunlar va qirralar (tugunlar juftligini birlashtiruvchi) to’plamidan iborat bo’lgan abstrakt matematik ob’ektdir.
    Grafning elementlari tarkibi va munosabatlar tuzilishi beriladi.Grafning tarkibiy qismlari bu uning tugunlari va qirralaridir. Bir nechta juft tugunlararo qirralardan iborat bo’lgan turlicha yo’llar to’plami mavjud bo’lishi mumkin. Yopiq yo’llar – sikllarning mavjud bo’lishi tarmoqlarga xos xususiyatdir.
    Yonaltirilmagan graf yoki simmetrik bog’liqlik Yonaltirilmagan graf yoki nosimmetrik bog’liqlik qirrayoylar Ilmoq – aynan bitta tugundan chiqib, yana shu tugunga kiruvchi qirra



    Download 0,79 Mb.
      1   2   3   4   5   6




    Download 0,79 Mb.
    Bosh sahifa
    Aloqalar
        Bosh sahifa
    Dərs
    Mühazirə
    Qaydalar
    Referat
    Xülasə
    Yazı


    Eng qisqa masofani aniqlash misolini ko’rib chiqaylik. Shahar viloyatlarini birlashtiruvchi avtomobil yo’llari tarmog’I berilgan bo’lsin. Ba’zi yo’llar bir tomonlama

    Download 0,79 Mb.