|
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
|
| bet | 1/6 | | Sana | 19.05.2024 | | Hajmi | 0,79 Mb. | | #243966 |
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
Graflar haqida
Deykstra algoritmi va Bellman-Ford algoritmi haqida
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
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
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
|
