|
Mustaqil ish-1 Mavzu: Graf daraxtini qurish va murakkablik darajasini baholash usullari Guruh
|
| bet | 1/2 | | Sana | 14.05.2024 | | Hajmi | 486,56 Kb. | | #233625 |
Bog'liq Aliqulov Farrux
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: 027-21-guruh talabasi
Bajardi: Aliqulov Farrux
Tekshirdi: Narmanov Otabek
Toshkent 2024
Mundarija:
Kirish
Asosiy qism:
Graf daraxti
Graf daraxtini Murakkabligini o’lchash
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 (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.
Daraxt atamasi 1857 yilda ingliz matematigi Artur Keyli tomonidan kiritilgan.
Algoritm ildiz tuguniga tashrif buyurish va keyin uning barcha qo'shnilarini rekursiv ravishda o'rganish orqali ishlaydi. Ushbu jarayon barcha tugunlarga tashrif buyurilgunga qadar grafikning barcha uchlari uchun takrorlanadi. O'tish jarayonida algoritm allaqachon o'rganilgan tugunni qayta ko'rib chiqmaslik uchun tashrif buyurilgan tugunlar ro'yxatini saqlaydi.
Grafik - bu cho'qqilar va qirralardan iborat chiziqli bo'lmagan ma'lumotlar strukturasi. Cho'qqilar ba'zan tugunlar deb ham ataladi va qirralar grafikdagi har qanday ikkita tugunni bog'laydigan chiziqlar yoki yoylardir. Rasmiyroq qilib aytganda, Grafik cho'qqilar to'plami ( V ) va qirralar to'plamidan ( E ) iborat. Grafik G(E, V) bilan belgilanadi.
Grafikning komponentlari
Vertices: Vertices - bu grafikning asosiy birliklari. Ba'zan, cho'qqilar cho'qqi yoki tugunlar sifatida ham tanilgan. Har bir tugun/cho'qqi etiketli yoki yorliqsiz bo'lishi mumkin.
Grafik turlari
Null grafik
Grafikda qirralar bo'lmasa, grafik null grafik deb nomlanadi.
Trivial grafik
Faqat bitta tepaga ega bo'lgan grafik, shuningdek, mumkin bo'lgan eng kichik grafikdir.
Yo'naltirilmagan grafik
Qirralari hech qanday yo'nalishga ega bo'lmagan grafik. Ya'ni tugunlar har bir chekkaning ta'rifida tartibsiz juftliklardir.
Yo'naltirilgan grafik
Qirrasi yo'nalishga ega bo'lgan grafik. Ya'ni tugunlar har bir chekkaning ta'rifida juftlik bilan tartiblangan.
Ulangan grafik
Bir tugundan biz boshqa istalgan tugunga tashrif buyurishimiz mumkin bo'lgan grafik bog'langan grafik deb nomlanadi.
Uzilgan grafik
Tugundan kamida bitta tugunga etib bo'lmaydigan grafik ajratilgan grafik deb nomlanadi.
Muntazam grafik
Har bir cho'qqining darajasi K ga teng bo'lgan grafik K muntazam grafik deb ataladi.
To‘liq grafik
Har bir tugundan bir-biriga chekka bo'lgan grafik.
Tsikl grafigi
Grafik o'z-o'zidan tsikl bo'lgan grafik, har bir cho'qqining darajasi 2 ga teng.
Tsiklik grafik
Kamida bitta tsiklni o'z ichiga olgan grafik siklik grafik deb nomlanadi.
Yo‘naltirilgan asiklik grafik
Hech qanday tsiklni o'z ichiga olmaydigan yo'naltirilgan grafik.
Ikki tomonlama grafik
Har bir to'plamdagi cho'qqida ular orasidagi chekka bo'lmasligi uchun cho'qqini ikkita to'plamga bo'lish mumkin bo'lgan grafik.
O'lchovli grafik
Qirralari allaqachon mos og'irlik bilan ko'rsatilgan grafik vaznli grafik deb nomlanadi.
Og'irlangan grafiklarni qo'shimcha ravishda yo'naltirilgan vaznli grafiklar va yo'naltirilmagan vaznli grafiklar deb tasniflash mumkin.
Daraxt v/s Grafik
Daraxtlar cheklangan turdagi grafiklardir, faqat bir nechta qoidalar mavjud. Har bir daraxt har doim grafik bo'ladi, lekin hamma grafiklar daraxt bo'lmaydi. Bog'langan ro'yxat, daraxtlar va uyalar - bularning barchasi grafiklarning alohida holatlaridir.
Grafiklarning tasviri
Grafikni saqlashning ikki yo'li mavjud:
Qo'shnilik matritsasi
Qo'shnilar ro'yxati
Qo'shnilik matritsasi
Ushbu usulda grafik 2D matritsa shaklida saqlanadi, bu erda satrlar va ustunlar cho'qqilarni bildiradi. Matritsadagi har bir yozuv ushbu cho'qqilar orasidagi chekka og'irligini ifodalaydi.
Qo'shnilar ro'yxati
Ushbu grafik bog'langan ro'yxatlar to'plami sifatida taqdim etilgan. O'sha cho'qqiga ulangan qirralarga ishora qiluvchi ko'rsatgichlar qatori mavjud.
Qo'shnilik matritsasi va qo'shnilik ro'yxati o'rtasidagi taqqoslash
Grafikda ko'p sonli qirralar bo'lsa, uni matritsa sifatida saqlash yaxshi, chunki matritsadagi faqat ba'zi yozuvlar bo'sh bo'ladi. Kamroq murakkablik uchun Prim va Dijkstra qo'shnilik matritsasi kabi algoritm ishlatiladi.
|
| |
