O’zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARNI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI QARSHI FILIALI

“KT va TT” Fakulteti TT-11-21 guruh talabasi “Ma’lumotlar tuzilmasi va algoritmlar” fanidan tayyorlagan 4-MUSTAQIL ISH

Qabul qildi: Zohidov J. Bajardi: Jumanazarova G.

2022

Yo’naltirilgan va Yo’naltirilmagan graflar.
Algoritmlarni to'g'ridan-to'g'ri o'rganishni boshlashdan oldin, siz grafiklarning o'zlari haqida asosiy bilimlarga ega bo'lishingiz, ularning kompyuterda qanday ifodalanishini tushunishingiz kerak. Grafik nazariyasining barcha jihatlari bu erda batafsil tavsiflanmaydi (bu shart emas), faqat bilmaslik dasturlashning ushbu sohasini o'zlashtirishni sezilarli darajada murakkablashtiradigan narsalar. Bir nechta misollar sizga grafik haqida qisqacha tasavvur beradi. Shunday qilib, odatiy grafik metro xaritasi yoki boshqa marshrutdir. Xususan, dasturchi kompyuter tarmog'ini yaxshi biladi, bu ham grafikdir. Bu erda umumiy chiziqlar bilan bog'langan nuqtalarning mavjudligi. Shunday qilib, kompyuter tarmog'ida nuqtalar alohida serverlar, chiziqlar esa har xil turdagi elektr signallaridir. Metroda birinchisi - stansiyalar, ikkinchisi - ular orasiga yotqizilgan tunnellar. Grafik nazariyasida nuqtalar deyiladi cho'qqilari (tugunlar) va chiziqlar - qovurg'alar (yoylar). Shunday qilib, grafik Qirralar bilan bog'langan cho'qqilar to'plami. Matematika narsalarning mazmuni bilan emas, balki ularning tuzilishi bilan ishlaydi, uni bir butun sifatida berilgan narsalardan mavhumlashtiradi. Aynan shu texnikadan foydalanib, biz har qanday ob'ekt haqida grafik sifatida xulosa qilishimiz mumkin. Grafiklar nazariyasi matematikaning bir qismi bo'lganligi sababli, uning uchun mutlaqo hech qanday ma'no yo'q, asosan, ob'ekt nima; muhimi, bu grafikmi, ya'ni grafiklar uchun zarur bo'lgan xususiyatlarga egami. Shuning uchun, misollar keltirishdan oldin, biz ko'rib chiqilayotgan ob'ektda faqat o'xshashlikni ko'rsatishga imkon beradigan narsani ajratib ko'rsatamiz, biz umumiyni qidiramiz. Keling, kompyuter tarmog'iga qaytaylik. U ma'lum bir topologiyaga ega va uni shartli ravishda ma'lum miqdordagi kompyuterlar va ularni bog'laydigan yo'llar shaklida tasvirlash mumkin
Grafiklar nazariyasida ishlatiladigan ba'zi muhim belgilar: G = (V, E), bu yerda G - grafik, V - uning uchlari, E - qirralar; | V | - tartib (cho'qqilar soni); |E | - grafik hajmi (qirralar soni). Bizning holatda |V | = 5, | E | = 10; Agar boshqa cho'qqiga istalgan cho'qqidan kirish mumkin bo'lsa, bunday grafik deyiladi yo'naltirilmagan ulangan grafik . Agar grafik ulangan bo'lsa, lekin bu shart bajarilmasa, bunday grafik deyiladi yo'naltirilgan yoki digraf. Yo'naltirilgan va yo'naltirilmagan grafiklarda cho'qqi darajasi tushunchasi mavjud. Verteks darajasi Uni boshqa uchlari bilan bog'laydigan qirralarning soni. Grafikning barcha darajalarining yig'indisi uning barcha qirralari sonining ikki barobariga teng. rasm uchun barcha kuchlarning yig'indisi 20 ga teng.
Yo'naltirilgan grafiklar quyidagi belgilarga ega: G = (V, A), bu erda V uchlari, A yo'naltirilgan qirralardir. Grafiklarning uchinchi turi aralashgan grafiklar . Ularning ikkala yo'nalishi va yo'nalishi bo'lmagan qovurg'alari mavjud. Rasmiy ravishda aralash grafik quyidagicha yoziladi: G = (V, E, A), bu erda qavs ichidagi harflarning har biri ilgari unga tegishli bo'lgan bir xil narsani bildiradi. havolalar(grafik chetining ikki uchining tartibi muhim emas) deyiladi yo'naltirilmagan . Barcha qirralari joylashgan grafiklar yoylar(grafik chetining ikki uchining tartibi muhim) deyiladi yo'naltirilgan grafiklar yoki digraflar . Yo'naltirilmagan grafik sifatida ifodalanishi mumkin yo'naltirilgan grafik agar uning har bir bo'g'ini qarama-qarshi yo'nalishli ikkita yoy bilan almashtirilsa.
Yo'naltirilgan grafik ikkita to'plamdan iborat: elementlari cho'qqilar deb ataladigan chekli V to'plam va elementlari qirralar yoki yoylar deb ataladigan chekli E to'plamdan iborat. Har bir yoy tartiblangan juft cho'qqilar bilan bog'langan. Belgilar cho'qqilarni, yoylarni belgilash uchun belgilar ishlatiladi. Agar, u holda ular oxirgi cho'qqilar deb ataladi; bu holda - boshlang'ich cho'qqi, - oxirgi cho'qqi. Bir juft boshlanish va tugatish uchlari bo'lgan barcha yoylar parallel deyiladi. Agar hodisa cho'qqisi uning ham boshlang'ich, ham oxirgi cho'qqisi bo'lsa, yoy halqa deyiladi. Yo'naltirilgan grafikning grafik tasvirida cho'qqilar nuqta yoki doira shaklida, qirralari (yoylar) esa segmentlar bilan ifodalanadi. nuqtalarni bog'laydigan chiziqlar yoki ularning oxirgi uchlarini ifodalovchi doiralar. Bunga qo'shimcha ravishda, yoylarga yo'nalish belgilanadi, u boshlang'ich cho'qqidan oxirigacha bo'lgan o'q bilan ko'rsatiladi.
Binar to’plamlar shaklidagi ma’lumotlar tuzilmasi.