O’zbekiston Respublikasi Axborot Texnologiyalari
va kommunikatsiyalarini rivojlantirish vazirligi
Muhammad Al-Xorazmiy nomidagi Toshkent
axborot texnologiyalari universiteti.
Kopyuter Injinirig fakulteti.
Malumotlar tuzilmasi va algoritmlar
Mustaqil ish
Guruh: 027-21
Bajardi: Tuychiyev Javohirbek
Mavzu: Graflarni ifodalash usullari
Reja:
I.Kirish:
1.1 Graflarning kelip chiqish tarixi.
II.Asosiy qism:
2.1 Graflar nazariyasining asosiy tushunchalari.
2.2 Graflarni ifodalash usullari.
2.3 Graflarni tasvirlash usullari
III.Xulosa;
IV.
Foydalanilgan adabiyotlar va saytlar ro‘yxati
Kirish:
Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler
tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan
Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar
nazariyasining paydo bo‘lishiga asos bo‘ldi.
Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko‘priklar joylashuvi
1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7
raqamlar bilan belgilangan. Pregel daryosi Kyonigsberg shahrini o‘sha davrda
to‘rtta , , va qismlarga bo‘lgan. Shaharning ixtiyoriy qismida joylashgan uydan
chiqib yettita ko‘priklardan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish
mumkinmi? Kyonigsberg ko‘priklari haqidagi bu masalani hal qilish jarayonida
graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut Eyler
sikli nomi bilan yuritiladi, mavjudligi shartlari ham topildi. Bu natijalar e’lon
qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan. L. Eylerning
bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo‘yicha yagona
ilmiy ish bo‘lib keldi.
XIX asrning o‘rtalarida graflar nazariyasi bilan bog‘liq tadqiqotlar G.
Kirxgof va A. Keli ishlarida paydo bo‘ldi.“Graf” iborasi D. Kyonig tomonidan
1936 yilda graflar nazariyasiga bag‘ishlangan dastlabki darslikda uchraydi.
Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida
qo‘llaniladi. Ulardan ba’zilari quyidagilardir: boshqotirmalarni hal qilish; qiziqarli
o‘yinlar, yo‘llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini
loyihalashtirish; avtomatlar, blok-sxemalar va kompyuter uchun programmalarni
tadqiq qilish va hokazo.
Matematik nazariyada va informatikada graf — bu tugunlar(uchlar)dan
iborat bo'lgan bo'sh bo'lmagan to'plam va tugunlarni birlashtiruvchi yoylar
majmuidir. Graf - bu murakkab chiziqsiz ko'pbog'lamli dinamik tuzilma bo'lib,
murakkab ob'ektlarning xususiyatlari va munosabatlarini aks ettiradi. Ob'ektlar
tugun yoki graf uzellari ko'rinishida va munosabatlar yoy yoki yo'naltirilgan
qirralar kabi ifodalanadi. «Graf» tushunchasini birinchi marotaba 1936 yil vengriya
matematigi Denni Kyonig kiritgan. Lekin graflar nazariyasi bo'yicha 1-ish Leonard
Eylerga tegishli bo'lgan va u 1736 yilda bajarilgan edi. XVIII asrda mashhur
shvetsariyalik matematik, mexanik va fizik Leonard Eyler (1707-1783 yy)
Kyonigsberg ko’prigi haqidagi masalani yechish uchun birinchi marta graf
tushunchasidan foydalanadi.
1-rasm. Eski Kyonigsberg shahri sxemasi
Graflar nazariyasi diskret matematika fanining bir bo’limi bo’lib, unda
masalalar yechimlari chizmalar shaklida izlanadi. Keyingi paytlarda turli xil
diskret xususiyatlarga ega bo‘lgan xisoblash qurilmalarini loyihalashda graflarning
ahamiyati yanada oshdi. (V, E) sonlar juftligiga graf deyiladi, bu yerda V –
ixtiyoriy bo`sh bo`lmagan to`plam, E esa ning qism to`plami , bunda V to`plam
elementlarining tartiblanmagan juftliklari to`plami.
V – to`plam elementlari grafning uchlari deyiladi.
E – to`plam elementlari esa grafning qirralari deyiladi.
Agar V chekli bo`lsa, graf chekli deyiladi, aks holda cheksiz graf deyiladi.
Yo'l (path) – bu bironta tugundan boshqa bir tugungacha bo'lgan yonmayon
joylashgan tugunlar ketma-ketligidir.
Grafning uchlari va qirralari to`plamini mos ravishda va kabi belgilanadi.
ushbu to’plamda uchlar berilgan bo’ladi. to’plamida esa qirallarning qushni uchlar
juftligi bilan aniqlanadi.
Qirra ikkita uch bilan aniqlanadi. Umumiy uchga ega bo`lgan ikkita qirra
qo`shni hisoblanadi. Agar grafning ikkita uchi qirra bilan tutashtirilgan bo`lsa, bu
uchlar qo`shni uchlar deyiladi. Grafning bir uchdan chiqqan ikki qirrasi qo`shni
qirralar deyiladi. Agar grafda boshi va oxiri bitta tugunda tutashadigan qirra
mavjud bo'lsa, unga ilmoqli qirra deyiladi.
2-rasm. Qirra tushinchasi.
Agar grafda takroriy (karrali) qirralar mavjud bo`lsa, bunday grafga
multigraf deyiladi. Agar grafda karrali qirralar bilan birga uchni o`z-o`zi bilan
tutashtiruvchi ilmoqlar ham mavjud bo`lsa, bunday grafga psevdograf deyiladi.
Hozirgi kunga kelib graflarda eng qisqa y’olni aniqlash uchun ko’plab
algoritmlar ishlab chiqilgan. Ularni amalga oshirish masalaning berilishiga qarab
foydalanish mumkin. Hayotiy masalalarida odatda vaznga ega bo’lgan graf
tuzilmalarida eng qisqa yo’lni aniqlash algoritmlari qullaniladi. 21 Vaznga ega
bo’lgan graf tuzilmasini kompyuter hotirasiga saqlash uchun quyidagi
belgilanishlarini aytib o’tamiz:
n – tugunlar soni;
m – qirralar soni;
g[n][n] – grafning qo’shma matritsasi;
g[n][m] – grafning intsidientlik matritsasi;
e[m] – grafning qirralar ro’yhati (uchta maydondan iborat (boshlangich va
yakunlovchi tugunlar raqami va qirraning og’irlik qiymati));
w[i][j] – qirraning og’irligi (vazni, o’lchami) matritsasi;
d – masofa birligi;
d[n] – berilgan tugundan boshqa tugunlarga qisqa masofalar massivi;
d[n][n] – tugundan boshqa tugunlarga masofalar matritsasi;
Algoritmlar tahlilini oddiy usuldan murakkab usuliga qarab ko’rib chiqamiz.
Ularga Floyd-Uorshell, Ford-Bellman va Deykstra algoritmlari kiradi.
Ushbu algoritmlarning samaradorligini oshirish orqali boshqa ko’plab
algoritmlar uchun asos bo’lib hisoblanadi. Masalan Li(to’lqinli) algoritmi, A star
(A*) algoritmi, Djonson algoritmi, Viterbi algoritmi, Cherkasskiy algoritmi va
boshqalar.
Yo’naltirilmagan, yo’naltirilgan va o’girlikka ega bo’lgan graflarni
kompyuter dasturlash
tillari xotirasida ifodalash
, ya'ni xotirada tashkil etish uchun
statik tuzilmasi matritsadan yoki dinamik tuzilmasi ro’yxatlardan foydalanish
mumkin. Har qanday masalalarida har bitta usulining o’zining afzalligi va
kamchiliklariga egadir. Yo’naltirilmagan, yo’naltirilgan va o’girlikka ega bo’lgan
graflarni ifodalash uchun har usulining o’zining qoida asosida shakllanadi.
Shunday to’rtta usullarga to’xtalib o’tamiz:
Qo'shma matritsa (adjacency matrix);
Intsidientlik matritsa (incidence matrix);
Qo'shnilik ro'yxati (adjacency list);
Qirralar ro'yxati (edges list).
G
grafning
qo'shma matritsasi bu n-o'lchamli A kvadrat matritsa bo'lib,
graf uchun:
Aij = 1 agar i va j tugunlar qirra bilan birlashtirilgan bo'lsa
Aij = 0 agar i va j tugunlar o’rtasida qirra mavjud bo'lmasa
orgraf uchun:
Aij = 1 agar i tugundan j tugunga yoy mavjud bo'lsa
Aij = 0 agar i va j tugunlarda yoy tugallanmagan bo'lsa
vaznga ega graf uchun:
Aij = Wij agar i va j tugunlar qirra (yoy) bilan birlashtirilgan bo'lsa
Aij = ∞ agar i va j tugunlar qirra (yoy) mavjud bo’lmasa
Qo'shma matritsa asosiy diagonaliga semmitrik bo’ladi, agar yo’naltirilmagan
grafni ifodalasa, orgraflarda esa nosimmetrik bo’ladi.
Qo'shma matritsaning qulaylik tomonlari quyidagilarda:
Qirra(yoy) qushish va o’chirish oson;
Tugunlar qo’shniligini tekshirish.
Qo'shma
matritsaning
noqulayliklari
esa
quyidagicha:
Tugunlarni kiritish yoki o’chirish;
Siyrak graflar bilan ishlash.
Qo'shma
matritsa
asosiy
diagonaliga
semmitrik
bo’ladi,
agar
yo’naltirilmagan grafni ifodalasa, orgraflarda esa nosimmetrik bo’ladi.
Qo'shma matritsaning qulaylik tomonlari quyidagilarda:
Qirra(yoy) qushish va o’chirish oson;
Tugunlar qo’shniligini tekshirish;
Qo'shma matritsaning noqulayliklari esa quyidagicha;
Tugunlarni kiritish yoki o’chirish;
Siyrak graflar bilan ishlash.
G grafning intsidientlik matritsasi bu n-satr(tugunlar) va m-ustunlar
(qirralar)dan tashkil topgan B matritsa bo'lib, unda:
| 