|
LABORATORIYA ISHI - 24
Mavzu: Graf tushunchasi. Tasvirlash usullari
Ishdan maqsad. Ushbu laboratoriya ishida talabalar Graf tushunchasi bilan tanishib chiqishi kerak
Qo’yilgan masala. Talabalar topshiriq variantiga mos ravishda graf ustida berilgan amallar asosan bog’langan ro’yhatlar bilan ishlash ko’nikmasiga ega bo’lishlari kerak.
Ish tartibi:
Tajriba ishi nazariy ma’lumotlarini o‘rganish;
Berilgan topshiriqning algoritmini ishlab chiqish;
C++ dasturlash muhitida dasturni yaratish;
Natijalarni tekshirish;
Hisobotni tayyorlash va topshirish.
Graf - bu ba'zi bir juft ob'ektlar havolalar orqali bog'langan ob'ektlar to'plamining tasviriy tasviri. O'zaro bog'langan ob'ektlar tepaliklar deb nomlangan nuqtalar bilan ifodalanadi va tepaliklarni bog'laydigan bog'lanishlar qirralar deb nomlanadi.
Rasmiy ravishda, grafik - bu juftlik to'plami (V, E), bu erda V - tepaliklar to'plami va E - qirralarning to'plami, tepalik juftlarini bir-biriga bog'lab turadi. Quyidagi grafaga qarang
Yuqoridagi grafikada,
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Grafik ma'lumotlar tuzilishi
Matematik grafikalar ma'lumotlar tarkibida aks ettirilishi mumkin. Biz tepaliklar massivi va qirralarning ikki o'lchovli massivi yordamida grafani namoyish eta olamiz. Davom etishdan oldin, keling, ba'zi muhim shartlar bilan tanishib chiqamiz -
Vertex - Grafikning har bir tuguni vertex sifatida ifodalanadi. Quyidagi misolda belgilangan doira tepaliklarni aks ettiradi. Shunday qilib, A dan G gacha cho'qqilar. Biz ularni quyidagi rasmda ko'rsatilgandek massiv yordamida namoyish etishimiz mumkin. Bu erda A indeksni 0 bilan aniqlash mumkin, B 1 indeks yordamida va boshqalarni aniqlash mumkin.
Edge - Edge ikki tepalik orasidagi yo'lni yoki ikkita tepalik orasidagi chiziqni anglatadi. Quyidagi misolda A dan B gacha, B dan C gacha va hokazo chiziqlar qirralarni bildiradi. Quyidagi rasmda ko'rsatilgandek massivni ko'rsatish uchun biz ikki o'lchovli massivdan foydalanishimiz mumkin. Bu erda AB 0 qatorda 1, ustun 1da, BC 1 qatorda 1da, 2-ustunda va hokazolarda, boshqa kombinatsiyalarni 0 shaklida ushlab turilishi mumkin.
Yaqinlik - Ikkala tugun yoki tepaliklar bir-biriga chekka orqali ulangan bo'lsa, qo'shni. Quyidagi misolda B A bilan, C B bilan qo'shni va hokazo.
Yo'l - yo'l ikki tepalik orasidagi qirralarning ketma-ketligini anglatadi. Quyidagi misolda ABCD A dan D gacha bo'lgan yo'lni aks ettiradi.
Asosiy operatsiyalar
Quyida grafikaning asosiy asosiy operatsiyalari keltirilgan :
Vertex qo'shish - Grafikka vertex qo'shadi.
Edge qo'shish - Grafikning ikkita tepasi orasidagi chekka qo'shiladi.
Display Vertex - Grafika tepaligini namoyish etadi.
Grafika haqida ko'proq bilish uchun, iltimos, Grafik nazariyasi qo'llanmasini o'qing. Grafani bosib o'tish haqida kelgusi boblarda bilib olamiz.
Grafik - bu quyidagi ikki komponentdan iborat ma'lumotlar tuzilishi.
1. Tugunlar deb ham ataladigan cheklangan tepaliklar to'plami.
2. Shaklning tartiblangan juftligining cheklangan to'plami (u, v) chekka deb nomlanadi. Juftlik buyurtma qilingan, chunki (u, v) yo'naltirilgan grafik (di-grafik) holatida (v, u) bilan bir xil emas. Shaklning juftligi (u, v) u vertikaldan v tepaga qadar bir chekka borligini bildiradi, qirralarning vazni / qiymati / narxi bo'lishi mumkin.
Grafikalar hayotdagi ko'plab dasturlarni namoyish qilish uchun ishlatiladi: Grafikalar tarmoqlarni aks ettirish uchun ishlatiladi. Tarmoqlar shahar yoki telefon tarmog'idagi yoki elektron tarmoqdagi yo'llarni o'z ichiga olishi mumkin. Graflar, shuningdek, LinkIn, Facebook kabi ijtimoiy tarmoqlarda qo'llaniladi. Masalan, Facebook-da har bir odam vertex (yoki tugun) bilan ifodalanadi. Har bir tugun tuzilishga ega va shaxs identifikatori, ismi, jinsi va joyi kabi ma'lumotlarni o'z ichiga oladi. Grafikning ko'proq ilovalari uchun buni ko'ring.
Quyida 5 ta tepalikka ega bo'lgan yo'naltirilmagan grafikaga misol keltirilgan.
Quyidagi ikkitasi grafikaning eng ko'p ishlatiladigan tasvirlari.
1. Yaqinlik matritsasi
2. Yaqinlik ro'yxati
Shuningdek, boshqa hodisalar ham mavjud, "Intsident Matrix" va "Incident List". Grafik tasvirini tanlash vaziyatga xosdir. Bu butunlay bajariladigan operatsiyalar turiga va ulardan foydalanish qulayligiga bog'liq.
Yaqinlik ro'yxati:
Bir qator ro'yxatlar ishlatiladi. Massivning kattaligi tepalar soniga teng. Massiv bir qator bo'lsin []. Kirish massivi [i] ith vertexga qo'shni bo'lgan tepalar ro'yxatini aks ettiradi. Ushbu tasvir vaznli grafikani ko'rsatish uchun ham ishlatilishi mumkin. Qirralarning og'irliklari juftliklar ro'yxati sifatida ifodalanishi mumkin. Yuqorida keltirilgan grafikning qo'shni ro'yxati ko'rsatilgan.
Do'stlaringiz bilan baham: | 
