15-mavzu. O’rmon. Daraxtlarning xossalari. Ostov daraxti

soni
(m  k ) ga tengdir.


2- t e o r e m a . Istalgan daraxtning markazi uning bitta uchidan yoki ikkita

qo‘shni uchlaridan iborat bo‘ladi.
^{3- t e o r e m a (Keli). Uchlari soni} m ^{bo‘lgan belgilangan daraxtlar soni}
m^m2 ga teng.

Minimal uzunlikka ega yo‘l haqidagi masalani hal etish usullari orasida Deykstra² tomonidan taklif etilgan algoritm ko‘p qo‘llaniladi. Quyida grafning 1 ^{belgili uchidan chiqib (bu uchni manba deb qabul qilamiz) grafdagi ixtiyoriy} k uchgacha (bu uchni oxirgi uch deb hisoblaymiz) eng qisqa uzunlikka ega yo‘lni topish imkonini beruvchi Deykstra algoritmi keltirilgan.

² Deykstra Edsger Vayb (Dijkstra Edsger Wybe, 1930-2002) – Gollandiya matematigi.

Dastlabki qadam. Manbaga (1 belgili uchga)
₁  0
qiymatni mos qo‘yib, bu

uchni dastlab olamiz.
R  
deb qabul qilingan R to‘plamga kiritamiz:
R  {1} ^.


R  V \ R
deb

Umumiy qadam. Boshlang‘ich uchi R to‘plamga, oxirgi uchi esa R

to‘plamga tegishli bo‘lgan barcha yoylar to‘plami

(R, R )

bo‘lsin. Har bir

(i, j) (R, R )
yoy uchun
h_ij  _i  c_ij
miqdorni aniqlaymiz, bu yerda _i
^deb i  R
uchga

mos qo‘yilgan qiymat (grafning 1 belgili uchidan chiqib i belgili uchigacha eng qisqa yo‘l uzunligi) belgilangan.

 _j 
min
(i, j )( R,R )
^hij
qiymatni aniqlaymiz.

(R, R )

to‘plamning oxirgi tenglikda

minimum qiymat beruvchi barcha elementlarini, ya’ni
(i, j)
yoylarni ajratamiz.

Ajratilgan yoylarning har biridagi
j  R
belgili uchga  _j
qiymatni mos qo‘yamiz.  _j

qiymat mos qo‘yilgan barcha j uchlarni R to‘plamdan chiqarib ^R to‘plamga kiritamiz.

Ikkala uchi ham R to‘plamga tegishli bo‘lgan barcha

(i, j)

yoylar uchun

_i  c_ij   _j tengsizlikning bajarilishini tekshiramiz. Tekshirilayotgan tengsizlik

*
o‘rinli bo‘lmagan (ja’ni  _j

• 
  _i  c_ij
  

bo‘lgan) barcha
j_* belgili uchlarning har biriga

*

*
mos qo‘yilgan eski  _j
qiymat o‘rniga yangi _i  c_ij
qiymatni mos qo‘yamiz va
(i, j_*)

*

j

*
yoyni ajratamiz. Bunda eski 
ajratilmagan deb hisoblaymiz.
qiymat aniqlangan paytda ajratilgan yoyni

^{Uchlarga qiymat mos qo‘yish jarayonini oxirgi (} k ^{belgili) uchga qiymat mos} qo‘yilguncha davom ettiramiz. Grafning 1 belgili uchidan (manbadan) chiqib uning

^ixtiyoriy k ^{uchigacha (oxirgi uchigacha) eng qisqa yo‘l uzunligi }_k
bo‘ladi.

Oxirgi qadam. Grafning oxirgi uchidan boshlab ajratilgan yoylar yo‘nalishiga qarama-qarshi yo‘nalishda uning 1 belgili uchiga kelguncha ^{harakatlanib, natijada grafdagi 1 belgili uchdan ixtiyoriy} k ^{uchgacha eng qisqa} uzunlikka ega yo‘l(lar)ni topamiz.

berilgan grafda manfiy uzunlikka ega
(5,3) yoy ham bor. Isbotlash mumkinki, bu

grafda umumiy uzunligi manfiy bo‘lgan sikl mavjud emas.
Yuqorida bayon qilingan Deykstra algoritmini berilgan grafga qo‘llab, eng qisqa uzunlikka ega yo‘lni topish bilan shug‘ullanamiz.

Dastlabki qadam. Manbaga (1 belgili uchga)
₁  0
qiymatni mos qo‘yamiz

va R  {1} to‘plamga ega bo‘lamiz. Shuning uchun, ^{R  V \ R {2, 3, 4, 5, 6}} bo‘ladi.

Umumiy qadam. 1- iteratsiya.

R  {1} va
R {2,3,4,5,6}
bo‘lgani uchun

boshlang‘ich uchi R to‘plamga tegishli, oxirgi uchi esa R to‘plam elementi bo‘lgan

barcha yoylar to‘plami
(R, R )  {(1, 2), (1, 3), (1, 4)} ga ega bo‘lamiz.

(R, R )

to‘plamga

tegishli bo‘lgan har bir yoy uchun h_ij ning qiymatlarini topamiz:

(1, 2)


(1, 3)


(1, 4)
yoy uchun yoy uchun yoy uchun
h₁₂  ₁  c₁₂  0  2  2 ; ^h₁₃ ^{ }₁ ^{ c}₁₃ ^{ 0 10  10} ; h₁₄  ₁  c₁₄  0 13 13.

Bu h₁₂ ,
^h₁₃ va
^h14
miqdorlar orasida eng kichigi
^h12
bo‘lgani uchun
(1, 2)
yoyni

ajratamiz (3- shaklda bu yoy qalin chiziq bilan belgilangan) va ² belgili uchga
₂  2 qiymatni mos qo‘yamiz. Algoritmga ko‘ra ² uchni R to‘plamdan chiqarib,

^R to‘plamga kiritamiz. Natijada ³
bo‘lamiz.
R  {1, 2} va
R {3, 4, 5, 6}
to‘plamlarga ega

Ikkala uchi ham ^R to‘plamga tegishli bo‘lgan bitta
(1, 2)
yoy bo‘lgani uchun

faqat bitta
₁  c₁₂  ₂
tengsizlikning bajarilishini tekshirish kifoya. Bu tengsizlik

³ Yozuvning ixchamligi nuqtai nazardan bu yerda va bundan keyin hosil bo‘lgan to‘plamlar uchun ^R va R belgilar
qoldiriladi.

2. iteratsiya.

(R,R )  {(1, 3),(1, 4),(2, 3),(2, 5)}
bo‘lgani sababli
h₁₃  10 ,
h₁₄  13 ,

h₂₃  7 va
h₂₅  11
qiymatlarni va
min{ h₁₃, h₁₄ , h₂₃, h₂₅}  h₂₃  7
ekanligini aniqlaymiz.

Bu yerda eng kichik qiymat
(2, 3)
yoyga mos keladi. Shuning uchun,
(2, 3)
yoyni

ajratamiz va
₃  7
^qiymatni 3 ^{belgili uchga mos qo‘yamiz.} 3 ^{belgili uchni R}

to‘plamdan chiqarib, R to‘plamga kiritgandan so‘ng to‘plamlar hosil bo‘ladi.
R  {1, 2, 3} va
R  {4, 5, 6}

Ikkala uchi ham R to‘plamga tegishli bo‘lgan uchta
(1, 2) ,


(1, 3)
va (2, 3)

yoylardan birinchisi uchun
₁  c₁₂  ₂
tengsizlikning bajarilishi 1- iteratsiyada

tekshirilganligi va
₁ , ₂
qiymatlarning o‘zgarmaganligi sababli faqat ikkinchi va

uchinchi yoylarga mos
₁  c₁₃  ₃
va ₂  c₂₃  ₃
munosabatlarni tekshirish kifoya.

Bu munosabatlar
0 10  7 ^va
2  5  7
ko‘rinishda bajariladi. Shuning uchun 3-

iteratsiyaga o‘tamiz.

2. 
   iteratsiya. Boshlang‘ich uchi
   

R  {1, 2, 3}
to‘plamga tegishli, oxiri esa

R  {4, 5, 6}
to‘plamga tegishli bo‘lgan yoylar to‘rtta:
^{(1, 4)} ,
^{(2, 5)} ,
(3, 4)
va ^{(3, 5)} .

Shu yoylarga mos
h_ij ning qiymatlari
h₁₄  13 ,
h₂₅  11 ,
^h₃₄ ^{ 15} ,
h₃₅  13
va, shuning

uchun,
min{ h₁₄ , h₂₅, h₃₄, h₃₅}  h₂₅  11
bo‘ladi. Demak, bu iteratsiyada
(2, 5)
yoyni

ajratamiz va
₅  11 deb olamiz. Endi, algoritmga ko‘ra,
R  {1, 2, 3, 5} va
R {4, 6}

to‘plamlarni hosil qilamiz.
Ikkala uchi ham ^R to‘plamga tegishli bo‘lgan yoylar oltita:
(1, 2) ,
(2, 3) , (1, 3)

, (2, 5) ,
(3, 5)
va (5, 3) . Bu yoylarning har biri uchun
_i  c_ij   _j
tengsizlikning

bajarilishini tekshirishimiz kerak. Lekin, 1- va 2- iteratsiyalarda
(1, 2) ,
(2, 3)
va (1, 3)

yoylar uchun bu ish bajarilganligi sababli tekshirishni tarkibida 5 belgili uch

qatnashgan
(2, 5) ,
(3, 5)
va (5, 3)
yoylar uchun amalga oshirib, quyidagilarga ega

bo‘lamiz:
(2, 5)
yoy uchun
 ₂  c₂₅  ₅
munosabat to‘g‘ri ( 2  9 11 ),
(3, 5)
yoy

uchun
₃  c₃₅  ₅
^{munosabat to‘g‘ri (} 7  6 11^{), lekin}
(5, 3)
yoy uchun
₅  c₅₃  ₃

munosabat noto‘g‘ri (11 (6)  5  7 ). Oxirgi munosabatni hisobga olib, algoritmga

ko‘ra
₃  7
o‘rniga ₃  5 deb olamiz va
(5, 3)
yoyni ajratilgan deb, ilgari ajratilgan

(2, 3)
yoyni esa ajratilmagan deb hisoblaymiz (3- shaklda
₃  7
yozuvning va
(2, 3)

yoyning qalin chiziq’i ustiga ajratilganlikni inkor qiluvchi ^ belgisi qo‘yilgan).

2. 
   
   Download 160,96 Kb.