|
11-маъруза Йўналтирил маган графлар
|
| bet | 1/4 | | Sana | 14.05.2024 | | Hajmi | 0,98 Mb. | | #230833 |
Bog'liq MBma`ruza1
O`ZBEKISTON RESPUBLIKASI TOSHKENT AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI MA`LUMOTLAR TUZILMASI VA ALGORITMLAR MUSTAQIL ISH
Guruh:swd023
Tekshirdi:AKBAROVA MARG`UBA
Bajardi:IKROMOV NURMUHAMMAD
Mavzu:Graf tushunchasi. Yoʻnaltirilgan va yoʻnaltirilmagan graflar
Граф тушунчаси
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
Yo’naltirilmagan graflar - Yo’naltirilmagan graf G=(V, E) – bu tugunlar va ularni birlashtirib turuvchi yoylar dan tashkil topgan tuzilma xisoblanadi. Undagi ixtiyoriy yoy teskarisi bilan teng va u yo’naltirilmagan yoy deyiladi.
- Agar bo’lsa, u xolda u va v tugunlar qo’shni deyiladi va e yoy esa insident deyiladi.
- Tugunlarning chiqish darajasi deb u bilan qo’shni tugunlar soniga aytiladi.
- Chiqish darajasi 0 ga teng bo’lgan tugunlar izolyasiyalangan tugun deyiladi.
|
| |
