|
-Misol.
Tugunlarning tipi
|
| bet | 3/4 | | Sana | 11.01.2024 | | Hajmi | 2,46 Mb. | | #134474 |
Bog'liq DISKRET15.4-Misol.
Tugunlarning tipi. Aytaylik chekli G – daraxt berilgan bo‘lsin. Bu daraxtning chekka tugunlarini 1 tipli tugunlar deb ataymiz. Ta’kidlaymizki, agar daraxtning tugunlari soni 2 tadan ortiq bo‘lsa, u holda ular orasida chekka bo‘lmagan tugunlar mavjud bo‘ladi. Haqiqatdan ham, aytaylik a1 va a2 – G daraxtning chekka tugunlari bo‘lsin. U holda ular zanjir bilan bog‘langan bo‘lishi kerak. Agar bu zanjir faqat bitta qirradan iborat bo‘lsa, u holda a1 va a2 boshqa birorta ham tugun bilan bog‘lanmagan, bu esa daraxtning bog‘langanligiga ziddir. Agar bu zanjir 2 ta yoki ko‘proq širradan iborat bo‘lsa, u holda bu zanjir lokal darajasi 2 dan katta yoki teng bo‘lgan tugunlardan o‘tadi, ya’ni bu tugunlar chekka tugunlar emas .
G daraxtdan hamma 1 tipli tugunlarni va ularga qo‘shma bo‘lgan qirralarni tashlab yuboramiz. U holda sikllarsiz bog‘langan G| daraxt qoladi.
Haqiqatdan, ixtiyoriy a|, a|| G|| tugunlarni birlashtiruvchi zanjir L(a|,a||) G daraxtning chekka tugunlaridan o‘tmaydi, balkim to‘lig‘icha G| daraxtda yotadi. G| daraxt ham o‘z navbatida chekka tugunlarga ega bo‘ladi. Bu tugunlarni G daraxtdagi 2 tipli tugunlar deb ataymiz. Xuddi shu usul bilan 3, 4 va h.k tipli tugunlarni hosil qilamiz.
15.5-Misol.
a) G:
b)
v) g)
G| G|| G|||
Demak G daraxtning markazi 4 –tipli a1, a2 tugunlardan iborat
Ushbu daraxtning markazi 4-tipli a1, a2 tugunlardan iborat.
15.14-Teorema. G daraxtning markazi deb, eng katta K - tipga ega bo‘lgan tugunlarga aytiladi.
a| chetki bo‘lmasa, u holda undan yana bitta qirra chiqadi. Ushbu qirraning a|| tugunidan yana bitta qirra chiqadi va hokazo.
|
| |
