logo
  1. Главная страница
  2. Дипломные работы
  3. Общий
  4. DARAXT TUSHUNCHASI. DARAXTNING KOMPYUTER XOTIRASIDA TASVIRLANISHI

DARAXT TUSHUNCHASI. DARAXTNING KOMPYUTER XOTIRASIDA TASVIRLANISHI

Загружено в:

12.08.2023

Скачано:

0

Размер:

370.5048828125 KB
Скачать
Mundarija: KIRISH I-bob. DARAXT TUSHUNCHASI. DARAXTNING KOMPYUTER XOTIRASIDA TASVIRLANISHI. 1.1.Daraxt tushunchasi. Daraxtning kompyuter xotirasida tasvirlanishi 1.2. Daraxtlarni tasvirlash Binar (ikkilik) daraxtlar II-bob.DARAXT USTIDA BAJARILADIGAN ASOSIY AMALLAR 2.1.Daraxtlar bilan bajariladigan asosiy amallar; 2.2.Binar qidirish daraxtini tashkil qilish algoritmi 2.3. Daraxtlar. Eyler graflari III-bob. ILOVA Xulosa………………………………………………………………………… Foydalanilgan adabiyotlar va saytlar…………………………………………. 1 KIRISH . Mavzuning dolzarbligi.Bugungi kunda ma‘lumotlar oqimining ko‘pligi tufayli ularni qisqa vaqt ichida qayta ishlash muommosi ham ortib bormoqda. Hozirgi vaqtda axborot- kommunikasiya vositalari barcha turdagi tashkilot va muassasalarga shiddat bilan kirib kelmoqda. Axborotlarning haddan tashqari ko‘pligi bu axborotlarni saqlashda, qayta ishlashda, hamda har xil turdagi tizimlarni yaratish, ulardan keng foydalanishni va axborot tizimlari yaratishni talab qiladi. O‘zbekiston Respublikasi Prezidentining 2017 yil 7 fevraldagi PF-4947-son Farmoni bilan tasdiqlangan 2017-2021 yillarda O‘zbekiston Respublikasini rivojlantirishning beshta ustuvor yo‘nalishi bo‘yicha harakatlar strategiyasi mamlakatning davlat va jamiyat rivojlanishi istiqbolini strategik rejalashtirish tizimiga sifat jihatdan yangi yondashuvlarni boshlab berdi[1]. Unda belgilangan vazifalar sirasida ta‘lim va fan sohasini rivojlantirish ham aloxida ko‘zda tutilgan. O‘zbekiston Respublikasi birinchi Prezidentining 2012 yil 21 martdagi “Zamonaviy axborot-kommunikasiya texnologiyalarini yanada joriy etish va rivojlantirish chora-tadbirlari to‘g‘risida”gi PQ-1730 Qarori hamda “O‘zbekiston Respublikasida —Elektron ta‘lim milliy tarmog‘ini yaratish” investision loyihasini amalga oshirish chora-tadbirlari to‘g‘risida” gi PQ-1740 Qarori va me‘yoriy hujjatlar asosida algoritmik ta‘minot ishlab chiqish va joriy etish keng ko‘lamli hisoblanadi. Barcha tashkilot va muassasalarda avtomatlashtirilgan tizimlar yaratish ulardan keng ko‘lamda foydalanish uchun algoritmlash tillarini o‘rni katta hisoblanadi. Axborot tizimlari axborotni to‘plash, saqlash va qayta ishlash uchun, keng imkoniyatli maqsadlarda samarali foydalanish uchun xizmat qiladi. Zamonaviy axborotlashtirish tizimi, ma‘lumotlar integratsiyasi konsepsiyasiga asoslangan katta hajmdagi ma‘lumotlarni saqlash bilan tavsiflanadi va ko‘p sondagi foydalanuvchilarning turli xildagi talablariga javob berishi kerak bo‘ladi. Axborot tizimi va axborot texnologiyalarining avtomatlashtirilgan elementlarini qo‘llash va avtomatlashtirish asosida yangi axborot texnologiyasini yaratish avtomatlashtirish tizimlarini loyihalashtiruvchilarning asosiy vazifalaridan biri hisoblanadi Eyler graflari. 2 Graflar nazariyasining shakllanishi Kyonig- sberg ko'priklari haqidagi masala bilan bog'liq ekanligi yaxshi malum. L. Eyler 1736-yilda bu masalaning yechimga ega emasligini isbotladi. U graflar nazariyasining ancha umumiy hisoblangan quyidagi savoliga ham javob topdi: qanday shartlar bajarilganda, bog'lamli grafda barcha qirralardan faqat bir marta o'tadigan sikl mavjud bo'ladi? Grafning har bir qirrasidan faqat bir marta o'tadigan zanjir Eyler zanjiri, deb ataladi. Yopiq Eyler zanjiriga (ya'ni Eyler sik liga) ega graf Eyler graft, deb ataladi. Agar grafda yopiq bo'lmagan Eyler zanjiri topilsa, u holda bunday graf yarim Eyler graft, deb ataladi. Kurs ishining maqsadi : Elyer o’tuvchi daraxtlar mavzusini o’rganish Kurs ishining tuzilishi: Kurs ish kirish, 2 bob, 6 bo‘lim, umumiy xulosalar va tavsiyalar, foydalanilgan adabiyotlar ro‘yhatidan iborat bo‘lib, jami 30 sahifani tashkil qiladi 3 I-bob . DARAXT TUSHUNCHASI. DARAXTNING KOMPYUTER XOTIRASIDA TASVIRLANISHI . 1.1.Daraxt tushunchasi. Daraxtning kompyuter xotirasida tasvirlanishi Dastlab rekursiya so‘zining mazmuni haqida. Bu so‘z jarayonni ifodalaydi. Biron bir jarayon ro‘y berishi davomida yana shu jarayonning o‘zi ichma-ich takroriy ravishda bajarilsa, bunday jarayon rekursiv jarayon bo‘ladi. Masalan, faraz qilaylik, kompyuter ekraniga uning o‘zining tasvirini chizish kerak. Tasvirlangan ekranning ichida yana ekran tasviri bo‘lsin va h.k. bu jarayon rekursiv jarayondir. Endi rekursiv tuzilmalar haqida. Agar biron-bir ma‘lumotlar tuzilmasining har bir elementi yana xuddi shunday tuzilmadan iborat bo‘lsa, ushbu ma‘lumotlar tuzilmasi rekursiv tuzilma bo‘ladi. 4.2-rasmda misol sifatida S tuzilmadagi M 1 element aynan S tuzilmaga o‘xshash, M 2 elementda tashkil etuvchilar soni bitta ko‘p bo‘lsa-da, tuzilmasi S tuzilma bilan bir xil. Ya‘ni, ma‘lumotlarning rekursiv tuzilmasi - bu elementlari ham aynan shu tuzilma kabi ma‘lumotlardan iborat bo‘ladi. Daraxt tushunchasi. Daraxtning kompyuter xotirasida tasvirlanishi Daraxt - bu chiziqli bo‘lmagan bog ‘lamli ma‘lumotlar tuzilmasidir. 4 Daraxtlar quyidagi belgilari bilan tavsiflanadi: daraxtda ildiz deb ataluvchi shunday yagona element mavjudki, unga boshqa elementlardan murojaat mavjud emas; daraxtda ixtiyoriy elementga murojaat (element qiymatini olish) chekli sondagi ketma-ket murojaatlar yoki ko‘rsatkichlardan o‘tib borish orqali amalga oshiriladi; har bir element o‘zidan oldingi faqat bitta element bilan bog‘lanadi. 4.3- rasmda daraxtning tugunlari va ular orasidagi bog‘lanishlar tasvirlangan. Daraxtning ixtiyoriy tuguni oraliq tugun yoki terminal tugun (barg) bo‘lishi mumkin. 4.3-rasmdagi daraxtning M 1 va M 2 elementlari oraliq tugunlar, A, B, C, D, E lar esa barglardir. Terminal tugunning (bargning) asosiy xususiyati undan keyin tarmoqlanish (shoxning) yo‘qligidir. Daraxtdagi darajalar soni balandlik deb ataladi. Masalan 4.3-rasmdagi daraxtning balandligi 2 ga teng. Daraxtning tugunidan o‘sib chiquvchi shoxlar soni tugunning shoxlanish darajasi deyiladi. Masalan, 4.3-rasmdagi M 1 uchun shoxlanish darajasi 2, M 2 uchun esa 3 ga teng. SHoxlanish darajasi bo‘yicha daraxtlar quyidagi sinflarga ajratiladi: agar shoxlanish darajasi m ga teng bo‘lsa, bunday daraxt m-ar daraxt deyiladi; agar shoxlanish darajasi yoki 0, yoki m ga teng bo‘lsa, bunday daraxt to‘liq m-ar daraxt deyiladi; agar shoxlanish darajasining maksimal qiymati 2 ga teng bo‘lsa, bunday daraxt binar (ikkilik daraxt) deyiladi; 5 agar shoxlanish darajasi yo 0 ga, yo 2 ga teng bo‘lsa, bunday daraxt to‘liq binar daraxt deyiladi. Daraxt tugunlari o‘rtasidagi bog‘lanishlarni tavsiflash uchun «ota» va «bola» atamalari ishlatiladi. Masalan, 4.3-rasmdagi M 1 tugun A va B elementlar uchun «ota», A va B elementlar esa M 1 uchun «bola» hisoblanadi. Daraxtlarni tasvirlash Daraxtni tasavvur qilish va elementlarini qayta ishlash algoritmlarini tahlil qilishda uning chizma shaklidan foydalanish maqsadga muvofiq (4.4-rasm). Kompyuter xotirasida esa daraxtlarni bog‘lamli ro‘yxat shaklida tasvirlash ancha qulay. Bu ro‘yxatning elementlari tugunning qiymati va shoxlanish darajasi sonini saqlovchi axborot maydoniga hamda shoxlanish darajasiga teng bo‘lgan sondagi ko‘rsatkichlar maydoniga ega bo‘ladi. Elementning ixtiyoriy ko‘rsatkichi ushbu tugunni o‘zining o‘g‘il-tugunlariga yo‘naltiradi. Daraxtning grafik va chiziqli bo’lmagan ro’yxat shakllarida tasvirlanishi 1.2.Binar (ikkilik) daraxtlar Daraxtning eng ko‘p ishlatiladigan turlaridan biri binar daraxtdir. Daraxtni kompyuter xotirasida tasvirlashda har bir element 4 ta maydondan iborat yozuvni hosil qiladi. Bu maydonlarning qiymati mos ravishda yozuv kaliti, elementdan keyingi chap va o‘ng elementga ko‘rsatkichlar hamda yozuv qiymatidan iborat. 6 Binar daraxtni qurishda chap “bola” tugunga mos keluvchi yozuvning kaliti —ota” tugunga mos yozuvning kaliti qiymatidan kichik, o‘ng —bola” tugunga mos yozuvning kaliti esa - katta bo‘ladi. Misol uchun 50, 46, 61, 48, 29, 55, 79 kabi elementlardan tashkil topgan binar daraxtni qaraylik. Uning ko‘rinishi quyidagicha bo‘lsin: 1-rasm Binar daraxtni hosil qilish uchun xotirada tarkibi quyidagicha bo‘lgan elementlarni olish kerak (1-rasm): Xotirada daraxtga mos keluvchi ma'lumotlar tuzilmasini yaratish uchun MakeTree ( Key,Rec ) nomli protsedura ishlatilib, u xotirada ikki ko‘rsatkichga va ikki (kalit va axborot) maydonga ega bo‘lgan element (daraxt tuguni)ni hosil qiladi. MakeTree protsedurasining ko‘rinishi: Psevdokodda: p = getnode r(p) = rec k(p) = key v = p left(p) = nil right(p) = nil pA.right := nil; m-ar daraxtni binar daraxtga keltirish algoritmini quyidagicha yozish mumkin: daraxtning tugunlarida chap katta —bolaga mos keluvchi shoxdan boshqa barcha shoxlar kesib tashlanadi (2a-rasm); bir —ota”ning barcha —bola”lari gorizontal chiziqlar bilan birlashtiriladi (2b-rasm); 7 3. ushbu tuzilmadagi har bir element uchun uning ostida joylashgan element katta “bola” hisoblanadi (2v-rasm). 2a) 2b) 2v) 2 g) m-ar daraxtdan binar daraxtga o’tish 8 II-bob .DARAXT USTIDA BAJARILADIGAN ASOSIY AMALLAR 2.1.Daraxtlar bilan bajariladigan asosiy amallar Daraxtni aylanib chiqish (tugunlarni ketma-ket ko‘rib chiqish). Qismiy daraxtni o‘chirish. Qismiy daraxt qo‘shish. Daraxtni aylanib chiqish uchun quyidagi uchta protsedurani ishlatish zarur: Ildizni qayta ishlash. CHap shoxchani qayta ishlash. O‘ng shoxchani qayta ishlash. Bu uchala protsedura qanday ketma-ketlikda bajarilishi bilan bog‘liq holda daraxtni aylanib chiqish amalining uch xili bor: Yuqoridan-pastga qarab aylanib chiqish. Protseduralar 1-2-3 ketma- ketlikda bajariladi. CHapdan-o‘ngga aylanib chiqish. Protseduralar 2-1-3 ketma-ketlikda bajariladi. Pastdan-yuqoriga qarab aylanib chiqish. A, B, C, D, E, F, G –yuqoridan pastga; D, B, E, F, A, G –chapdan o’ngga; C, F, E, B, G, A –pastdan yuqoriga. 9 Daraxtni aylanib chiqishning turli usullari. Qismiy daraxtni o‘chirish amali. Bu amalni bajarish uchun o‘chiriladigan qismiy daraxt bog'langan tugunni va bu qismiy daraxtning indeksini ko‘rsatish zarur. Qismiy daraxtni o‘chirish amali uning asosiy daraxt bilan bog'lanishini bekor qilish, ya'ni element ko‘rsatkichiga nil ta'minlash va tugunning shoxlanish darajasini esa bir birlikka kamaytirish yo‘li bilan bajariladi. Qismiy daraxtni qo‘shish amali o‘chirishga teskari amaldir. Bu amalni bajarish uchun qo‘shiladigan qismdaraxt indeksini hamda biriktiriladigan tugunni bilish zarur. Qismdaraxt biriktiriladigan tugunning ko‘rsatkich maydoniga qismdaraxt ildizining adresi ta'minlanadi va tugunning shoxlanish darajasi bittaga oshiriladi. Qismdaraxt biriktirilgan “ota” tugunning «bola”lari soni bittaga ortganligi tufayli ular qaytadan nomerlab chiqiladi. Binar daraxtni aylanib chiqish. Qismdaraxtlarni aylanib chiqish ketma- ketligi bilan bog‘liq holda daraxtlarni aylanib chiqishning uchta ko‘rinishi mavjud (3- rasm): Yuqoridan pastga: A, V, S. CHapdan o‘ngga yoki simmetrik aylanib chiqish: V, A, S. Pastdan yuqoriga: V, S, A. 3-rasm Daraxtni chapdan o‘ngga yo‘nalishda aylanib chiqish algoritmi amaliyotda boshqalariga nisbatan ko‘proq qo‘llaniladi. SHuning uchun uni batafsilroq o‘rganish maqsadga muvofiq. Burning uchun tuzilishi sodda daraxt olinadi va qulaylik uchun intrave ( tree ) algoritmning satrlari nomerlab chiqiladi: 1: if tree <> nil 2: then intrave (left(tree)) 3: print info (tree) 4: intrave (right (tree)) 10 5: endif 6: return Yana qulaylik uchun ko‘rsatkichlar t^tree; l^left; r^right shaklda belgilab olinadi. 5-rasmda qaralayotgan oddiy daraxtni aylanib chiqish intrave(tree) protsedurasining bajarilishi namoyish qilingan. 5-rasm Oddiy daraxtni aylanib chiqish protsedurasi intrave(tree) ning rekursiv bajarilishi 2.2.Binar qidirish daraxtini tashkil qilish algoritmi Kalitlari 14, 18, 6, 21, 1, 13, 15 bo‘lgan elementlar berilgan bo‘lsin. 6- rasmda inary qidirishni tashkillashtirishga mo‘ljallangan daraxt tasvirlangan. Bu daraxtning e’tiborli tomoni shundaki, uni “chapdan o‘ngga” yo‘nalishida aylanib chiqilsa, o‘sish tartibida 1, 6, 13, 14, 15, 18, 21 ketma-ketlik hosil bo‘ladi. Ushbu daraxtni hosil qilish algoritmi quyida keltirilgan. 11 6-rasm 2.3. Daraxtlar. Eyler graflari Oriyentirlangan graflarda oriyentirlangan Eyler yo'lini izlash bilan shug'ullanish mumkin. Har bir yoydan faqat bir marta o'tadigan yo'l oriyentirlangan Eyler yo'li, deb ataladi. Tarkibida oriyentirlangan Eyler yo'li bor bo'lgan oriyentirlangan graf oriyen tirlangan Eyler grafi, deb ataladi. Endi qirralari soni n ga teng bo'lgan berilgan Eyler grafida Eyler zanjirini tuzishning Flyori algoritmini 1 keltiramiz. Bualgoritmga ко'ra, grafning qirralari Eyler siklida uchrashi tartibi bo'yicha 1 dan n gacha raqamlab chiqiladi. Berilgan Eyler grafi uchun Flyori algoritmiga binoan quyidagi ikkita qoida asosida ishlar ketma-ket bajariladi: Grafning ixtiyoriy v uchidan boshlab, bu uchga insident bo'lgan istalgan qirraga (masalan,^ qirraga) 1 raqami beriladi. Bu qirra grafdan olib tashlanadi va v uchdan V uchga (ya'ni olib tashlangan qirraga insident uchga) o'tiladi. Oxirgi o'tishdan oldingi o'tish natijasida hosil bo'lgan uch w bo'lsin va oxirgi o'tishda biror qirraga к raqami berilgan deylik. w uchga insident istalgan qirra imkoniyati boricha shunday tanlanadiki, bu qirrani olib tashlash grafdagi bog'lamlilikni buzmasin. Tanlangan qirraga navbatdagi (k+l) raqami beriladi va bu qirra grafdan olib tashlanadi. ■ 12 Flyori algoritmiga ko'ra, ish yuritish Eyler grafi uchun doimo chekli jarayon ekanligi va bu jarayon doimo grafdan barcha qirralarning olib tashlanishi, ya'ni Eyler zanjirini tuzish bilan tugashi isbotlangan. Shuni ham ta'kidlash kerakki, Flyori algoritmini qo'llash jarayonida qirralarni tanlash imkoniyatlari ko'p bo'lgani uchun, bunday vaziyatlarda, algoritmni qo'llash mavjud Eyler sikllaridan birini topish bilan cheklanadi.Tushunarliki, Flyori algoritmini takror qo'llab (bunda qirralarni tanlash jaroyoni algoritmini avvalgi qo'llashlardagidek aynan takrorlanmasligi kerak) grafda mavjud bo'lgan barcha Eyler sikllarini topish mumkin. 1-misol. 1-shaklda tasvirlangan grafni qaraymiz.Avvalo, bu grafning Eyler grafi bo'lishi shartini, ya'ni 1-teorema shartlarining bajarilishini tekshiramiz. Berilgan grafda to'qqizta uch bo'lib, 1, 3, 7, 9 belgili uch- larning darajasi ikkiga, 2, 4, 6, 8 belgili uchlarning darajasi to'rtga, 5 belgili uchning darajasi esa oltiga teng.Xullas, bu grafdagi barcha uchlarning darajalarijuftdir. Shu- ning uchun, 1-teoremaga ko'ra, 1 -shaklda tasvirlangan graf Eyler grafidir va uning tarkibida Eyler sikli mavjud. Berilgan grafga flyori algo ritmini qo'llab, mavjud Eyler sikl laridan birini aniqlaymiz. Dastlabki uch sifatida grafdagi 1 belgili uch olingan bo'lsin. Bu uchdan ikki yo'nalishda: (1;2) qirra bo'ylab yoki (1;4) qirra bo'ylab harakatlanish mumkin. Masalan, (1;2) qirra bo'ylab harakatlanib belgili uchga o'tamiz. Endi harakatni 3 yo'nalishda: yo (2;3) qirra bo'ylab, yo (2;4) qirra bo'ylab, yoki (2;5) qirra bo'ylab davom ettirish mumkin. Aytaylik, (2;3) qirra bo'ylab harakatlanib belgiliuchgao'tganbo'laylik. Shu usulda davometish mumkin bo'lgan Eyler sikllaridan birini, masalan, quyidag isiklnihosilqilamiz: ((1,2), (2,3),(3,5), (5,4), (4,6), (6,9), (9,8), (8,6), (6,5),(5,8), (8,7), (7,5), (5,2), (2,4),(4,1)). ■ 13 Daraxt haqida tushuncha Agar G grafda sikllar mavjud bo‘lmasa, u holda bunday graf - asiklik graf deyiladi. Asiklik grafda sikllar bo‘lmasligi, ya’ni sirtmoq, karrali qirralar bo‘lmasligi kerak. Daraxt deb, bog‘langan asiklik G grafga aytiladi. Sikllari mavjud bo‘lmagan bog‘lanmagan G graf, o‘rmon deyiladi. O‘rmonning bog‘lovchi kompanentasi sifatida daraxt ishlatiladi. O‘rmonning yoki daraxtning ixtiyoriy šismi o‘rmon yoki daraxt bo‘lib, ular sikllarga ega emas. Bunday grafdagi ixtiyoriy zanjir oddiy zanjir bo‘ladi. Teorema. Daraxtda ixtiyoriy ikkita a i va a j tugunlar bitta va faqat bita zanjir bilan bog‘langan. Ta’rif. A gar G grafning ixtiyoriy ikkita tuguni faqat bitta zanjir bilan bog‘langan bo‘lsa , G graf daraxt deb ataladi. Misol lar. Yo‘naltirilmagan daraxt. 1) 2) 3) 4) 15.3-Misol. Yo‘naltirilgan daraxt. 1) 2) 3) 14 Teorema. G chekli daraxtda tugunlar soni r, qirralar soni q dan bitta ortiq, ya’ni p=q+1. Aytaylik, a 0 ildizli G daraxtning tuguni a berilgan bo‘lsin. V (a) - a tugundan o‘tuvchi va ildiz a 0 bilan bog‘lovchi zanjirdagi tugunlar to‘plami bo‘lsin. Bu to‘plam G grafda G(a) graf ostini hosil qiladi. Graf osti G(a) a 0 ildizli daraxt G da a tugunning shaxobchasi deyiladi. Misol. Tugunlarning tipi. Aytaylik chekli G – daraxt berilgan bo‘lsin. Bu daraxtning chekka tugunlarini 1 tipli tugunlar deb ataymiz. Ta’kidlaymizki, agar daraxtning tugunlari soni 2 tadan ortiq bo‘lsa, u holda ular orasida chekka bo‘lmagan tugunlar mavjud bo‘ladi. Haqiqatdan ham, aytaylik a 1 va a 2 – G daraxtning chekka tugunlari bo‘lsin. U holda ular zanjir bilan bog‘langan bo‘lishi kerak. Agar bu zanjir faqat bitta qirradan iborat bo‘lsa, u holda a 1 va a 2 boshqa birorta ham tugun bilan bog‘lanmagan, bu esa daraxtning bog‘langanligiga ziddir. Agar bu zanjir 2 ta yoki ko‘proq širradan iborat bo‘lsa, u holda bu zanjir lokal darajasi 2 dan katta yoki teng bo‘lgan tugunlardan o‘tadi, ya’ni bu tugunlar chekka tugunlar emas . G daraxtdan hamma 1 tipli tugunlarni va ularga qo‘shma bo‘lgan qirralarni tashlab yuboramiz. U holda sikllarsiz bog‘langan G | daraxt qoladi. Haqiqatdan , ixtiyoriy a | , a ||∈ G || tugunlarni birlashtiruvchi zanjir L(a | ,a || ) G daraxtning chekka tugunlaridan o‘tmaydi, balkim to‘lig‘icha G | daraxtda yotadi. G | daraxt ham o‘z navbatida chekka tugunlarga ega bo‘ladi. Bu tugunlarni G daraxtdagi 2 tipli tugunlar deb ataymiz. Xuddi shu usul bilan 3, 4 va h.k tipli tugunlarni hosil qilamiz. 15 а || |а || а |а 1 а 2 а 9 V 8 а 7 а 6 а 5а 4 а 3 а 0 а 3 а 7а 5 а 0 g(а i ) – graf ости Misol . a) G: b) v) g) G | G || G ||| Demak G daraxtning markazi 4 –tipli a 1 , a 2 tugunlardan iborat. Misol . Ushbu daraxtning markazi 4-tipli a 1 , a 2 tugunlardan iborat. 163 2 1 1 2 11 1 111 1 3 1а 2а 1 22 2 4 4 1 1 112 343 2 4 4 3 2 1 111 а 1 43 1 21 1 а 2 343 4 44 Teorema. G daraxtning markazi deb, eng katta K - tipga ega bo‘lgan tugunlarga aytiladi. Teorema. Har bir G daraxtda bitta tugundan yoki ikkita qo‘shni tugunlardan iborat markaz mavju d dir. G grafning a tuguni chetki tugun deyiladi, agarda uning lokal darajasi ρ (a)=1. Chetki tugunga qo‘shma bo‘lgan qirra ham chetki širra deyiladi. Tasdiq. Agar chekli daraxtda tugunlar soni 1 tadan ortiq bo‘lsa, u holda u hech bo‘lmaganda ikkita chetki tugunga va hech bo‘lmaganda bitta chetki qirraga ega bo‘ladi. Isboti. Haqiqatdan, aytaylik a G daraxtning tuguni bo‘lsin. Bu tugun boshqa tugunlar bilan bog‘langanligi uchun, undan hech bo‘lmaganda bitta qirra chiqadi. Agar bu qirraning ikkinchi tomoning tuguni a | chetki bo‘lmasa, u holda undan yana bitta qirra chiqadi. Ushbu qirraning a || tugunidan yana bitta qirra chiqadi va hokazo. Shunday qilib, yangi tugunlardan o‘tuvchi zanjir šurish mumkin. Qaralayotgan G daraxt chekli bo‘lganligi uchun, zanjir qurish jaryoni ham cheklidir. Zanjirning oxirgi qirrasi va unga qo‘shma bo‘lgan tugunlardan biri chetkidir (a IV ) . Aytaylik, G daraxtda a 0 tugun berilgan bo‘lsin. Bu tugunni G daraxtning ildizi, G daraxt esa ildizli daraxt deyiladi. Bunday daraxtda qirralar yo‘naltirilgan bo‘ladi. Tugun a | ni ildiz a 0 bilan L zanjir orqali birlashtirish mumkin. Agar G daraxtda tugunlarni bog‘lovchi qirralarda yo‘nalish ko‘rsatilgan bo‘lsa va hamma qirralarning yo‘nalishi ildizdan boshlangan bo‘lsa, G daraxt yo‘naltirilgan daraxt deyiladi. Agar yo‘naltirilgan G daraxtda hamma qirralarning yo‘nalishini teskarisiga (ya’ni ildizga qarab ) o‘zgartirsak, u holda yana yo‘naltirilgan daraxt hosil bo‘ladi. Boshqacha aytganda yig‘uvchi tarmoq hosil bo‘ladi. 17а | а || а |V a а а | а || а ||I в а2Yo‘naltirilgan daraxtning har bir tuguniga (ildizdan tashqari) faqat bitta širra kiradi, ya’ni bu tugun fašat bitta qirraning tugashi bo‘ladi. Haqiqatdan ham, qaralayotgan tugunni ildizi bilan bog‘lovchi zanjirda bu qirra oxirgi hisoblanadi. Ildizga birorta ham qirra kirmaydi, ildiz bilan qo‘shma bo‘lgan xamma qirralar ildizni o‘zlarining ikkita tomoni bilan bog‘laydi, demak ildiz ularning boshlanishi deyiladi. Berilgan har bir G daraxtda ildiz sifatida ixtiyoriy tugunni olib, G daraxtni yo‘naltirilgan daraxtga aylantirish mumkin. Daraxtda siklomatik son. Aytaylik G chekli yo‘naltirilmagan daraxt bo‘lsin. Uning siklomatik soni deb γ ( G )= γ б + γ к− γ у , aytiladi. Bu yerda γб - grafning bog‘liqlik komponentalari soni; γк - grafning qirralar soni; γу - grafning tugunlari soni. Tasdiq. G daraxtning siklomatik soni 0 (nol) ga teng. Tasdiq. O‘rmonning siklomatik soni – bog‘langan daraxt komponentalarining yig‘indisi bo‘lib, u ham 0 (nol) ga teng. Tasdiq. Qolgan chekli graflarning siklomatik soni musbatdir, ya’ni γ (G)>0. Misol. γ (G)=2+4-4=2>0; 18a 4 a 2 a 3 a 1 a 4a 1 a 3 ILOVA #include<iostream> using namespace std; class Graph{ int V; int a; public: Graph(int V) {this->V = V; a = new list<int>[V]; } ~Graph() { delete [] a; } void addEdge(int v, int w); int isEulerian(); bool isConnected(); void DFSUtil(int v, bool visited[]); }; void Graph::addEdge(int v, int w){ a[v].push_back(w); a[w].push_back(v);} void Graph::DFSUtil(int v, bool visited[]){ visited[v] = true; list<int>::iterator i; for (i = a[v].begin(); i != a[v].end(); ++i) if (!visited[*i]) DFSUtil(*i, visited); } bool Graph::isConnected(){ bool visited[V]; 19 int i; for (i = 0; i < V; i++) visited[i] = false; for (i = 0; i < V; i++) if (a[i].size() != 0) break; if (i == V) return true; DFSUtil(i, visited); for (i = 0; i < V; i++) if (visited[i] == false && a[i].size() > 0) return false; return true;} int Graph::isEulerian(){ if (isConnected() == false) return 0; int o = 0; for (int i = 0; i < V; i++) if (a[i].size() & 1) o++; if (o > 2) return 0; return (o)? 1 : 2; } void test(Graph &g){ int res = g.isEulerian(); 20 if (res == 0) cout << "Grafik Eyler emas\n"; else if (res == 1) cout << "Grafikda Eyler yo'li mavjud\n"; else cout << "Grafikda Eyler sikli mavjud\n";} int main(){ Graph g1(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); test(g1); Graph g2(5); g2.addEdge(1, 0); g2.addEdge(0, 2); g2.addEdge(2, 1); g2.addEdge(0, 3); g2.addEdge(3, 4); g2.addEdge(4, 0); test(g2); Graph g3(5); g3.addEdge(1, 0); g3.addEdge(0, 2); 21 g3.addEdge(2, 1); g3.addEdge(0, 3); g3.addEdge(3, 4); g3.addEdge(1, 3); test(g3); Graph g4(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); test(g4); Graph g5(3); test(g5); return 0; } 22 Xulosa Men Bu kurs ishini yozishda o’z bilimlarimni yanada mustahkamladim. 1-teorema. Bog'lamli graf Eyler graft bo'lishi uchun undagi barcha uchlarning darajalari juft bo 'lishi zarur va yetarlidir. Isboti. Zarurligi. G Eyler grafida C—Eyler sikli bo'lsin. U holda С sikl bo'ylab harakatlanganda grafning har bir uchidan o'tish uchun bir juft qirradan foydalaniladi — bu qirralardan bin uchga kirish uchun, ikkinchisi esa uchdan chiqish uchun zarur bo'ladi. Bu yerda har bir uch darajasining juftligi С sikldagi har bir qirraning bir marta uchrashi mumkinligidan kelib chiqadi. Yetarliligi. Endi G grafning har bir uchi darajasi juft bo'lsin, deb faraz qilamiz. G graf bog'lamli bo'lgani uchun undagi har bir uchning darajasi ikkidan kichik emas.Ma'lumki, agar grafda har bir uchning darajasi ikkidan kichik bo'lmasa, u holda bunday graf tarkibida sikl mavjud (ushbu bobning 4-paragrafidagi 1-teore- maga qarang). Demak, G grafning qirralaridan tashkil etilgan qandaydir C 2 sikl bor. Bu siklni uning ixtiyoriy v, uchidan boshlab quramiz. Dastlab v, uchga insident bo'lgan ixtiyoriy bir qirrani tanlab, bu qirra bo'ylab harakatlanamiz va uning boshqa uchiga o'tamiz. Har safar, imkoniyati boricha, yangi qirra tanlab va bu qirradan o'tib, uning boshqa uchiga boramiz. Shuni ta'kidlash zarurki, bunday o'tishlar jarayonida faqat qirraning yangisini tanlashga harakat qilinadi, uchlar esa istalgancha takrorlanishi mumkin. Har bir uchga insident qirralar soni juft bo'lgani uchun C x siklni qurish jarayoni faqat v x uchga borgandagina tugaydi. Bu yerda ikki hoi bo'lishi mumkin: C x sikl G grafning barcha qirralaridan o'tadi yoki C x sikl G grafnir.p barcha qirralaridan o'tmaydi. , Birinchi holda teorema isbotlandi deyish mumkin. Ikkinchi holda G grafdan C x siklga tegishli barcha qirralarni olib tashlaymiz va natijada hosil bo'lgan grafni C x deb belgilaymiz. Bu yerda yakkalanib qolgan uchlarni olib tashlash yoki olib tashlamaslik muhim emas. Agar yakkalanib qolgan uchlar olib tashlanmasa, natijada bog'lamli bo'lmagan G x grafni hosil qilishimiz ham mumkin.Grafdan qirralarni bunday olib tashlash amali, tabiiyki, grafning qirralari sonini kamaytiradi, lekin grafdagi uchlarning darajalari juftligi xossasini o'zgartirmaydi. 1-natija. Bog'lamli graf yarim Eyler graft bo'lishi uchun undagi ikkitadan ко'p bo’lmagan uchning darajalari toq bo lishi zarur va yetarlidir. 23 Isboti 1-teoremaning isbotidan ba'zi o'zgartirishlar natijasida hosil qilinishi mumkin.■ Oriyentirlangan graflarda oriyentirlangan Eyler yo'lini izlash bilan shug'ullanish mumkin. Har bir yoydan faqat bir marta o'tadigan yo'l oriyentirlangan Eyler yo'li, deb ataladi. Tarkibida oriyentirlangan Eyler yo'li bor bo'lgan oriyentirlangan graf oriyen tirlangan Eyler grafi, deb ataladi. Endi qirralari soni n ga teng bo'lgan berilgan Eyler grafida Eyler zanjirini tuzishning Flyori algoritmini 1 keltiramiz. Bualgoritmga ко'ra, grafning qirralari Eyler siklida uchrashi tartibi bo'yicha 1 dan n gacha raqamlab chiqiladi. 24 Foydalanilgan adabiyotlar 1. Boltayev B.J , Azamatov A.R , Rahimov A.D “Algoritmlash va dasturlash asoslari” kitobi 2. A.M. Po’latov “Algoritmlash va C++ dasturlash asoslari” kitobi 3. A.R. Azamatov “Algoritmlash asoslari” kitobi 4. hozir.org: https://www.geeksforgeeks.org/eulerian-path-and-circuit 5. uzvikipediya. https://www.google.com/search?q=eyler+graflari&sxsr 6. arxiv.uz: https://www.google.com/search?q=euler+graph&oq=eyuler 25

Mundarija: KIRISH I-bob. DARAXT TUSHUNCHASI. DARAXTNING KOMPYUTER XOTIRASIDA TASVIRLANISHI. 1.1.Daraxt tushunchasi. Daraxtning kompyuter xotirasida tasvirlanishi 1.2. Daraxtlarni tasvirlash Binar (ikkilik) daraxtlar II-bob.DARAXT USTIDA BAJARILADIGAN ASOSIY AMALLAR 2.1.Daraxtlar bilan bajariladigan asosiy amallar; 2.2.Binar qidirish daraxtini tashkil qilish algoritmi 2.3. Daraxtlar. Eyler graflari III-bob. ILOVA Xulosa………………………………………………………………………… Foydalanilgan adabiyotlar va saytlar…………………………………………. 1

KIRISH . Mavzuning dolzarbligi.Bugungi kunda ma‘lumotlar oqimining ko‘pligi tufayli ularni qisqa vaqt ichida qayta ishlash muommosi ham ortib bormoqda. Hozirgi vaqtda axborot- kommunikasiya vositalari barcha turdagi tashkilot va muassasalarga shiddat bilan kirib kelmoqda. Axborotlarning haddan tashqari ko‘pligi bu axborotlarni saqlashda, qayta ishlashda, hamda har xil turdagi tizimlarni yaratish, ulardan keng foydalanishni va axborot tizimlari yaratishni talab qiladi. O‘zbekiston Respublikasi Prezidentining 2017 yil 7 fevraldagi PF-4947-son Farmoni bilan tasdiqlangan 2017-2021 yillarda O‘zbekiston Respublikasini rivojlantirishning beshta ustuvor yo‘nalishi bo‘yicha harakatlar strategiyasi mamlakatning davlat va jamiyat rivojlanishi istiqbolini strategik rejalashtirish tizimiga sifat jihatdan yangi yondashuvlarni boshlab berdi[1]. Unda belgilangan vazifalar sirasida ta‘lim va fan sohasini rivojlantirish ham aloxida ko‘zda tutilgan. O‘zbekiston Respublikasi birinchi Prezidentining 2012 yil 21 martdagi “Zamonaviy axborot-kommunikasiya texnologiyalarini yanada joriy etish va rivojlantirish chora-tadbirlari to‘g‘risida”gi PQ-1730 Qarori hamda “O‘zbekiston Respublikasida —Elektron ta‘lim milliy tarmog‘ini yaratish” investision loyihasini amalga oshirish chora-tadbirlari to‘g‘risida” gi PQ-1740 Qarori va me‘yoriy hujjatlar asosida algoritmik ta‘minot ishlab chiqish va joriy etish keng ko‘lamli hisoblanadi. Barcha tashkilot va muassasalarda avtomatlashtirilgan tizimlar yaratish ulardan keng ko‘lamda foydalanish uchun algoritmlash tillarini o‘rni katta hisoblanadi. Axborot tizimlari axborotni to‘plash, saqlash va qayta ishlash uchun, keng imkoniyatli maqsadlarda samarali foydalanish uchun xizmat qiladi. Zamonaviy axborotlashtirish tizimi, ma‘lumotlar integratsiyasi konsepsiyasiga asoslangan katta hajmdagi ma‘lumotlarni saqlash bilan tavsiflanadi va ko‘p sondagi foydalanuvchilarning turli xildagi talablariga javob berishi kerak bo‘ladi. Axborot tizimi va axborot texnologiyalarining avtomatlashtirilgan elementlarini qo‘llash va avtomatlashtirish asosida yangi axborot texnologiyasini yaratish avtomatlashtirish tizimlarini loyihalashtiruvchilarning asosiy vazifalaridan biri hisoblanadi Eyler graflari. 2

Graflar nazariyasining shakllanishi Kyonig- sberg ko'priklari haqidagi masala bilan bog'liq ekanligi yaxshi malum. L. Eyler 1736-yilda bu masalaning yechimga ega emasligini isbotladi. U graflar nazariyasining ancha umumiy hisoblangan quyidagi savoliga ham javob topdi: qanday shartlar bajarilganda, bog'lamli grafda barcha qirralardan faqat bir marta o'tadigan sikl mavjud bo'ladi? Grafning har bir qirrasidan faqat bir marta o'tadigan zanjir Eyler zanjiri, deb ataladi. Yopiq Eyler zanjiriga (ya'ni Eyler sik liga) ega graf Eyler graft, deb ataladi. Agar grafda yopiq bo'lmagan Eyler zanjiri topilsa, u holda bunday graf yarim Eyler graft, deb ataladi. Kurs ishining maqsadi : Elyer o’tuvchi daraxtlar mavzusini o’rganish Kurs ishining tuzilishi: Kurs ish kirish, 2 bob, 6 bo‘lim, umumiy xulosalar va tavsiyalar, foydalanilgan adabiyotlar ro‘yhatidan iborat bo‘lib, jami 30 sahifani tashkil qiladi 3

I-bob . DARAXT TUSHUNCHASI. DARAXTNING KOMPYUTER XOTIRASIDA TASVIRLANISHI . 1.1.Daraxt tushunchasi. Daraxtning kompyuter xotirasida tasvirlanishi Dastlab rekursiya so‘zining mazmuni haqida. Bu so‘z jarayonni ifodalaydi. Biron bir jarayon ro‘y berishi davomida yana shu jarayonning o‘zi ichma-ich takroriy ravishda bajarilsa, bunday jarayon rekursiv jarayon bo‘ladi. Masalan, faraz qilaylik, kompyuter ekraniga uning o‘zining tasvirini chizish kerak. Tasvirlangan ekranning ichida yana ekran tasviri bo‘lsin va h.k. bu jarayon rekursiv jarayondir. Endi rekursiv tuzilmalar haqida. Agar biron-bir ma‘lumotlar tuzilmasining har bir elementi yana xuddi shunday tuzilmadan iborat bo‘lsa, ushbu ma‘lumotlar tuzilmasi rekursiv tuzilma bo‘ladi. 4.2-rasmda misol sifatida S tuzilmadagi M 1 element aynan S tuzilmaga o‘xshash, M 2 elementda tashkil etuvchilar soni bitta ko‘p bo‘lsa-da, tuzilmasi S tuzilma bilan bir xil. Ya‘ni, ma‘lumotlarning rekursiv tuzilmasi - bu elementlari ham aynan shu tuzilma kabi ma‘lumotlardan iborat bo‘ladi. Daraxt tushunchasi. Daraxtning kompyuter xotirasida tasvirlanishi Daraxt - bu chiziqli bo‘lmagan bog ‘lamli ma‘lumotlar tuzilmasidir. 4

Daraxtlar quyidagi belgilari bilan tavsiflanadi: daraxtda ildiz deb ataluvchi shunday yagona element mavjudki, unga boshqa elementlardan murojaat mavjud emas; daraxtda ixtiyoriy elementga murojaat (element qiymatini olish) chekli sondagi ketma-ket murojaatlar yoki ko‘rsatkichlardan o‘tib borish orqali amalga oshiriladi; har bir element o‘zidan oldingi faqat bitta element bilan bog‘lanadi. 4.3- rasmda daraxtning tugunlari va ular orasidagi bog‘lanishlar tasvirlangan. Daraxtning ixtiyoriy tuguni oraliq tugun yoki terminal tugun (barg) bo‘lishi mumkin. 4.3-rasmdagi daraxtning M 1 va M 2 elementlari oraliq tugunlar, A, B, C, D, E lar esa barglardir. Terminal tugunning (bargning) asosiy xususiyati undan keyin tarmoqlanish (shoxning) yo‘qligidir. Daraxtdagi darajalar soni balandlik deb ataladi. Masalan 4.3-rasmdagi daraxtning balandligi 2 ga teng. Daraxtning tugunidan o‘sib chiquvchi shoxlar soni tugunning shoxlanish darajasi deyiladi. Masalan, 4.3-rasmdagi M 1 uchun shoxlanish darajasi 2, M 2 uchun esa 3 ga teng. SHoxlanish darajasi bo‘yicha daraxtlar quyidagi sinflarga ajratiladi: agar shoxlanish darajasi m ga teng bo‘lsa, bunday daraxt m-ar daraxt deyiladi; agar shoxlanish darajasi yoki 0, yoki m ga teng bo‘lsa, bunday daraxt to‘liq m-ar daraxt deyiladi; agar shoxlanish darajasining maksimal qiymati 2 ga teng bo‘lsa, bunday daraxt binar (ikkilik daraxt) deyiladi; 5

Похожие

Daraxtlar, ikki tomonlama daraxtlar. Ikkilik daraxtlarning vakili. Ikkilik daraxtlarning o'tishi
Graflarni kampyuter xotirasida aks ettirish
Ikkkilik qidruv daraxti
Matritsalarni ko’paytirish algoritmlari
Balanslangan qidiruv daraxtlari