Algoritmlarni loyihalashtirish

Algoritmlarni loyihalashtirish

MUHAMMED AL-XORAZMIY NOMIDAGI TOSHKENT INFORMACION TEXNOLOGIYALARI UNIVERSITETI
“ALGORITMLARNI LOYIHALASHTIRISH” FANI BO’YICHA


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

Tayorladi: Abdukarimov Sardor

032-19 guruh
Qabul qildi: Mirzayev A.N

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

Reja:

• 
  Graflar haqida
  
• 
  Deykstra algoritmi va Bellman-Ford algoritmi haqida
  
• 
  Graflarni eniga va bo’yiga aylanishi
  

Graflar haqida

• 
  Graflar
  
• 
  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.
  

К
С
О
И
Н

Graflar haqida

• 
  Tarmoq
  
• 
  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
  

I
II
III
IV

Deykstra algoritmi

• 
  Gollandiyalik olim Edsger Deykstra algoritmi grafning boshlang’ich berilgan tugunidan boshlab qolgan barcha tugunlargacha bo'lgan barcha eng qisqa yo'llarni topadi.Uning yordamida, agar barcha zarur ma'lumotlar berilgan bo'lsa, masalan, neft va shu kabi mahsulotlarni eksport qilish uchun bitta shahardan boshqa shaharlarning har biriga borish uchun qaysi yo'llar ketma-ketligini tanlash afzalroq ekanligini bilib olish mumkin. Ushbu usulning salbiy tomoni shundaki, manfiy vaznga ega bo’lgan qirralari mavjud bo'lgan graflarni qayta ishlash imkonining mavjud emasligi, ya'ni, masalan, ba'zi tizim birorta kompaniya uchun foydasiz bo'lgan marshrutlarni taqdim qilsa, u holda u bilan ishlash uchun Deykstraning algoritmidan foydalanib bo’lmaydi.