O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR
VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNOLOGIYALARI UNIVERSITETI
QARSHI FILIALI
TELEKOMMUNIKATSIYA
TEXNOLOGIYALARI
FAKULTETI
TT_11-22 GURUH TALABASINING
ALGORITMLARNI LAYIHALASH
FANIDAN
5-MUSTAQIL ISHI
BAJARDI:
Ziyadova Shahnoza
QABUL QILDI: Ablaqulov.K.B
QARSHI-2024
Mavzu:
Maʻlumotlar tarmoq tuzilmalari. Graf tushunchasi va uning
ko‘rinishlari. Graflarni tasvirlash usullari.
Reja:
1.
Graflar nazariyasining asosiy tushunchalari
2.
Graflarni ifodalash usullari
3.
Graflarda ko'rik o'tkazish
3
Matematik nazariyada va informatikada graf — bu tugunlar(uchlar)dan iborat
bo'lgan bo'sh bo'lmagan to'plam va tugunlarni birlashtiruvchi yoylar majmuidir.
Graf
- bu murakkab chiziqsiz ko'p bog'lamli dinamik tuzilma bo'lib, murakkab
ob'ektlarning xususiyatlari va munosabatlarini aks ettiradi. Ob'ektlar tugun yoki graf
uzellari ko'rinishida va munosabatlar yoy yoki yo'naltirilgan qirralar kabi ifodalanadi.
«Graf» tushunchasini birinchi marotaba 1936 yil vengriya matematigi Denni
Kyonig kiritgan. Lekin graflar nazariyasi bo'yicha 1-ish
Leonard Eylerga tegishli
bo'lgan va u 1736 yilda bajarilgan edi. XVIII asrda mashhur shvetsariyalik matematik,
mexanik va fizik Leonard Eyler (1707-1783 yy) Kyonigsberg ko’prigi
haqidagi
masalani yechish uchun birinchi marta graf tushunchasidan foydalanadi.
Graflar nazariyasi diskret matematika fanining bir bo’limi bo’lib, unda
masalalar yechimlari chizmalar shaklida izlanadi.
Keyingi paytlarda turli xil diskret xususiyatlarga ega bo‘lgan
xisoblash
qurilmalarini
loyihalashda
graflarning
ahamiyati
yanada
oshdi.
(
)
,
V E
sonlar juftligiga
graf deyiladi,
bu yerda
V
– ixtiyoriy bo`sh bo`lmagan
to`plam,
E
esa ning qism to`plami, bunda
V
to`plam elementlarining tartiblanmagan
juftliklari to`plami.
V
– to`plam elementlari grafning uchlari deyiladi.
E
– to`plam elementlari esa grafning qirralari deyiladi.
Agar
V
chekli bo`lsa, graf
chekli
deyiladi, aks
holda
