Mavzu: Graf daraxtini qurish va murakkablik darajasini baholash usullari

MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI KOMYUTER INJINIRINGGI FAKULTETI

Algoritmlarni loyihalash

Mustaqil ish-1
Mavzu: Graf daraxtini qurish va murakkablik darajasini baholash usullari




Bajardi: Xayitboyev Bekzod


Toshkent 2023

Mundarija:

1. 
   Kirish
   
2. 
   Asosiy qism:
   

Graf daraxti
Graf daraxtini qurish
Graf daraxtini Murakkabligini o’lchash
Dastur kodi
3) Xulosa
4)Foydalanilgan adabiyotlar

Graf daraxti

Grafik nazariyasida daraxt yo'naltirilmagan, bog'langan va asiklik grafikdir. Boshqacha qilib aytganda, hatto bitta siklni ham o'z ichiga olmagan bog'langan grafik daraxt1 deyiladi. Daraxt ierarxik tuzilmani grafik shaklda ifodalaydi.
Grafik daraxti algoritmi - bu ildiz deb ataladigan ma'lum bir tugundan boshlab, grafikning barcha uchlari va qirralarini o'rganish uchun ishlatiladigan grafik o'tish algoritmining bir turi. Ushbu algoritmda grafik daraxtga o'xshash struktura sifatida qaraladi, ildiz tugunlari boshlang'ich nuqtadir.
Grafiklar nazariyasida daraxt - bu yo'naltirilmagan grafik bo'lib, unda har qanday ikkita cho'qqi aynan bitta yo'l bilan bog'langan yoki ekvivalent ravishda bog'langan asiklik yo'naltirilmagan grafikdir. O'rmon - bu yo'naltirilmagan grafik bo'lib, unda har qanday ikkita cho'qqi ko'pi bilan bitta yo'l bilan bog'langan yoki ekvivalent ravishda asiklik yo'naltirilmagan grafik yoki ekvivalent daraxtlarning ajratilgan birlashuvi bilan bog'langan.

Koʻp daraxt[3] (yoki yoʻnaltirilgan daraxt yoki yoʻnaltirilgan daraxt yoki yakka bogʻlangan tarmoq) yoʻnaltirilgan asiklik grafik (DAG) boʻlib, uning ostidagi yoʻnaltirilmagan grafigi daraxtdir. Ko'p o'rmon (yoki yo'naltirilgan o'rmon yoki yo'naltirilgan o'rmon) yo'naltirilgan asiklik grafik bo'lib, uning asosiy yo'naltirilmagan grafigi o'rmondir.

A labeled tree with 6 vertices and 5 edges.