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 vw 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, v2v3, … , vn-1vn 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
Do'stlaringiz bilan baham: |