|
Samarqand davlat universiteti o. R. Yusupov, I. Q. Ximmatov, E. Sh. EshonqulovBog'liq ALGORITMLAR VA MA‟LUMOTLAR STRUKTURALARI16-rasm. Graf turlari
Graf
- bu abstrakt obyekt boʻlib, uchlar toʻplami (tugunlar) va
qirralarning toʻplami - uchlar juftliklari orasidagi bogʻlanishlardan
tashkil topadi (ulanishlar). Graf mavzusi juda keng. Graflar diskret
matematikaning oʻrganish mavzusidir (bu yerda graf tushunchasining
aniqroq ta‘rifi berilgan). Graf murakkab tuzilgan ma‘lumotni tavsiflash
uchun ishlatiladi va shuning uchun katta amaliy ahamiyatga ega.
Matematikada graflar paydo boʻlishiga Eyler asarlari yordam berdi.
Graflar bilan qayerda uchrashamiz? Ehtimol, ular bilan qayerda
uchrashmasligimizni aytish osonroq. Ya‘ni biz graflarda juda koʻp
holatda uchratamiz. Misol qilib quyidagilarni keltirishimiz mumkin:
Lokal yoki global tarmoq modeli
Algoritmlarning blok-sxemasi
Elektr sxemalar
81
Oila daraxti (Shajara)
Metro xaritasi
Ma‘lumotlar bazasi modeli
Aqlli xaritalar
va boshqa koʻplab sohalarda qoʻllanilib kelmoqda. Ushbu darsda butun
graflar nazariyasini olish mumkin emas. Shuning uchun qisqacha
ma‘lumotlarni keltirib oʻtamiz.
G graf
- G: = (V, E) tartiblangan juftlik, bu yerda V - uchlarning
(yoki tugunlarning) boʻsh boʻlmagan toʻplami, E esa qirralar deb
nomlangan uchlarning juftlari toʻplamidir. Grafning uchlari va qirralari
(ular graf elementlari deb ataladi), grafdagi uchlar soni | V | - graf tartibi,
qirralarning soni | E | - graf hajmi deb ataladi.
17-rasm. Yoʻnaltirilmagan graf
18-rasm. Daraxt - bu bogʻlangan asiklik graf
Ildiz
ajdod
qirra
avlod
barg
|
| |
