Daraxtlar grafning xususiy holati sifatida


Binar (ikkilik) daraxtlar


Download 0.92 Mb.
bet3/9
Sana04.05.2023
Hajmi0.92 Mb.
#1425531
1   2   3   4   5   6   7   8   9
Bog'liq
DARAXTLAR GRAFNING XUSUSIY HOLATI SIFATIDA

7.1. Binar (ikkilik) daraxtlar



Ikkilik daraxt - bu har bir tugunda koʻpi bilan ikkita avlod (bola) boʻlgan ma’lumotlarning iyerarxik tuzilishi. Odatda, birinchisi ajdod tuguni, avlodlar esa chap va oʻng merosxoʻrlar deb nomlanadi.

30-rasm. Binar daraxt


31-rasm. Kalitlari lotin alifbosi boʻlgan ikkilik qidiruv daraxti, alfavit boʻyicha tartiblangan.

7.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:




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.


a)

b)





Download 0.92 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling