Mavzu: Grafning metrik xarakteristikalari

3- iteratsiya. Boshlang‘ich uchi to‘plamga tegishli, oxiri esa to‘plamga tegishli bo‘lgan yoylar to‘rtta: , , va . Shu yoylarga mos ning qiymatlari , , , va, shuning uchun, bo‘ladi. Demak, bu iteratsiyada yoyni ajratamiz va deb olamiz. Endi, algoritmga ko‘ra, va to‘plamlarni hosil qilamiz.
Ikkala uchi ham to‘plamga tegishli bo‘lgan yoylar oltita: , , , , va . Bu yoylarning har biri uchun tengsizlikning bajarilishini tekshirishimiz kerak. Lekin, 1- va 2- iteratsiyalarda , va yoylar uchun bu ish bajarilganligi sababli tekshirishni tarkibida belgili uch qatnashgan , va yoylar uchun amalga oshirib, quyidagilarga ega bo‘lamiz: yoy uchun munosabat to‘g‘ri ( ), yoy uchun munosabat to‘g‘ri ( ), lekin yoy uchun munosabat noto‘g‘ri ( ). Oxirgi munosabatni hisobga olib, algoritmga ko‘ra o‘rniga deb olamiz va yoyni ajratilgan deb, ilgari ajratilgan yoyni esa ajratilmagan deb hisoblaymiz (3- shaklda yozuvning va yoyning qalin chiziq’i ustiga ajratilganlikni inkor qiluvchi belgisi qo‘yilgan).
4- iteratsiya. , bo‘lgani uchun va , , , hamda bo‘ladi. Demak, va yoylarni ajratamiz hamda 4 belgili uchga qiymatni mos qo‘yamiz. Natijada , to‘plamlarga ega bo‘lamiz.

munosabatning to‘g‘riligi , , , , va yoylar uchun tekshirilib ko‘rilganda, uning barcha yoylar uchun bajarilishi ma’lum bo‘ladi.
5- iteratsiya. Endi bo‘lgani uchun , , va bo‘ladi. Bu yerda minimum yoyda erishilgani uchun uni ajratib, orgrafning oxirgi belgili uchiga qiymatni mos qo‘yamiz.
Oxirgi qadam. Berilgan orgrafda 1 belgili uchdan 6 belgili uchgacha eng qisqa uzunlikka ega yo‘l(lar)ni topish maqsadida, algoritmga asosan, grafning oxirgi belgili uchidan boshlab ajratilgan yoylar yo‘nalishiga qarama-qarshi yo‘nalishda harakatlanib, uning 1 belgili uchiga kelishimiz kerak. belgili uchga kiruvchi uchta yoydan faqat bittasi ( yoy) ajratilgan bo‘lgani uchun yoy yo‘nalishiga qarama-qarshi yo‘nalishda harakat qilib, belgili uchdan belgili uchga kelamiz. belgili uchga kiruvchi ikkala ( va ) yoylar ham ajratilgan bo‘lgani uchun biz tuzmoqchi bo‘lgan eng qisqa uzunlikka ega yo‘l yagona emas.
Agar harakatni yoy yo‘nalishiga teskari yo‘nalishda davom ettirsak, u holda belgili uchdan belgili uchga kelib, eng qisqa uzunlikka ega yo‘llardan biri bo‘lgan marshrutni topamiz.
Agarda harakatni yoy yo‘nalishiga teskari yo‘nalishda davom ettirsak, u holda belgili uchdan belgili uchga kelamiz. belgili uchga kiruvchi ikkita yoydan faqat bittasi ( yoy) ajratilgan bo‘lgani uchun belgili uchdan belgili uchga kelamiz. Shu usulda davom etsak, oldin belgili, keyin esa belgili uchga o‘tib mumkin bo‘lgan eng qisqa uzunlikka ega bo‘lgan yo‘llardan ikkinchisini, ya’ni marshrutni aniqlaymiz.
Shunday qilib, 2- shaklda tasvirlangan grafda eng qisqa uzunlikka ega va yo‘llar borligini aniqladik. Bu yo‘llarning har biri minimal uzunlikka ega. ■