Respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot

---

O‘ZBEKISTON
 RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA 
KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI 
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT 
TEXNOLOGIYALARI UNIVERSITETI 
 
 
 
 
 
Kompyuter injiniringi 
FAKULTETI 
 
 
Algoritmlash va matematik modellashtirish kafedrasi 
“Diskret
 
tuzilmalar”
 fani 
 
 
 
 
 
MUSTAQIL ISH № 1 
 
Mavzu: 
Daraxtlarni Prufer usulida kodlash. Daraxtlarni ularning kodi bo‘yicha 
yasash.
 
 
 
Topshirdi: 
030-20 guruh talabasi 
Tojimov Alisher 
 
Toshkent 
–
 2021-y 

---

Reja 
1.Kirish 
2.Daraxt va unga ekvivalent tushunchalar
 
3.Daraxtlarni Prufer usulida kodlash 
4.
Daraxtlarni ularning kodi bo’yicha
 yasash 
5.Foydalanilgan adabiyotlar 

---

1948 yilda, Klod Shannon nashr etilgan "Muloqotning matematik nazariyasi", 
Iyul va Oktyabr sonlarida ikki qismdan iborat maqola 
Bell tizimi texnik jurnali
. 
Ushbu ish kodlashni qanday qilib yaxshiroq kodlash masalasiga qaratilgan ma 
`lumot jo'natuvchi uzatishni xohlaydi. Ushbu fundamental ishda u tomonidan 
ishlab chiqilgan ehtimollar nazariyasidagi vositalardan foydalanilgan Norbert 
Viner, ular o'sha paytda aloqa nazariyasiga tatbiq etilish bosqichlarida 
bo'lgan. Shannon ishlab chiqdi axborot entropiyasi maydonini ixtiro qilgan 
holda xabardagi noaniqlik o'lchovi sifatida axborot nazariyasi. 
The ikkilik Golay kodi 1949 yilda ishlab chiqilgan. Bu har 24 bitli so'zda uchta 
xatolikni tuzatishga va to'rtinchisini aniqlashga qodir bo'lgan xatolarni 
tuzatuvchi kod. 
Richard Xamming g'olib bo'ldi Turing mukofoti 1968 yilda ishlaganligi 
uchun Bell laboratoriyalari raqamli usullarda, avtomatik kodlash tizimlarida 
va xatolarni aniqlash va xatolarni tuzatish kodlarida. U sifatida tanilgan 
tushunchalarni ixtiro qildi Hamming kodlari, Hamming windows, Hamming 
raqamlariva Hamming masofasi. 
1972 yilda, Nosir Ahmed taklif qildi diskret kosinus o'zgarishi (DCT), u T. 
Natarajan bilan ishlab chiqqan va K. R. Rao 1973 yilda.
[2]
 DCT eng keng 
qo'llaniladigan hisoblanadi yo'qotishlarni siqish algoritmi, kabi multimedia 
formatlari uchun asos JPEG, MPEG va MP3. 
Daraxt tushunchasiga boshqacha ham ta'rif berish mumkin. Umuman 
olganda, 
G(m,n)-gvaf 
uchun 
daraxtlar haqidagi asosiy teorema, 
deb ataluvchi 
quyidagi teorema o'rinlidir.
1-teorema. Uchlari soni m va qirralari soni n bo 'Igan G graf uchun quyidagi 
tasdiqlar ekvivalentdir:
•
G daraxtdir;
•
G asiklikdir va n=m
—
l;
•
G bog'lamlidir va n=m
—
\;
Induksion o'tish: 
G 
daraxt uchun 
k>2 
va
m=k 
bo'lganda, 2) tasdiq o'rinli bo'lsin 
deb faraz qilamiz. 
Endi uchlari soni 
m=k+l 
va qirralari soni 
n 
bo'lgan daraxtni 
qaray-miz. Bu daraxtning ixtiyoriy qirrasini (vp v2) bilan belgilab, undan bu 

---

qirrani olib tashlasak, Vj uchdan v2 uchgacha marshruti (aniqrog'i, zanjiri) mavjud 
bo'lma-gan 
grafni hosil qilamiz
, chunki agar hosil bo'lgan grafda bunday zanjir bor 
bo'lsa edi, u holda 
G 
daraxtda sikl topilar edi. Bunday bo'lishi esa mumkin emas. 
Hosil bo'lgan graf ikkita 
Gl
va
G2
bog'lamli komponentalardan iborat bo'lib, bu 
komponentalarning har biri daraxtdir. Yana shuni ham e'tiborga olish kerakki 
, 
Gl
va
G2 
daraxtlarning 
har biridagi uchlar soni 
к dan 
oshmaydi. 
Matematik induksiya usuliga ko'ra, bu daraxtlarning har birida qirralar soni uning 
uchlari sonidan bitta kam bo'lishini ta'kidlaymiz, ya'ni 
Gx
graf 
(m, 
«)-graf bo'lsa, 
quyidagi tengliklar o'rinlidir: 
n=nx+n2+\, k+l=ml+m2va. n=m — \ 
(/=1,2). Bu tengliklardan 
n=nl+n2+l=m]— l+m2—
1+1= 
(mx+m2)—l= (k+l)—l
Endi daraxtlar haqidagi asosiy teoremaning 2) tasdig'idan uning 3) tasdig'i kelib 
chiqishini isbotlaymiz. 
G 
graf asiklik, ya'ni u siklga ega bo'lmagan graf va
n=m— 
1 
bo'lsin. 
G 
grafning bog'lamli bo'lishini isbotlash kerak. 
Agar 
G 
graf bog'lamli bo'lmasa, u holda uni har bir bog'lamli komponentasi sik-
lsiz graf 
G. 
(ya'ni daraxt) bo'lgan qandaydir
к.kta (k>l) 
graflar dizyunktiv birlash-
masi sifatida ^=U^ 
tenglik
/=] 
bilan ifodalash mumkin. Har bir 
i=l,k
uchun 
G.t
graf 
daraxt bo'lgani uchun, yuqorida isbotlangan tasdiqqa ko'ra, agar unda 
mj 
ta uch va 
«.ta qirra bo'lsa, u holda 
G. 
asiklikdir va 
n=m—
1 tenglik
Agar qandaydir ikki uch bittadan ko'p, masalan, ikkita turli oddiy zanjir vosita-
sida tutashtirilishi imkoniyati bo'lsa, u holda bu uchlarning biridan zanjirlarning 
biron-tasi bo'ylab 
harakatlanib ikkinchi uchga
, keyin bu uchdan ikkinchi zanjir 
bo'ylab harakatlanib dastlabki uchga qaytish imkoniyati bor bo'lar edi. Ya'ni 
qaralayotgan graf da sikl topilar edi