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

1- t e o r e m a . Uchlari soni m va qirralari soni n bo‘lgan G graf uchun quyidagi tasdiqlar ekvivalentdir:
G daraxtdir;
G asiklikdir va n m 1;
G bog‘lamlidir va n m 1;
G bog‘lamlidir va undan istalgan qirrani olib tashlash amalini qo‘llash natijasida bog‘lamli bo‘lmagan graf hosil bo‘ladi, ya’ni G ning har bir qirrasi ko‘prikdir;
G grafninng o‘zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta oddiy zanjir bilan tutahtiriladi;
G asiklik bo‘lib, uning qo‘shni bo‘lmagan ikkita uchini qirra bilan tutashtirish amalini qo‘llash natijasida faqat bitta siklga ega bo‘lgan graf hosil bo‘ladi.
na t i j a . Bittadan ko‘p uchga ega bo‘lgan istalgan daraxtda hech bo‘lmasa ikkita darajasi birga teng uchlar mavjud.
n a t i j a . m ta uch va k ta bog‘lamli komponentali o‘rmondagi qirralar
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
mm2 ga teng.
Minimal uzunlikka ega yo‘l haqidagi masalani hal etish usullari orasida Deykstra2 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.
2 Deykstra Edsger Vayb (Dijkstra Edsger Wybe, 1930-2002) – Gollandiya matematigi.
Dastlabki qadam. Manbaga (1 belgili uchga)
1 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
hij i cij
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 cij j tengsizlikning bajarilishini tekshiramiz. Tekshirilayotgan tengsizlik
*
o‘rinli bo‘lmagan (ja’ni j
bo‘lgan) barcha
j* belgili uchlarning har biriga
*
*
mos qo‘yilgan eski j
qiymat o‘rniga yangi i cij
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.
2- m i s o l . 2- shaklda tasvirlangan orgrafda oltita uch (V {1, 2, 3, 4, 5, 6}) va o‘n bitta yoy bo‘lib, har bir yoy uzunligi uning yoniga yozilgan. Ko‘rinib turibdiki,
2- shakl
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)
1 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 hij ning qiymatlarini topamiz:
(1, 2)
(1, 3)
(1, 4)
yoy uchun yoy uchun yoy uchun
h12 1 c12 0 2 2 ; h13 1 c13 0 10 10 ; h14 1 c14 0 13 13.
Bu h12 ,
h13 va
h14
miqdorlar orasida eng kichigi
h12
bo‘lgani uchun
(1, 2)
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 3
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
1 c12 2
tengsizlikning bajarilishini tekshirish kifoya. Bu tengsizlik
3 Yozuvning ixchamligi nuqtai nazardan bu yerda va bundan keyin hosil bo‘lgan to‘plamlar uchun R va R belgilar
qoldiriladi.
0 2 2 ko‘rinishdagi to‘g‘ri munosabatdan iborat bo‘lgani uchun 2- iteratsiyaga o‘tamiz.
iteratsiya.
( R,R ) {(1 , 3) ,(1 , 4) ,(2 , 3) ,(2 , 5)}
bo‘lgani sababli
h13 10 ,
h14 13 ,
h23 7 va
h25 11
qiymatlarni va
min{ h13, h14 , h23, h25} h23 7
ekanligini aniqlaymiz.
Bu yerda eng kichik qiymat
(2, 3)
yoyga mos keladi. Shuning uchun,
(2, 3)
yoyni
ajratamiz va
3 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
1 c12 2
tengsizlikning bajarilishi 1- iteratsiyada
tekshirilganligi va
1 , 2
qiymatlarning o‘zgarmaganligi sababli faqat ikkinchi va
uchinchi yoylarga mos
1 c13 3
va 2 c23 3
munosabatlarni tekshirish kifoya.
Bu munosabatlar
0 10 7 va
2 5 7
ko‘rinishda bajariladi. Shuning uchun 3-
iteratsiyaga o‘tamiz.
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
hij ning qiymatlari
h14 13 ,
h25 11 ,
h34 15 ,
h35 13
va, shuning
uchun,
min{ h14 , h25, h34, h35} h25 11
bo‘ladi. Demak, bu iteratsiyada
(2, 5)
yoyni
ajratamiz va
5 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 cij 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
2 c25 5
munosabat to‘g‘ri ( 2 9 11 ),
(3, 5)
yoy
uchun
3 c35 5
munosabat to‘g‘ri ( 7 6 11), lekin
(5, 3)
yoy uchun
5 c53 3
munosabat noto‘g‘ri (11 (6) 5 7 ). Oxirgi munosabatni hisobga olib, algoritmga
ko‘ra
3 7
o‘rniga 3 5 deb olamiz va
(5, 3)
yoyni ajratilgan deb, ilgari ajratilgan
(2, 3)
yoyni esa ajratilmagan deb hisoblaymiz (3- shaklda
3 7
yozuvning va
(2, 3)
yoyning qalin chiziq’i ustiga ajratilganlikni inkor qiluvchi belgisi qo‘yilgan).
|