Graflar va yo‘llar
Manzilga tezroq yeting. Hamma nuqtani kamroq xarajat bilan ulang. Qalamni uzmasdan chizing. Bir chizma — uch xil matematik savol.
Qaysi yo‘lning jami qiymati kichik?
Yo‘llar jadvali
| Yo‘l | Qiymat | Holat | Tanlash |
|---|
Masofalar jadvali
O‘zingizni tekshiring
Bu savollar chizmani o‘zgartirsangiz ham bir xil shartga ega. Javoblaringiz qurilmada tekshiriladi.
Tajriba daftari
Daftar faqat shu brauzerda saqlanadi. «Ochish» yozuvdagi grafni qayta tiklaydi.
Matematik g‘oyalar va tajriba chegaralari
1. Eng qisqa yo‘l
Graf — nuqtalar va ularni ulovchi yo‘llar. Har yo‘lga manfiy bo‘lmagan qiymat biriktirilgan. Deykstra algoritmi hali tasdiqlanmagan eng kichik masofani tanlaydi, keyin qo‘shni nuqtalar masofalarini yaxshilaydi.
Kenglik bo‘yicha qidirish (BFS) esa eng kam yo‘llar sonini topadi. Qiymatlar har xil bo‘lsa, bu yo‘lning jami qiymati eng kichik bo‘lishi shart emas. Bir nechta teng optimal yo‘l mavjud bo‘lishi mumkin.
2. Tejamkor tarmoq
Qamrovchi daraxt hamma nuqtani ulaydi va unda aylana yo‘q. Kruskal algoritmi yo‘llarni arzonidan boshlab ko‘rib chiqadi; aylana hosil qilmasa, uni oladi. Maqsad ikki nuqta orasidagi emas, butun tarmoqning jami qiymatini kamaytirish.
Graf bog‘lanmagan bo‘lsa, hamma nuqtani ulovchi daraxt yo‘q. Har bog‘langan qism uchun alohida minimal daraxt olinadi — bu minimal qamrovchi o‘rmon. Ayrim qismlar yolg‘iz nuqtadan iborat bo‘lishi mumkin.
3. Qalamni uzmasdan
Nuqtaning darajasi — unga tutash ochiq yo‘llar soni. Barcha yo‘llardan aynan bir marta o‘tish uchun yo‘li bor nuqtalar bitta bog‘langan qismda bo‘lishi va 0 yoki 2 ta nuqtaning darajasi toq bo‘lishi zarur va yetarli.
0 ta bo‘lsa — yopiq yurish; 2 ta bo‘lsa — ularning biridan boshlanib, boshqasida tugaydigan yurish. Nuqtaga bir necha marta qaytish mumkin. Yo‘lsiz yolg‘iz nuqtalar yurishga xalaqit bermaydi. Yo‘l qiymatlari bu savol uchun ahamiyatsiz.
Bu laboratoriya yo‘nalishsiz, o‘ziga qaytuvchi va parallel yo‘llarsiz graf bilan ishlaydi. Eng ko‘pi 20 ta nuqta va 100 ta yo‘l. Sonlar aniq butun qiymatlardir; chizmadagi geometrik uzunliklar hisobga olinmaydi. Avtomatik Eyler namoyishi hisoblangan yurishni tartib bilan ko‘rsatadi, algoritmning ichki stek amallarini emas.