Samarqand davlat universiteti o. R. Yusupov, I. Q. Ximmatov, E. Sh. Eshonqulov

184 
Bu 
12
h
, 
13
h
va 
14
h
miqdorlar orasida eng kichigi 
12
h
bo‗lgani uchun 
)
2
,
1
(
yoyni ajratamiz (3- shaklda bu yoy qalin chiziq bilan belgilangan) va 
2
belgili uchga 
2
2


qiymatni mos qo‗yamiz. Algoritmga ko‗ra 
2
uchni 
R
to‗plamdan chiqarib, 
R
to‗plamga kiritamiz. Natijada
7
}
2
,
1
{

R
va 
}
6
,
5
,
4
,
3
{

R
to‗plamlarga ega bo‗lamiz. 
Ikkala uchi ham 
R
to‗plamga tegishli bo‗lgan bitta 
)
2
,
1
(
yoy 
bo‗lgani uchun faqat bitta 
2
12
1




c
tengsizlikning bajarilishini 
tekshirish kifoya. Bu tengsizlik 
2
2
0


ko‗rinishdagi to‗gʻri 
munosabatdan iborat bo‗lgani uchun 2- iteratsiyaga o‗tamiz. 
2- iteratsiya.
)}
5
2
(
)
3
2
(
)
4
1
(
)
3
1
{(
)
(
,
,
,
,
,
,
,
R
R,

bo‗lgani sababli 
10
13

h
, 
13
14

h
, 
7
23

h
va 
11
25

h
qiymatlarni va 
7
}
,
,
,
min{
23
25
23
14
13


h
h
h
h
h
ekanligini 
aniqlaymiz. Bu yerda eng kichik qiymat 
)
3
,
2
(
yoyga mos keladi. 
Shuning uchun, 
)
3
,
2
(
yoyni ajratamiz va 
7
3


qiymatni 
3
belgili uchga 
mos qo‗yamiz. 
3
belgili uchni 
R
to‗plamdan chiqarib, 
R
to‗plamga 
kiritgandan so‗ng 
}
3
,
2
,
1
{

R
va 
}
6
,
5
,
4
{

R
to‗plamlar hosil bo‗ladi. 
Ikkala uchi ham 
R
to‗plamga tegishli bo‗lgan uchta 
)
2
,
1
(
, 
)
3
,
1
(
va 
)
3
,
2
(
yoylardan birinchisi uchun 
2
12
1




c
tengsizlikning bajarilishi 1- 
iteratsiyada tekshirilganligi va 
1

, 
2

qiymatlarning o‗zgarmaganligi 
sababli faqat ikkinchi va uchinchi yoylarga mos 
3
13
1




c
va 
3
23
2




c
munosabatlarni tekshirish kifoya. Bu munosabatlar 
7
10
0


va 
7
5
2


ko‗rinishda bajariladi. Shuning uchun 3- iteratsiyaga o‗tamiz. 
3- iteratsiya.
Boshlangʻich uchi 
}
3
,
2
,
1
{

R
to‗plamga tegishli, oxiri 
esa 
}
6
,
5
,
4
{

R
to‗plamga tegishli bo‗lgan yoylar to‗rtta: 
)
4
,
1
(
, 
)
5
,
2
(
, 
)
4
,
3
(
va 
)
5
,
3
(
. Shu yoylarga mos 
ij
h
ning qiymatlari 
13
14

h
, 
11
25

h
, 
15
34

h
, 
13
35

h
va, shuning uchun, 
11
}
,
,
,
min{
25
35
34
25
14


h
h
h
h
h
bo‗ladi. Demak, bu 
iteratsiyada 
)
5
,
2
(
yoyni ajratamiz va 
11
5


deb olamiz. Endi, algoritmga 
ko‗ra, 
}
5
,
3
,
2
,
1
{

R
va 
}
6
,
4
{

R
to‗plamlarni hosil qilamiz. 
Ikkala uchi ham 
R
to‗plamga tegishli bo‗lgan yoylar oltita: 
)
2
,
1
(
, 
)
3
,
2
(
, 
)
3
,
1
(
, 
)
5
,
2
(
, 
)
5
,
3
(
va 
)
3
,
5
(
. Bu yoylarning har biri uchun 
j
ij
i
c




tengsizlikning bajarilishini tekshirishimiz kerak. Lekin, 1- va 2- 
7
Yozuvning ixchamligi nuqtai nazardan bu yerda va bundan keyin hosil bo‗lgan to‗plamlar uchun 
R
va 
R
belgilar qoldiriladi. 

185 
iteratsiyalarda 
)
2
,
1
(
, 
)
3
,
2
(
va 
)
3
,
1
(
yoylar uchun bu ish bajarilganligi 
sababli tekshirishni tarkibida 
5
belgili uch qatnashgan 
)
5
,
2
(
, 
)
5
,
3
(
va 
)
3
,
5
(
yoylar uchun amalga oshirib, quyidagilarga ega bo‗lamiz: 
)
5
,
2
(
yoy 
uchun 
5
25
2




c
munosabat to‗gʻri (
11
9
2


), 
)
5
,
3
(
yoy uchun 
5
35
3




c
munosabat to‗gʻri (
11
6
7


), lekin 
)
3
,
5
(
yoy uchun 
3
53
5




c
munosabat 
noto‗gʻri (
7
5
)
6
(
11




). Oxirgi munosabatni hisobga olib, algoritmga 
ko‗ra 
7
3


o‗rniga 
5
3


deb olamiz va 
)
3
,
5
(
yoyni ajratilgan deb, ilgari 
ajratilgan 
)
3
,
2
(
yoyni esa ajratilmagan deb hisoblaymiz (3- shaklda 
7
3


yozuvning va 
)
3
,
2
(
yoyning qalin chiziq‘i ustiga ajratilganlikni inkor 
qiluvchi 

belgisi qo‗yilgan). 
4- 
iteratsiya.
}
5
,
3
,
2
1
{
,
R

, 
}
6
,
4
{

R
bo‗lgani 
uchun 
)}
6
,
5
(
),
6
,
3
(
),
4
,
3
(
),
4
,
1
{(
)
,
(

R
R
va 
13
14

h
, 
13
34

h
, 
17
36

h
, 
18
56

h
hamda 
13
}
,
,
,
min{
34
14
56
36
34
14



h
h
h
h
h
h
bo‗ladi. Demak, 
)
4
,
1
(
va 
)
4
,
3
(
yoylarni 
ajratamiz hamda 4 belgili uchga 
13
4


qiymatni mos qo‗yamiz. Natijada 
}
4
,
5
,
3
,
2
1
{
,
R

, 
}
6
{

R
to‗plamlarga ega bo‗lamiz. 
j
ij
i
c




munosabatning to‗gʻriligi 
)
3
,
1
(
, 
)
4
,
1
(
, 
)
3
,
2
(
, 
)
5
,
3
(
, 
)
3
,
5
(
va 
)
4
,
3
(
yoylar uchun tekshirilib ko‗rilganda, uning barcha yoylar uchun 
bajarilishi ma‘lum bo‗ladi. 
5- iteratsiya.
Endi 
)}
6
,
5
(
),
6
,
4
(
),
6
,
3
{(
)
,
(

R
R
bo‗lgani uchun 
17
36

h
, 
14
46

h
, 
18
56

h
va 
14
}
,
,
min{
46
56
46
36


h
h
h
h
bo‗ladi. Bu yerda minimum 
)
6
,
4
(
yoyda erishilgani uchun uni ajratib, orgrafning oxirgi 
6
belgili uchiga 
14
6


qiymatni mos qo‗yamiz. 
Oxirgi qadam.
Berilgan orgrafda 1 belgili uchdan 6 belgili 
uchgacha eng qisqa uzunlikka ega yo‗l(lar)ni topish maqsadida, 
2
9
6
10
7
–6
13
12
8
1
5
1 
2 
3 
5 
6 
4 

186 
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 (
)
6
,
4
(
yoy) ajratilgan bo‗lgani uchun 
)
6
,
4
(
yoy yo‗nalishiga 
qarama-qarshi yo‗nalishda harakat qilib, 
6
belgili uchdan 
4
belgili 
uchga kelamiz. 
4
belgili uchga kiruvchi ikkala (
)
4
,
1
(
va 
)
4
,
3
(
) yoylar 
ham ajratilgan bo‗lgani uchun biz tuzmoqchi bo‗lgan eng qisqa 
uzunlikka ega yo‗l yagona emas. 
Agar harakatni 
)
4
,
1
(
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 
)
6
,
4
,
1
(
1


marshrutni topamiz. 
Agarda harakatni 
)
4
,
3
(
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 (
)
3
,
5
(
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 
)
6
,
4
,
3
,
5
,
2
,
1
(
2


marshrutni aniqlaymiz. 
Shunday qilib, 2- shaklda tasvirlangan grafda eng qisqa uzunlikka 
ega 
1

va 
2

yo‗llar borligini aniqladik. Bu yo‗llarning har biri minimal 
14
6


uzunlikka ega. 

Download 4,61 Mb.