|
1-rasm. Yo’naltirilmagan graf.
2-rasm. Daraxt - bu bog'langan asiklik graf
Lug'at
Bu yerda biz graflar nazariyasidan (diskret matematikaning bir bo'limi) atamalarning kichik tanlovini qildik, ammo bu atamalar boshqa adabiyotlarda boshqacha berilgan bo’lishi mumkin.
Boshlang’ich terminologiya
|
O’zbek
|
Рус
|
En
|
Tavsif
|
Uch
|
Вершина
|
vortex
|
Grafning elementi
|
Tugun
|
Узел
|
node
|
Uch tushunchasi bilan bir xil
|
Qirra
|
Ребро
|
edge
|
Ikki qo'shni uchlarning bog’lanishi
|
Yoy
|
Дуга
|
arc
|
Qirra bilan bir xil, lekin orgrafda emas
|
Aloqa, bog’lanish, munosabat
|
Связь
|
link
|
Graf elementi (qirra yoki yoy)
|
Qo’shnilik
|
Смежность
|
adjacent
|
Ikkita uch o’rtasida aloqa mavjud bo’lganini bildiruvchi atama
|
Insidentlik
|
Инцидентность
|
incident on
|
Uchga nisbatan qirra haqida
|
Daraja
|
Степень
|
degree
|
Uchga tutashgan qirralarning soni
|
Asosiy tushunchalar
Grafdagi marshrut - bu har bir uch (oxirgisidan tashqari) ketma-ketlikdagi keyingi uchga qirra bilan bog'langan uchlarning cheklangan ketma-ketligi.
Yo'l - bu qirralarning takrorlanmagan yo'lidir. Oddiy zanjir - bu uchlarni takrorlamaydigan marshrut (bu oddiy zanjirda takrorlanadigan qirralarning yo'qligini anglatadi)
Orgrafdagi yo'naltirilgan marshrut (yoki yo'l) - bu har bir element oldingi va keyingi qismga tushadigan uchlar va yoylarning cheklangan ketma-ketligi.
Birinchi va oxirgi uchlar bir-biriga to'g'ri keladigan zanjirlar sikl deb ataladi (1-rasmda ACD va ACDE sikllar)
Yo'lning (yoki siklning) uzunligi uni tashkil etuvchi qirralarning soni deyiladi
Agar uning qirralari takrorlanmasa, yo'l (yoki sikl) oddiy deb nomlanadi; agar u sodda bo'lsa va undagi tepaliklar takrorlanmasa u elementar deb nomlanadi.
Graf turlari
Yo'naltirilgan graf - (qisqacha orgraf) - qirralari yo'naltirilgan graf (4-rasm pastga qarang).
Yo'naltirilmagan graf - uchlar juftligi tartiblanmagan graf (3-rasm, pastga qarang).
Bog'langan graf - bu har qanday uch juftligi o'rtasida kamida bitta yo'l mavjud bo'lgan graf.
Daraxt - bu bog'langan asiklik grafik, ya'ni sikllar yo'q va tepalik juftligi orasida bitta yo'l bor (2-rasm). Kirishning nol darajasiga ega bo'lgan uch daraxtning ildizi, chiqish nol darajaga ega tugunlar esa barglar deb nomlanadi.
Grafni tasvirlash usullari
Grafni tasvirlash uchun bir nechta usullardan foydalaniladi. Graflardan o'tish uchun siz o'zingizning muammoingizni eng samarali hal qiladiganlardan foydalanishingiz kerak. Ko'pincha, tanlov qo'shnilik matritsasi va qo'shnilik ro'yxati o'rtasida bo'ladi (quyidagi jadval ikkala yondashuvning samaradorligini taqqoslaydi). Shu bilan birga, o'rnatilgan C-massivga tayanib, o'zingizning ma'lumotlar tuzilmalaringizni modellashtirishingiz va STD-da mavjud bo'lgan turli xil konteynerlardan foydalanishingiz mumkin.
Qo’shnilik matritsasi
1 dan n gacha raqamlangan G grafning qo'shnilik matritsasi kvadrat kattalikdagi A matritsasi bo'lib, unda a [i][j] elementining qiymati 1 ga teng bo'lsa, grafning i- va j- uchlari qo’shni bo‘ladi, aks holda qiymati nolga teng bo‘ladi. Bunday matritsa binar matritsa deb ham ataladi. Oddiy graf uchun asosiy diagonal elementlari 0 ga teng bo‘ladi.
Qo'shnilik matritsasi orgrafni tavsiflash uchun ham, yo'naltirilmagan grafni tasvirlash uchun ham mos keladi. Yo'naltirilmagan graf uchun elementlarning qiymatlari asosiy diagonalga nisbatan nosimmetrikdir.
Qo'shnilik matritsadan foydalanish faqat qirralari ko'p bo'lmagan hamda murakkab bo‘lmagan graflar uchun afzalroqdir, chunki u har bir element uchun bitta bit saqlashni talab qiladi. Agar graf murakkab bo'lsa, unda xotiraning katta qismi nollarni saqlashga sarflanadi, ammo murakkab graflarda qo'shnilik matritsasi grafni xotirada ixchamroq ifodalaydi va taxminan bit xotiradan foydalanadi. Ushbu kattalik qo'shnilik ro'yxatlariga qaraganda yaxshiroq (pastga qarang).
3-rasm. Yo’naltirilmagan grafda qo’shnilik matritsasi
4-rasm. Orgrafda qo’shnilik matritsasi
Qo'shnilik matritsasini amalga oshirish uchun massivlar massivi qo'llaniladi: vektorlar vektori (vector>) yoki kaliti uchlar soni, qiymati esa vektori. Agar grafni kengaytirish kerak bo'lmasa, u holda vektorni array (massiv) bilan almashtirish kerak.
Insidentlik matritsasi
Insidentlik matritsasi - bu grafning elementlari (qirra - uch) orasidagi bog'lanishlar ko'rsatiladigan grafni tasvirlash shakli. Matritsaning ustunlari qirralarga, satrlar uchlarga to'g'ri keladi. Demak, matritsa kvadrat bo‘lmaydi. Matritsa yacheykasidagi nolga teng bo'lmagan qiymat uch va qirra (ularning insidentligi) o'rtasidagi munosabatni bildiradi.
Y o'naltirilgan graf holatida tegishli ustundagi har bir uch chiquvchi x vertikal qatorida "−1" va kiruvchi y uch qatorida "1" qiymatiga ega; agar uch va qirra o'rtasida hech qanday bog'liqlik bo'lmasa, unda mos keladigan katak "0" qiymatiga ega bo‘ladi.
5-rasm. Yo’naltirilmagan grafda insidentlik matritsasi
5-rasm. Orgrafda insidentlik matritsasi
Qo’shnilik ro'yxati
Qo’shnilik ro'yxati - bu grafni uchlar ro'yxati ("ro'yxatlar ro'yxati") to'plami sifatida ko'rsatish usuli - grafning har bir uchi qo'shni uchlar ro'yxatiga to'g'ri keladi. Masalan, 1-rasmni biz quyidagi qo'shnilik ro'yxati bilan tavsiflashimiz mumkin:
a: {b, c, d, e}
b: {a}
c: {a, d}
d: {a, c, e}
e: {a, f}
f: {e}
Bu sodda graflarni aks ettirish uchun ham, grafni kenglik yoki chuqurlikda bosib o'tish uchun asosiy algoritmlarni amalga oshirish uchun ham eng qulay usuldir, bu yerda siz hozirda ko'rib chiqilgan uchning "qo'shnilarini" tezda olishingiz kerak.
Qo’shnilik matritsalarini taqqoslash
Amal
|
Qo’shnilik ro’yxati
|
Qo’shnilik matritsasi
|
(x,y) qirraning mavjudligini tekshirish
|
O(|V|+|E|)
|
O(1)
|
Qirraning darajasini hisoblash
|
O(1)
|
O(|V|)
|
Sodda grafilar uchun xotiradan foydalanish
|
O(|V|+|E|)
|
O(|V|2)
|
Graflarda o’tish
|
O(|V|+|E|)
|
O(|V|2)
|
Do'stlaringiz bilan baham: |
