Daraxtlarni Prufer usulida kodlash. Daraxtlarni ularning kodi bo‘yicha yasash

Prüfer kodi o'zboshimchalik bilan 
cheklangan daraxtni
 xaritaga joylashtiradia 
burchaklar 
ketma-ketlikni
 tashkil raqamlar (dan oldin ) mumkin bo'lgan takror-
lashlar bilan. Belgilangan tepalikli daraxt va Prüfer kodi o'rtasidagi munosabatlar 
birma-bir: har bir daraxt o'ziga xos Prüfer kodiga mos keladi va kod ketma-ketligi 
elementlari tepalik raqamlariga beriladi. 
Aksincha, berilgan kodga ko'ra raqamlar yordamida daraxtni aniq qayta qurish 
mumkin cho'qqilar. Kodni 
Xaynts Prufer
 1918yilda 
Cayley formulasini
 isbot-
lashda 
qurgan
 .

---

Bo'lsin tepaliklari raqamlangan daraxt bor ... T daraxtining Prüfer kodini qu-
rish daraxtdan faqat ikkita tepalik qolguncha ketma -ket olib tashlash orqali amalga 
oshiriladi. Bu holda, har safar eng kichik sonli terminal tepalik tanlanadi va u ulan-
gan yagona tepalikning raqami kodga yoziladi. Natijada ketma -ketlik paydo bo'la-
di raqamlardan tashkil topgan , ehtimol takrorlash bilan. 
 
 
 
 
 
Diagrammadagi daraxt uchun 1 -vertex eng kichik sonli sonli tepalikdir, shuning 
uchun u birinchi bo'lib o'chiriladi va 4 Prüfer kodiga yoziladi. 
Keyingi 2 va 3 vertikalar o'chiriladi, shuning uchun kodga ikki marta 4 qo'shiladi. 
Vertex 4 endi terminal va eng kichik raqamga ega, shuning uchun u olib tashlanadi 
va kodga 5 ta qo'shiladi. 
Faqat ikkita tepalik qoldi, shuning uchun kod to'liq yoziladi va jarayon to'xtaydi. 
Natijada - Prüfer kodi (4,4,4,5). 
Daraxtni tiklash
Daraxtni kod bo'yicha tiklash tepalik raqamlari ro'yxatini tayyorlang .
... Keling, birinchi raqamni tanlaymiz bu kodda topilmagan. Chegarani qo'shing, 
shundan keyin biz o'chirib tashlaymiz dan va dan ... 

---

Biz protsedurani kod paydo bo'lguncha takrorlaymiz bo'sh bo'lib qoladi. Bu erda 
ro'yxat to'liq ikkita raqamni o'z ichiga oladi va ... Chegarani qo'shish qoladi va 
daraxt qurilgan
. 
 
 
 
 
 
Xususiyatlar
• 
Agar Tepalik darajasi raqamlangan , keyin aniq Prüfer kodida uchraydi (
) 
bir marta. 
• 
Prüfer kodidan 
Cayley formulasi
 , ya'ni to'liq grafikdagi 
daraxtlar
 soni kelib 
chiqadi. bilan tepaliklari teng ... Prüfer kodi yoyilgan daraxtlar va uzunlik ket-
ma -ketligi o'rtasida bijektsiya berishidan dalolat beradi dan raqamlar. 
• 
Prüfer kodi, agar tepalik darajalari berilgan bo'lsa, Cayley formulasini umum-
lashtirishga imkon beradi. Daraxtlar darajasining ketma -ketligi, bu darajadagi 
daraxtlar soni 
multinominal koeffitsientga
 teng 
• 
Prüfer kodi tasodifiy daraxtlarni qurish uchun ishlatiladi. 
Dekodlash bosqichi, shuningdek, ikki bosqichdan iborat: kanal - standart, stan-
dart-ma'lumot qabul qiluvchi. O'tkazish oxirida ma'lumotlar iste'molchiga o'tka-

---

ziladi. Shunga qaramay, biz iste'molchi ushbu ma'lumotlarni qanday izohlashi 
haqidagi savolni ko'rib chiqmaymiz. 
Avval ta'kidlab o'tilganidek, ma'lumotlarni uzatish tizimi, masalan, telefon xabar-
lari, radio, televidenie dasturlari ma'lumotlarni kompyuterning registrlarida raqam-
lar to'plami sifatida taqdim etadi. Shunga qaramay, kosmosda uzatish vaqtni uza-
tish yoki ma'lumotni saqlashdan farq qilmaydi. Sizda bir muncha vaqt o'tgach talab 
qilinadigan ma'lumotlar bormi, keyin ularni kodlash va ma'lumotlarni saqlash man-
basida saqlash kerak. Agar kerak bo'lsa, ma'lumotlar dekodlanadi. Agar kodlash va 
dekodlash tizimi bir xil bo'lsa, biz ma'lumotlarni uzatish kanali orqali o'zgarishsiz 
uzatamiz. 
Taqdim etilgan nazariya va fizikadagi an'anaviy nazariya o'rtasidagi asosiy farq 
manba va qabul qilgichda shovqin yo'qligi haqidagi taxmindir. Aslida, har qanday 
qo'shimcha qurilmada xatolar yuzaga keladi. Kvant mexanikasida shovqin har qan-
day bosqichda boshlang'ich shart sifatida emas, balki noaniqlik printsipiga ko'ra 
paydo bo'ladi; har qanday holatda ham, axborot nazariyasidagi shovqin tushuncha-
si kvant mexanikasiga teng kelmaydi. 
Aniqlik uchun biz tizimdagi ma'lumotlarning ikkilik shaklini ko'rib chiqamiz. Bo-
shqa shakllar ham xuddi shunday ishlov beriladi; soddaligi uchun biz ularni ko'rib 
chiqmaymiz. 
Oddiy belgilar qisqa va nodir belgilar uzun bo'lgan klassik Morz kodi va nuqta 
kodidagi kabi o'zgaruvchan uzunlikdagi kodlangan belgilarga ega tizimlarni ko'rib 
chiqamiz. Ushbu yondashuv sizga kodning yuqori samaradorligiga erishishga im-
kon beradi, ammo shuni ta'kidlash kerakki, Mors kodi ikkilik emas, uchlik, chunki 
u nuqta va chiziqlar orasidagi bo'shliq belgisini o'z ichiga oladi. Agar koddagi bar-
cha belgilar bir xil uzunlikda bo'lsa, unda bunday kod blok kodi deb ataladi. 
Kodning birinchi aniq zaruriy xususiyati - bu shovqin bo'lmagan holda xabarni 
aniq dekodlash qobiliyati, hech bo'lmaganda bu kerakli xususiyat bo'lib ko'rinadi, 
ammo ba'zi hollarda bu talabni e'tiborsiz qoldirish mumkin. Uzatish kanalidagi 
ma'lumotlar qabul qiluvchiga birlar va nollar oqimiga o'xshaydi. 
Ikki qo'shni belgini ikki baravar kengayish, uchta qo'shni belgini uch baravar 
kengayish deb ataymiz va umuman olganda, biz N belgilarini yuborsak, qabul qilu-
vchi N belgilarining asosiy kodiga qo'shimchalarni ko'radi. Qabul qilgich N qiy-
matini bilmagan holda oqimni tarjima qilingan bloklarga ajratishi kerak. Yoki, bo-
shqacha qilib aytganda, qabul qiluvchining asl xabarni tiklashi uchun oqimni o'ziga 
xos tarzda buzishi kerak. 
Kam sonli belgilar bilan alfavitni ko'rib chiqing, odatda juda katta alifbolar. Til-
larning alifbolari 16 dan 36 tagacha belgidan boshlanadi, jumladan katta va kichik 
harflar, raqam belgilari, tinish belgilari. Masalan, ASCII jadvalida 128 \u003d 2 ^ 
7 ta belgi. 
S1, s2, s3, s4 4 ta belgidan iborat maxsus kodni ko'rib chiqing