112
33-rasm. Daraxtlarda insidentlik matritsalari
8.3. Pryufer Kodi
Pryufer kodi [1, n] kesmadagi n-2 butun sonlar ketma-ketligi
yordamida n uchlari bilan belgilangan daraxtlarni
birma-bir kodlash
usuli. Ya‘ni, Pryufer kodi - bu toʻliq graf va raqamlar ketma-ketligining
barcha daraxtlari orasidagi biyeksiyasidir.
Daraxtlarni kodlashning ushbu usuli nemis matematiki Xaynts
Pryufer tomonidan 1918-yilda taklif qilingan.
ta uchlari bilan berilgan
daraxt uchun Pryufer kodini qurish algoritmini koʻrib chiqaylik.
Kirishda qirralarning roʻyxati berilgan.
Eng kichik raqamga ega
boʻlgan daraxtning bargi tanlanadi, keyin u daraxtdan olib tashlanadi va
bu barg bilan bogʻlangan uchlarning soni Pryufer kodiga qoʻshiladi.
Ushbu protsedura
marta takrorlanadi. Oxir-oqibat, daraxtda faqat
2 ta uch qoladi va algoritm shu yerda tugaydi. Qolgan ikkita uchning
raqamlari kodga yozilmaydi.
Shunday qilib, ma‘lum bir
daraxt uchun Pryufer kodi
ta
raqamlar ketma-ketligi boʻlib, bu yerda har bir raqam eng kichik barg
bilan bogʻlangan uchning soni - bu segmentdagi raqam [1, n ].
Pryufer kodini aniqlash.
a)
b) c) d) e)
34-rasm. Daraxtlar uchun Pryufer kodini aniqlash bosqichlari
113
Kodni olish algoritmi quyidagicha. Daraxt tugunlari 1 dan n gacha
boʻlgan raqamlar bilan belgilangan (raqamlangan) boʻlsin.
Biz eng
kichik sonli 1-darajali uchni topamiz va kodga unga qoʻshni boʻlgan
uchning sonini kiritamiz, shundan soʻng topilgan uchni (qirrasi
bilan
birga) oʻchirib tashlaymiz. Olingan graf osti bilan biz xuddi shu amalni
bajaramiz, uni faqat bitta qirra qolguncha takrorlaymiz. Kodni yaratish
jarayoni 34-rasmda keltirilgan. Keyingi bosqichda oʻchirilgan uchning
soni ramkaga kiritilgan. Berilgan grafda (34-rasm, a)
birinchi darajali
uchlar orasida minimal son 2-uchda joylashgan. U 1-uchga qoʻshni.
Shuning uchun Pryufer kodining birinchi raqami 1. 2-uchni olib tashlash
natijasida biz b-rasmda koʻrsatilgan grafni olamiz. Ushbu grafda darajasi
birga teng boʻlgan uchlar orasidagi minimal son 3 ga teng,
shuning
uchun kodning ikkinchi raqami 4. Shaklda koʻrsatilgan graflarga mos
keladigan yana uchta takrorlashni bajargandan soʻng, c, d, e-rasmlardagi
bitta qirradan iborat daraxtni olamiz {7; 6}. Jarayon tugallandi.
Qabul qilingan qadamlarning natijalari jadvalda keltirilgan.
Oxirgi
qatorida kerakli kod mavjud - 14166.
Qadam
1
2
3
4
5
34-rasm
a
b
c
d
e
Minimal
raqam
2
3
4
1
5
Oʻchirilgan
qirra
{1;2} {4;3} {1;4} {6;1}
{6;5}
Pryufer kodi
1
4
1
6
6
