Mavzu: Bog‘langan graflarga marshrutlar, ularni narxi bo‘yicha baholash. “Xasis” algoritmlar. Eng qisqa marshrutni aniqlash algoritmi. Uni variantlar soni bo`yicha hajmini baholash. Maqsad

12-Amaliy ish
Mavzu: Bog‘langan graflarga marshrutlar, ularni narxi bo‘yicha baholash. “Xasis” algoritmlar. Eng qisqa marshrutni aniqlash algoritmi. Uni variantlar soni bo`yicha hajmini baholash.
Maqsad: Talabalar graf uchun minimal narxli daraxtlar skeletini qurish algoritmini o’rganishi, Kruskal va Primo algoritmlarini bilan ishlashni o‘rganishi, bu algoritmlar haqida bilim va ko‘nikmalarga ega bo‘lishi hamda mustaqil masalalar yechishi va shu masalaga mos algoritmlar qura olishi kerak.
Amaliy ishini bajarish uchun zarur jihozlar. Zarur dasturiy ta’minot (C++ dasturlash tili kompilyatori, matn muharriri) o‘rnatilgan personal kompyuter, amaliy ishini bajarish bo‘yicha (ushbu) uslubiy ko‘rsatma
Zarur nazariy ma’lumotlar.
Kruskal algoritmi.
Ushbu algoritm 1956 yili Kruskal tomonidan ishlab chiqilgan. Faraz qilamiz, V = {1, 2, .... n} tugunlar to‘plamidan iborat va E qirralar to‘plamida aniqlangan s narx funksiyasi bilan berilgan G=(V, E) bog‘langan graf bo‘lsin. Kruskal algoritmida G graf uchun minimal narxli daraxtlar skeletini qurish G grafning faqat n ta tugunlaridan tashkil topgan va qirralari bo‘lmagan T=(V, ø) grafdan boshlanadi. Shunday qilib, har bir tugun bog‘langan (o‘zi-o‘zi bilan) komponent hisoblanadi. Algoritm bajarilishi vaqtida bog‘langan komponentlar naboriga ega bo‘lamiz, asta-sekin birlashtirib daraxtlar skeletini tashkillashtiramiz.
Asta-sekin o‘suvchi bog‘langan komponentlarni qurishda E to‘plamdan qirralar ularning narxi o‘sishi tartibida navbatma-navbat tekshiriladi. Agar navbatdagi qirra turli komponentlardagi ikkita tugunni birlashtirsa, u holda bu qirra T grafga qo‘shiladi. Agar bu qirra bitta komponentning ikkita tugunini birlashtirsa, u tashlab yuboriladi, chunki uning bog‘langan komponentga qo‘shilishi sikl hosil bo‘lishiga olib keladi. G grafning barcha tugunlari bitta komponentga tegishli bo‘lsa, T minimal narxli daraxtlar skeletini qurish bu graf uchun tugaydi.
Primo algoritmi
Ushbu algoritm dastlab 1930 yilda chesh matematigi Voysex Yarnik tomonidan taklif etilgan. Keyin Robert Primo tomonidan 1957 yilda qayta ko’rib chiqilgan va ulardan tashqari E. Deykstra tomonidan 1959 yilda ishlab chiqilgan.
Kruskal algoritm "ochko'z" algoritm anglatadi. o'sha mohiyati - har qadamda eng yuqori g'alaba. Har doim emas, "ochko'z" algoritmlarni muammo uchun eng yaxshi yechim beradi. a nazariyasi aniq vazifalar, ularning qo'llash ular optimal yechim berish, deb ko'rsatib, bor. Bu matroids nazariyasi hisoblanadi. Kruskal algoritmi shu kabi muammolari bilan bog'liq.
Algoritm kirishiga yo’naltirilmagan og’irlikka ega bo’lgan graf uzatiladi.

1. 
   Boshida istalgan tugun olinadi va unga tegishli bo’lgan eng kam vaznga ega insident yoy topiladi. Topilgan yoy va unga tegishli tugunlar daraxtni shakllantira boshlaydi.
   
2. 
   Keyin bir uchi bilan daraxtga tegishli bo’lgan tugunlariga tutashgan va ikkinchi uchi esa tutashmagan boshqa yoylar xam tekshiriladi. Ulardan og’irligi kami tanlanadi.
   
3. 
   Xar bir qadamdagi yoy daraxtga qo’shilib boraveradi. Daraxtning balandligi xam 1 taga oshib boraveradi. Grafning barcha tugunlari ko’rib chiqilmaguncha algoritm davom etaveradi.
   

Algoritm natijasi bo’lib minimal narxli daraxt skeleti xisoblanadi. E’tibor qaratish lozimki, minimal narxli daraxtlarni hosil qilishda xalqa paydo bo’lishiga yo’l qo’ymaslik kerak.

Amaliy topshiriqlari va

ish davomida ishlab chiqiladigan dasturning to‘liq namunasi.