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

110 
 
30-rasm. Binar daraxt 
 
 
31-rasm. Kalitlari lotin alifbosi boʻlgan ikkilik qidiruv daraxti, 
alfavit boʻyicha tartiblangan.
 
8.2. Daraxtlarni mashinada tasvirlash usullari 
Matritsali koʻrinish. 
Daraxt, boshqa har qanday graf singari, 
matritsalar yordamida tasvirlanishi mumkin. Misol tariqasida quyida 32-
rasmda
koʻrsatilgan tartiblangan daraxt uchun A – qoʻshnilik va B – 
insidentlik matritsalarini keltirilgan: 
 
 
 
 
 
 
 
 

111 
 
 
 
 
 
 
 
32-rasm. Daraxtlarda qoʻshnilik (A) va insidentlik (B) matritsalari 
 
Daraxtlar uchun bunday matritsalarning oʻziga xos xususiyatlarini 
ta‘kidlaylik. 
ga teng boʻlgan daraxtning qirralari sonining nisbati 
bogʻlangan graf uchun minimal, shuning uchun daraxtning qoʻshnilik 
matritsasi juda kam (ularning nisbati va undagi nollar 
yoʻnaltirilgan daraxt uchun va 
yoʻnaltirilmagan uchun). 
Daraxtning insidentlik matritsasi 
oʻlchamiga ega, ya‘ni 
kvadratga yaqin, va aslida, agar biz uning ortiqcha ekanligini hisobga 
olsak. Darhaqiqat, har qanday qatorni olib tashlab, biz avvalgidek grafni 
toʻliq tavsiflaydigan kvadrat matritsani olamiz. 
Quyida keltirilgan insident matritsasining yana bir xususiyati 
quyidagicha. Satr va ustunlarni qayta tartiblash orqali har qanday 
daraxtning insidentlik matritsasi 
ustun birliklaridan biri 
qatorda, 
ikkinchisi pastki qatorlardan birida boʻlganda pastki trapetsiya 
matritsaga tushirilishi mumkin.

Download 4,61 Mb.