19-ma`ruza. Ma’lumotlarning tarmoqli tuzilmalari. Graf tushunchasi va uning ko’rinishlari

1	2	3	4
5
1	0	1	0	0	1
2	1	0	1	1	1
3	0	1	0	1	0
4	0	1	1	0	1
5	1	1	0	1	0

13-rasm. Vaznsiz yo’naltirilgan graf
13-rasmda tasvirlangan graf uchun qo’shnilik matritsasi quyidagicha bo’ladi:

№ tugun	1	2	3	4
1	0	1	0	1
2	0	0	1	1
3	0	1	0	0
4	1	0	1	0

14-rasm. Vaznli yo’naltirilmagan graf
14-rasmda tasvirlangan graf uchun qo’shnilik matritsasi quyidagicha bo’ladi:

№ vershinы	1	2	3	4	5
1	0	40	0	0	18
2	40	0	22	6	15
3	0	22	0	14	0
4	0	6	14	0	22
5	18	15	0	20	0

Graflarni qo’shnilik vektori yordamida ham tasvirlash mumkin. Qo’shnilik vektori har bir tugun uchun qo’shni tugunlar nomerini saqlaydi (15-rasm).

15-rasm. Grafni qo’shnilik vektori orqali tasvirlashga misol
Grafni tasvirlashning yana bir usuli intsidentlik matritsasi hisoblanadi, bu matritsada grafning intsident elementlari (tugun va yoy) orasidagi bog’lanish ko’rsatiladi. Matritsa ustunlari yoylarga, satrlari esa tugunlarga mos qo’yiladi (16-rasm). Yo’naltirilmagan grafning intsidentlik matritsasining har bir elementi, agar tugun yoyga intsident bo’lmasa 0, yoki intsident bo’lsa 1 qiymatlar bilan to’ldiriladi. Yo’naltirilgan graf holatida (17-rasm), agar tugun yoyga intsident va uning boshlanish nuqtasi bo’lsa matritsaning mos elementiga 1 qo’yiladi, agar tugun yoyga intsident bo’lmasa 0 qo’yiladi, yoki agar tugun yoyga intsident, lekin uning oxiri hisoblansa -1 qo’yiladi.

16-rasm. Vaznli yo’naltirilmagan graf.
16-rasmda tasvirlangan vaznli yo’naltirilmagan grafning intsidentlik matritsasi quyidagi ko’rinishda bo’ladi:

№ vershinы	a	b	c	d	e
1	1	1	0	0	0
2	1	0	1	1	0
3	0	0	0	1	1
4	0	1	1	0	1

Vaznli yo’naltirilgan grafning intsidentlik matritsasiga misol.

17-rasm. Vaznli yo’naltirilgan graf
17-rasmda tasvirlangan vaznli yo’naltirilgan grafning intsidentlik matritsasi quyidagi ko’rinishda bo’ladi:

№ vershinы	a	b	c	d	e
1	1	-1	0	0	0
2	-1	0	1	1	0
3	0	0	0	-1	-1
4	0	1	-1	0	1

Qo’shnilik ro’yxati – graflarni ifodalashning yana bir usuli bu tugunlarning vertikal ro’yxatlari to’plami hisoblanadi. Grafning har bir tuguni ushbu tugunning “qo’shni”laridan tashkil topgan ro’yxatga mos keladi. Agar graf vaznli bo’lsa, u holda qo’shni-tugunlar raqami yonida ushbu qo’nishgacha bo’lgan yoy uzunligi ko’rsatiladi.

18-rasm. Yo’naltirilgan vaznli graf uchun qo’shnilik ro’yxati
Agar komp’yuter xotirasi yetarli bo’lsa, qo’shnilik ro’yxatiga nisbatan qo’shnilik matritsasidan foydalanish oson. Qo'shnilik ro'yxati bilan ko'rsatilgan grafda berilganlarga qo'shni bo'lgan tugunlarni izlash, yoylar va tugunlarni qo'shish va siyrak graflar bilan ishlash juda qulay. Biroq, bunday ko'rinish bilan elementni o'chirish va elementni qidirish noqulay.
Umuman olganda dasturlash orqali grafni ifodalashda qo’shnilik matritsasini ishlatish tavsiya etiladi, chunki bunday ifodalash orqali elementni qidirish juda qulay hisoblanadi.
Graflarni dasturiy qayta ishlash bo’yicha laboratoriya mashg’ulotlarida to’liq tanishib chiqamiz.
Adabiyotlar
1. [RU]  Alfred V. Axo., Djon E. Xopkroft, Djefri D. Ul’man. Struktura dannыx i algoritmы. //Ucheb.pos., M.: Izd.dom: "Vil’yams", 2000, — 384 s.
2. [EN] Adam Drozdek. Data structures and algorithms in C++. Fourth edition.Cengage Learning, 2013.
3. [UZ] I.M.Boynazarov. Dinamik ma’lumotlar tuzilmasi. Uslubiy qo’llanma. -Samarqand, TATU Samarqand filiali, 2018 y. 215 bet.
4. [UZ] Narzullaev U.X., Qarshiev A.B., Boynazarov I.M. Ma’lumotlar tuzilmasi va algoritmlar. //O’quv qo’llanma. Toshkent: Tafakkur nashriyoti, 2013 y. – 192 b.