Mustaqil ish Mavzu: “Graflarni eniga va bo’yiga aylanishi (tekshirish)” Bajardi: 030-19 guruh talabasi Boynazarov Jalil Tekshirdi Mirzayev A. N toshkent 2022-yil Reja
O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUXAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
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
