|
Mustaqil ish mavzu: Marshurutlar va ularning vazifalari Qabullagan: Bajargan: nukus-2024
|
| bet | 3/5 | | Sana | 20.05.2024 | | Hajmi | 254,53 Kb. | | #244908 |
Bog'liq marshrut Asoslarning tarkibi, tuzilishi va nomlanishi. 7 - sinf , asl, Buxoro tarixi, tarmoq xavsizligi 3, 98380, 117-royxat, Tasdiqlayman, CHEVARXONA, amaliy ish, word, Dif. tenglamalar-2024 (2), visual studio, ehtimol topshiriq, diskretOxirgi qadam. Berilgan orgrafda 1 belgili uchdan 6 belgili uchgacha eng qisqa uzunlikka ega yo‘l(lar)ni topish maqsadida,
algoritmga asosan, grafning oxirgi 6 belgili uchidan boshlab ajratilgan yoylar yo‘nalishiga qarama-qarshi yo‘nalishda harakatlanib, uning 1 belgili uchiga kelishimiz kerak. 6 belgili uchga kiruvchi uchta yoydan
faqat bittasi ( (4, 6)
yoy) ajratilgan bo‘lgani uchun
(4, 6)
yoy yo‘nalishiga
qarama-qarshi yo‘nalishda harakat qilib, 6 belgili uchdan 4 belgili
uchga kelamiz. 4 belgili uchga kiruvchi ikkala ( (1, 4) va (3, 4) ) yoylar
ham ajratilgan bo‘lgani uchun biz tuzmoqchi bo‘lgan eng qisqa uzunlikka ega yo‘l yagona emas.
algoritmga asosan, grafning oxirgi 6 belgili uchidan boshlab ajratilgan yoylar yo‘nalishiga qarama-qarshi yo‘nalishda harakatlanib, uning 1 belgili uchiga kelishimiz kerak. 6 belgili uchga kiruvchi uchta yoydan
faqat bittasi ( (4, 6)
yoy) ajratilgan bo‘lgani uchun
(4, 6)
yoy yo‘nalishiga
qarama-qarshi yo‘nalishda harakat qilib, 6 belgili uchdan 4 belgili
uchga kelamiz. 4 belgili uchga kiruvchi ikkala ( (1, 4) va (3, 4) ) yoylar
ham ajratilgan bo‘lgani uchun biz tuzmoqchi bo‘lgan eng qisqa uzunlikka ega yo‘l yagona emas.
Agar harakatni
(1, 4)
yoy yo‘nalishiga teskari yo‘nalishda davom
ettirsak, u holda 4 belgili uchdan 1 belgili uchga kelib, eng qisqa
uzunlikka ega yo‘llardan biri bo‘lgan
1 (1, 4, 6)
marshrutni topamiz.
Agarda harakatni
(3, 4)
yoy yo‘nalishiga teskari yo‘nalishda davom
ettirsak, u holda 4 belgili uchdan 3 belgili uchga kelamiz. 3 belgili
uchga kiruvchi ikkita yoydan faqat bittasi ( (5, 3) yoy) ajratilgan bo‘lgani
uchun 3 belgili uchdan 5 belgili uchga kelamiz. Shu usulda davom etsak, oldin 2 belgili, keyin esa 1 belgili uchga o‘tib mumkin bo‘lgan eng qisqa uzunlikka ega bo‘lgan yo‘llardan ikkinchisini, ya’ni
2 (1, 2, 5, 3, 4, 6) marshrutni aniqlaymiz.
Shunday qilib, 2- shaklda tasvirlangan grafda eng qisqa uzunlikka
|
| |
