Fan: Algoritm va berilganlar strukturasi. Mavzu: Graf nazaryasiga kirish,daraxtlar,ikkilik daraxtlar

Fan:Algoritm va berilganlar strukturasi. Mavzu:Graf nazaryasiga kirish,daraxtlar.

Graf ,Daraxt

Graf nazariyasi daraxtlarni, ulardan iborat elementlarning aloqalarini tasvirlash va ma'lumotlarni tahlil qilish uchun ishlatiladi. Daraxtlar, elementlarning (bunday daraxtlarda odatda "tugun" deb ataluvchi elementlar ishlatiladi) aloqalarini ifodalaydi.

Daraxtlar graf bo’ladi graf daraxt bolaolmaydi.

graf

Daraxt

Graf nazariyasi daraxtlarni, ulardan iborat elementlarning aloqalarini tasvirlash va ma'lumotlarni tahlil qilish uchun ishlatiladi. Daraxtlar, elementlarning (bunday daraxtlarda odatda "tugun" deb ataluvchi elementlar ishlatiladi) aloqalarini ifodalaydi.

Daraxtlarni taqdimot qilishning bir usuli matritsalar orqali amalga oshiriladi. Matritsalar yordamida aloqalar ro'yxatini ifodalash mumkin. Matritsa qator va ustunlaridan tashkil topadi va elementlari 0 va 1 qiymatlari bilan to'ldiriladi. 0 qiymati tugunlar orasidagi aloqani ifodalaydi, va 1 qiymati aloqaning mavjudligini anglatadi.

Daraxtlar ustida amallar ko'p turdagi operatsiyalar va tahlillarni o'z ichiga oladi. Quyidagi asosiy amallar daraxtlar ustida amalga oshiriladi: Daraxtda element qo'shish: Yangi tugun (bufer) qo'shish orqali daraxtga yangi element qo'shiladi. Buferning aloqa tugunlar bilan bog'liq bo'lishi kerak. Daraxtdan element o'chirish: Tugunni (buferni) o'chirish orqali daraxtdan element o'chiriladi. Buferning aloqa tugunlar bilan bog'liq bo'lishi kerak. Daraxt ustida element qidirish: Berilgan bir elementni daraxtda qidirish amaliyatini o'zgartirish mumkin. Bu amalning vaqti ham bilanadi. Daraxt elementlarining aloqasini tekshirish: Ikkilik daraxtlarda, elementlar orasidagi aloqalar to'g'rimi, yoki bir-biriga mos kelishini tekshirish amalga oshiriladi.

Graflar ustida amallar ko'p turlarda ishlatiladi. Graflar bir yoki bir nechta aloqador elementlarning aloqalarini tasvirlaydigan matematikiy jadvallar hisoblanadi. Graflarning ustida amallarni amalga oshirish uchun quyidagi asosiy operatsiyalar ishlatiladi: Graf elementini qo'shish: Yangi tugun (yoki boshqa aloqador element)ni grafga qo'shish orqali grafga yangi element qo'shiladi. Elementning aloqalariga qarab, aloqa tugunlari ham muayyanlanadi. Graf elementini o'chirish: Tugunni (yoki aloqador elementni) o'chirish orqali grafdan element o'chiriladi. Elementning aloqalariga qarab, aloqa tugunlari ham o'chiriladi. Graf ustida aloqalar bilan amal qilish: Graflar ustida yo'l topish, elementlarni qidirish, elementlar orasidagi yo'l uzunligini topish, boshqa graflar bilan biriktirish va tashqariga ma'lumotlarni jo'natish kabi amallar bajarish mumkin. Graf elementlari orasidagi aloqalarni tekshirish: Elementlar orasidagi aloqalar to'g'rimi, yoki bir-biriga mos kelishini tekshirish amalga oshiriladi.