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

O‘ZBEKISTON RESPUBLIKASI OLIY TA’LIM, FAN VA

INNOVATSIYALAR VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
TELEKOMMUNIKATSIYA TEXNOLOGIYALARI FAKULTETI
Algoritmlarni loyihalash
Mustaqil ish-1
Mavzu:
Graf daraxtini qurish va murakkablik
darajasini baholash usullari
Guruh: 222-21
Bajardi: Obidov Xojiakbar
Tekshirdi: Begimov O’ktam
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.[1] 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.[2]

Koʻp daraxt[3] (yoki yoʻnaltirilgan daraxt[4] yoki yoʻnaltirilgan daraxt[5][6] yoki

yakka bogʻlangan tarmoq[7]) 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.