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.
