Kompyuter injinering fakulteti 2-bosqich ki-13-21(S) guruh talabasining diskret tuzilmalari fanidan tayyorlagan

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI QARSHI FILIALI

KOMPYUTER INJINERING FAKULTETI
2-BOSQICH KI-13-21(S) GURUH TALABASINING
DISKRET TUZILMALARI FANIDAN TAYYORLAGAN

8-Mustaqil ish

Bajardi:

Qabul qildi:

Baho:

Ashurov.A.

Turdiyev. U

_______________

QARSHI – 2022

Reja
Daraxt va unga ekvivalent tushunchalar
Daraxtlarni Prufer usulida kodlash
Daraxtlarni ularning kodi bo’yicha

Graf, uch, qirra, daraxt, о'rmon, asiklik graf, marshrut, sikl, zanjir, oddiy zanjir, ко'prik, grafning sinch daraxti, grafning sinch o'rmoni, grafning siklomatik soni. Daraxt va unga ekvivalent tushunchalar. Siklga ega bo'lmagan oriyentirlanmagan bog'lamli graf daraxt, deb ataladi1. Ta'rifga ko'ra, daraxt sirtmoqlar va karrali qirralarga ega emas. Siklga ega bo'lmagan oriyentirlanmagan graf о'rmon (asiklik graf), deb ataladi. 1-misol.1-shaklda bog'lamli komponentali soni beshga teng bo'lgan graf tasvirlangan bo'lib, u o'rmondir. Bu grafdagi bog'lamli komponentalarning har bin daraxtdir. ■ 2-misol 2-shaklda to'rtta uchga ega bir-biriga izomorf bo'lmagan barcha (ular bor-yog'i ikkita) daraxtlarning geometrik ifodalanishi tasvirlangan.Beshta uchga ega birbiriga izomorf bo'lmagan barcha daraxtlar uchta, oltita uchga ega bunday barcha daraxtlar esa oltita ekanligini ko'rsatish qiyin emas. 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 qaraymiz. Bu daraxtning ixtiyoriy qirrasini (vp v2) bilan belgilab, undan bu qirrani olib tashlasak, Vj uchdan v2 uchgacha marshruti (aniqrog'i, zanjiri) mavjud bo'lmagan 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, GlvaG2daraxtlarning 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 siklsiz graf G. (ya'ni daraxt) bo'lgan qandaydir
K ta (k>l) graflar dizyunktiv birlashmasi 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.
Har bir fan o’z axboroti, o’zaro bog’lanmagan ma’lumotlari majmuyiga ega bo’lib, ularni qayta ishlashni o’z usullari va qoidalari mavjud. Mazkur usul va qoidalar shu fanning maqsad va vazifalaridan kelib chiqadi, hamda axborot va ma’lumotlar shu o’rganuvchi asosiy abyektga bog’liq bo’ladi. Masalan, biologiyada o’rganiladigan obyekt-tabiiy trik sistemalar(odamlar, hayvonlar, o’simliklar va ...) bo’lib, biologiya fanida qo’llaniladiganaxborotlar ana shu obyektlar yordamida, ularning bevosita ishtirokida to’planadi, qayta ishlanadi, saqlanadi va uzatiladi.
Informatika fani uchun o’rganiladigan obyekt bo’lib, axborot hisoblanadi. Shuning uchun ham bu fanda axborotlarni yig’ish, hosil qilish, saqlash, qayta ishlash va uzayishda hisoblash texnikasi qay tarzda qollanilishi asosiy masala hisoblanadi.
Informatikada axborotlar ikki tuga – anolog va raqamli (diskret) axborotlarga bo’lib o’rganiladi.
Analog axborotlar uzluksiz mavjud bo’lib, uni istalgan vaqtda qabul qilish mumkin, boshqacha aytganda, analog axborotlar atrof muhitga(shu jumladan insonga ham) uzluksiz ta’sir etuvchi uzluksiz signallardir.
Tabiatda bu signallarning ikkita, aynan bir xil kombinatsiyasi uchramaydi. Biz ikkita aynan bir xil tovush, xatto bir daraxtda ikkita aynan bir xil yaproq uchratmaymiz. Ammo buning teskarisi, ya’ni bir xil shakilga ega bo’lib, turli mazmun kasb etadigan holat ham mavjud. Masalan bitta nota qog’ozda bitta yagona belgi bilan ifodalansada, u turli musiqa asboslarida (g’ichchak yoki nayda va boshqa ...) ijro etilganda, uning farqini darhos sezamiz.
Ta’kidlash lozimki, analog axborotni qayta ishlash uchun ularning biror davrdagi holatini ajratib olamiz va tahli qilishimiz lozim. Buning uchun esa bu axborotni boshqacha shakilga o’tkazishimiz lozim. Bunda turli belgilardan foydalanamiz. Har xil ranglarni tuli raqamlar bilan, tovushlarni esa notalar bilan belgilab, analog axborotni analoag axborotga aylantirishimiz mumkin.
Inson tamonidan yaratilgan qurilmalar ichida analog axborot bilan ishlaydiganlari ham, raqamli axborot bilan ishlaydiganlari ham mavjud. Analog qurilmalarga telivizor, telefon, raqamli qurilmalarga shaxsiy kompyuterlarni misol qilishimiz mumkin. Hozir raqamli televizorlar va raqamli telefonlar hayotimizdan chuqur o’rin olmoqda.
Biz axborotlarni turli-tuman signallar holatida qabul qilamiz. Signallarning turli tumanligi axborotlarni qayata ishlash jarayonini murakkablashtiradi. Shuning uchun ham axborotlarni to’plash, saqlash va qayta ishlashni osonlashtirish maqsadida ular bir xil shakilga keltiriladi, ya’ni qayta ishlash uchun qulay bo’lgan belgilar bilan almashtiriladi. Bu jarayon axborotlarni qayta ishlash deyiladi.
Hayotda axborotlarni kodlashni turli hil yo’llari mavjud. Ularga quyida siz bilan tanishadigan, Morze va harflarni raqamlash usullarini kiritish mumkin.