Graflar nazariyasi ning asosiy tushunchalari

qo'shma matritsasibu 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 matritsasibu 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
vaznga ega graf uchun:Bij = ±Wij agar i tugun yoy boshi(oxiri) bo'lsa
Bij = 0 agar i tugun j yoy bilan to'qnashmagan bo'lsa
Intsidientlik matritsaning qulaylik tomonlari quyidagilarda:
Qirra(yoy) o’lchamini yoki yo’nalishini o’zgartirish;
Qirra(yoy)larni qushish yoki o’chirish;
To’qnashuv(intsidientlik)ni tekshirish.
Intsidientlik matritsaning noqulayliklari esa quyidagicha:
Tugunlarni qushish yoki o’chirish;
Siyrak graflar bilan ishlash.
Qo'shnilik(qo'shni tugunlar) ro'yxati– bu A[n] massiv bo'lib, A[i] xar bir elementi i tugun bilan qo'shni tugunlar ro'yxatini o'zida saqlaydi.Qo'shnilik(qo'shni tugunlar) ro'yxati qulaylik tomonlari quyidagilarda:
Joriy (berilgan) tugunga qo’shni tugunni izlash;
Tugun yoki qirra(yoy)larni qushish;
Siyrak graflar bilan ishlash.
Qo'shnilik(qo'shni tugunlar) ro'yxati noqulayliklari esa quyidagicha:
Qirra(yoy)ning mavjudligini tekshirish;
Tugun yoki qirra(yoy)larni o’chirish.
Qirralar ro'yxati– qirralarning qo'shni tugunlar juftliklaridan iborat chiziqli ro'yxatdir.Qo'shnilik(qo'shni tugunlar) ro'yxati qulaylik tomonlari quyidagilarda:
Qirra(yoy)larni qushish yoki o’chirish;
Yoylarning yuklanishi bo’yicha tartiblash;
Siyrak graflar bilan ishlash.
Qo'shnilik(qo'shni tugunlar) ro'yxati noqulayliklari esa quyidagicha:
Tugun va qirra(yoy)ning qo’shniligini aniqlash;
Berilgan tugunga intsidient qirra(yoy)larni tanlash.
3. Graflarda ko'rik o'tkazish
Grafni ko'rikdan o'tkazish (Graph traversal) – bu berilgan tugundan boshlab barcha tugunlarni bir martadan ko'rib chiqish amalidir.Ko’rikdan o’tkazish ikkita usuli mavjud:
Chuqurligiga (tubiga) qarab qidirish (Depth-First Search – DFS)
Kengligiga (eniga) qarab qidirish (Breadth-First Search – BFS)
Bu usullar berilgan X tugundan boshlab bironta konteynerni qo'llagan holda barcha tugunlarni ko'rib chiqadi.
Chuqurlikka qarab ko'rishda stek tuzilmasiqo'llaniladi.
Kenglikka qarab ko'rishda esa navbat tuzilmasidanfoydalaniladi.
Tubiga qarab ko’rikni o’tqazish psevdokodi quyidagicha amalga oshiriladi
A tugundan boshlab tubiga qarab ko’rib chiqish misoli
Eniga qarab ko’rikni o’tqazish psevdokodi quyidagicha amalga oshiriladi
A tugundan boshlab eniga qarab ko’rib chiqish misoli
Nazorat savollar.
Graf nima va uning turlarini aytib bering.
Graflarni ko’rikdan o’tkazish algoritmlari.
Graflarni dasturda ifodalash usullari?
Adabiyotlar.
AdamDrozdek. Data structure and algorithms in C++. Fourth edition. 2013. Chapter 8. 391-490 betlar.
A computer science portal for geeks. http://www.geeksforgeeks.org/data-structures/#Graph
http://www.tutorialspoint.com/data_structures_algorithms/graph_data_structure.htm
http://fayllar.org