6-laboratoriya mashg’uloti graflar. Umumiy ma’lumotlar Graf

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)

http://hozir.org