Mavzu: daraxtlarni prufer usulida kodlash

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNALOGIYALARI UNIVERSITETINING 210-20 GURUH TALABASI SAFAROV SAIDBEKNING DISKRET TUZULMALARI FANIDAN TAYYORLAGAN

MUSTAQIL ISHI
MAVZU:DARAXTLARNI PRUFER USULIDA KODLASH

TAYYORLADI:SAFAROV S

TEKSHIRDI:TURG’UNOV A
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