Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
QARSHI FILIALI
TT va KT fakulteti 2-kurs TT 11-19- guruh talabasi
Mansurov Shuhratning Ma’lumotlar tuzilmasi va algoritmlari fanidan

MUSTAQIL ISHI

Qabul qildi: _______ M.Ro’ziqulova

Qarshi 2020

Mavzu: Graflarni ko’rikdan o’tkazish algoritmlari

Reja:
1.Graflarni ifodalash usullari
2.Qo’shma matritsa
3.Graflarni ko’rikdan o’tkazish

.

Graflar nazariyasining asosiy masalasi berilgan nuqtalar tutashtiruvchi chiziqlarning xossalaridan tashkil topadi. Bunday talqinda chiziqlarnig to’g’ri chiziq yoki kesma, yoylardan yoki egri chiziqlardan iborat bo’lishi hamda bu chiziqlar qaerda joylashishi, uzun yoki qisqa bo’lishi muhim emas. Shunisi muhimki bu chiziqlar berilgan ikki nuqtani tutashtiradi. 1736 – yilda L.Eyler tomonidan o’sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonisberg ko’priklari haqidagi masalaning qo’yilishi va echilishi graflar nazariyasining paydo bo’lishiga asos bo’ldi. Kyonisberg shaxridagi Pregel daryosi ustiga qurilgan ettita ko’prik o’sha vaqtda shaxarni to’rtta qismga ajratgan. Shaxarning ixtiyoriy qismida

joylashgan uydan chiqib ettita ko’rikdan faqat bir martadan o’tib, yana o’sha
uyga qaytib kelish mumkinmi? Kyonisberg ko’priklari haqidagi bu masalani hal
qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida
bu marshrut Eyler tsikli nomi bilan yuritiladi) mavjudligi shartlari ham topildi.
L.Eyler tomonidan e’lon qilingan tarixiy ilmiy ish yuz yildan kshproq vaqt
mobaynida graflar nazariyasi bo’yicha yagona ilmiy ish bo’lib keldi.
XIX asrning o’rtalarida graflar nazariyasi bilan bog’liq tadqiqotlar
G.Kirxgof (1924–1887, olmon fizigi) va A.Keli (1821–1895, ingliz matematigi)
ishlaarida paydo bo’ldi.
“Graf” iborasi D.Kyonig (1884–1944, venger matematigi) tomonidan 1936–
yilda graflar nazariyasiga bag’ishlangan dastlabki darsliklarda uchraydi.
Graflar nazariyasi bo’yicha tadqiqotlar natijalari inson faoliyatining turli
sohalarida qo’llaniladi. Ulardan ba’zilari quyidagilar: boshqotirmalarni hal
qilish; qiziqarli o’yinlar; yo’llar, elektr zanjirlari, integral sxemalari va
boshqarish sistemalarini loyihalashtirishva hakazo.
Avvalo grafning abstrakt matematik tushuncha sifatidagi ta’rifini keltiramiz.
Ixtiyoriy nuqtalarning qandaydir usulda bog’lanishidan tashkil topgan V
V to’plamni qaraymiz. Ushbu V to’plamni uchlar to’plami va uning v
elementlarini esa uchlar deb ataymiz. V Vto’plamning v1 Vva v2
ko’rinishidagi barcha juftliklar to’plamini (Vv1,v2 elementlaridan tuzilgan
V deb belgilaymiz.to’plamning o’z-o’ziga Dekrat ko’paytmasini) V
O va juftlikga aytiladiki, bu erda V V ,U Graf deb shunday
V to’plamning elementlaridanko’rinishidagi juftliklar bo’lib, V v1,v2  U
tuzilgandir. Grafni lotin alifbosining G harfi bilan belgilaymiz. Grafga ta’rif berishda boshqacha yondoshuvdan ham foydalanish mumkin. graf deb bir qancha V uchlar to’plamining birlashmasiga yokiV GG qaysi uchlar bog’langanligini ko’rsatuvchi juftliklarga1.1 V a,b a,b E aytiladi.
juftlik grafning1.1Mos ravishda grafning geometrik tasvirida aniq har bir
1.1qirrasi deyiladi, a va b uchlar esa E qirraning oxirlari deyiladi. Qirraning
ta’rifida uning oxirgi ikki uchining joylashish tartibi e’toborga olinishi ham,
olinmasligi ham mumkin. Agar bunday tartib mavjud bo’lmasa, ya’ni
deyish mumkin bo’lsa, u holda E ni yo’naltirilmagan qirrab,a a, b E
deb ataladi. Agar bunday tartib mavjud bo’lsa, u holda qirra yo’naltirilgan qirra
qirrada a boshlang’ich uch, b oxirgi ucha, b deyiladi. Yo’naltirilgan E
deb hisoblanadi. Shuningdek E qirrani a uchdan chiquvchi va b uchga
boruvchi qirra deyiladi. Qirra yo’naltirilgan
bo’lgan holda ham, qirra a va b uchlarga intsidient deba,b yo’naltirilmagan holda ham E ataladi.
Teorema 1.1.
Daraxtda ixtiyoriy ikki uch yagona zanjir bilan bog’langan bo’ladi.
Lokal darajalar. Agar grafni uni tashkil etuvchi qirralari soni sanoqli bo’lsa,
chekli graf, aksincha bo’lsa, cheksiz graf deb ataymiz. yo’naltirilmagan graf bo’lsin. Bitta a uchga intsidient bo’lgan qirralarG (1.2) kabi belgilaymiz. Birorasoni uning lokal darajasi deyiladi va uni uchning lokal darajasi hisoblanish jarayonida shu uchga intsidient bo’lagan sirtmoq uchun noaniqlik vujudga keladi. Ya’ni, sirtmoqni qanday hisobga qo’shish kerak; bitta qirra sifatidami yoki ikkita. Ushbu holatda qaralayotgan masalaga bog’liq ravishda qanday hisoblash qulaylik tug’dirsa, shunday hisoblagan ma’quldir. Shunga ko’ra, har bir holatda sirtmoqni qanday tartibda hisoblanganligi ko’rastilishi zarur.
Lokal daraja uchun bir necha sodda formulalar keltiramiz. G grafdagi a va
kabi belgilaymiz. Agarb,a a,bb uchlarni tutashtiruvchi qirralar sonini
grafda karrali qirralar bo’lmasa, u holda quyidagicha hollar bo’lishi mumkin:
0 a,b
1 a,b
Ko’rinib turibdiki, har bir (1.1.2) lokal darajada a uch uchun quyidagi yig’indi
mavjud:
(1.3)a,b a
Vb

Graflarni ifodalash usullari
Yo’naltirilmagan, yo’naltirilgan va o’girlikka ega bo’lgan graflarni kompyuter dasturlash tillari hotirasida 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.
G grafning intsidientlik matritsasi bu n-satr(tugunlar) va m-ustunlar (qirralar)dan tashkil topgan B matritsa bo'lib, unda:
graf uchun:
Bij = 1 agar i tugun j qirra bilan to'qnashgan bo'lsa
Bij = 0 agar i tugun j qirra bilan to'qnashmagan bo'lsa
orgraf uchun:
Bij = -1 agar i tugun j yoyning boshi bo'lsa
Bij = 0 agar i tugun j yoy bilan to'qnashmagan bo'lsa
Bij = 1 agar i tugun j yoyning oxiri bo'lsa