Diskret tuzulmalari fanidan tayyorlagan

---

 
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNALOGIYALARI UNIVERSITETI FARG’ONA FILIALINING
721.21 GURUH TALABASI JAHONGIROV FIRDAVSXONNING
DISKRET TUZULMALARI FANIDAN TAYYORLAGAN 
 
 
 
 
MUSTAQIL ISHI 
MAVZU:DARAXTLARNI PRUFER USULIDA KODLASH 

---

Reja Daraxt va unga ekvivalent tushunchalar Daraxtlarni Prufer usulida 
kodlash Daraxtlarni ularning kodi bo’yicha 
Reja 

Daraxt va unga ekvivalent tushunchalar 

Daraxtlarni Prufer usulida kodlash 

Daraxtlarni ularning kodi bo’yicha 

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 vam=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 GlvaG2bog'lamli komponentalardan iborat bo'lib, bu 
komponentalarning har biri daraxtdir. Yana shuni ham e'tiborga olish kerakki 
, GlvaG2 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 Gxgraf (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 van=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,kuchun G.tgraf 
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