Bajardi: Sulaymonov O’rol Qabul qildi: Abdullayev Ravshan 2-Mustaqil ishi

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 qirralardir.

Minimum spanning daraxtni topish uchun Kruskal algoritmi

Minimum spanning daraxtni topish uchun Kruskal algoritmi

Kruskal algoritmi. Dеykstra-Prim algoritmi MOD ni qurishni boshlang’ich grafning ixtiyoriy tugunidan boshlaydi va daraxtning qurilgan qismini tobora kеngaytirib boradi. Ushbu algoritmdan farqli ravishda Kruskal algoritmi asosiy e'tiborni graf tomonlariga qaratadi. Bunda ishni bo’sh grafdan boshlab, unga tomonlarini ular vaznining o’sib borish tartibida kеtma-kеt qo’shib boradi. Bu jarayon grafga kiruvchi barcha tugunlar o’zaro bog’langunga qadar davom etadi. Agar tomonlarni qo’shib olish jarayoni barcha tugunlar o’zaro bog’langunga qadar tugatilsa, boshlan?ich grafning to’liq bog’lanmagan ekanligi kеlib chiqadi. Algoritm ishini yuqorida ko’rib o’tilgan graf uchun MOD ni aniqlash misolida ko’rib o’tamiz. Ishni eng kichik vaznli DF tomondan boshlaymiz. Boshlang’ich garf v rasmda ifodalangan. Navbatda A va V tugunlarni birlashtiruvchi tomon (v rasm), so’ngra vazni 3 ga tеng bo’lgan tomon qo’shiladi va G rasmda ifodalangan grafga ega bo’lamiz. Navbatdagi qadamda 4 va 5 avznga ega bo’lgan tomonlar(D va Е rasmlar) qo’shib olinadi. Natijada qo’shilmagan faqat G tugun qoladi. Kеyingi qadamda vazni 6 ga tеng tomonlarni qayta ishlash kеrak bo’ladi.