11-маъруза Йўналтирил маган графлар

12-маъруза Maʻlumotlar tarmoq tuzilmalari. Graf tushunchasi va uning ko‘rinishlari. Graflarni tasvirlash usullari

Граф тушунчаси
Def.2.
G=(V,E) juftlikka yo’naltirilgan graf (orgraf) deyiladi, bunda V - uchlari to’plami (tugun), E - esa yoylar (yo’naltirilgan yoqlar).
v
w
Izoh
Graf yoyi tartiblangan (v,w) juftlik ko’rinishida aniqlangan bo’lib, v - yoy boshi, w - esa yoy oxiri bo’ladi..
Eslatma
Ba’zan vw yoyda v uchidan w uchigacha olib boradi deyiladi, w ga esa v uchiga qo’shma deyiladi.
1
2
3
4
Def.3.
Orgrafda yo’l deb shunday v1, v2,…, vn tugunlar ketma-ketligi aytiladiki, bunda v1  v2, v2v3, … , vn-1vn yoylar mavjud bo’lishi shart..
Eslatma
Yo’l v1 dan boshlanadi va v2,…, vn-1 tugunlardan o’tib vn da yakunlanadi.
Def.4.
Yo’l uzunligi deb yo’lni tashkil etuvchi yoylar soniga aytiladi
Def.5.
Yo’l oddiy deyiladi, agar birinchi va so’ngi tugundan tashqari barcha tugunlar turli hil bo’lsa.
Chiziqsiz ma’lumotlar tuzilmasini mantiqiy tasvirlash
Qo’shma matrisa
Ko’rsatkichli bog’langan ro’yxat
Masalan, qo’shma matrisa orqali ifodalab olish
1
2
3
4
0
1
1
0
0
0
0
1
0
1
0
0
0
0
1
0