Muhammad ai-xorazmiy nomidagi toshkent axborot texnalogiyalari universiteti farg’ona filiali

MUHAMMAD AI-XORAZMIY NOMIDAGI TOShKENT AXBOROT TEXNALOGIYaLARI UNIVERSITETI FARG’ONA FILIALI

KOMPYUTER INJINERING KAFEDRASI AXBORT XAVFSIZLIGI YONALISHI 641-21-GURUX TALABASI

ABDUG’OFFOROV OMADBEKNING MA’LUMOTLAR TUZULMASI ALGORITM
FANIDAN TAYYORLAGAN
MUSTAQIL ISHI

Mavzu:Yo`naltirilgan va yo`naltirilmagan graflar

Reja:

i.
Graflar nazariyasi

ii.
Yo`natirilgan graflar
iii.
Yo`naltirilmagan graflar
iv.
Yo`naltirilgan va yo`naltirilmagan graflar farqi
v.
Xulosa
vi.
Foydalanilgan adabiyotlar
1736 yilda L. Eyler tomonidan o`sha davrda qiziqarli amaliy masalalardan bir hisoblangan Kyonisberg ko`priklari haqidagi masalalrni qo`yilishi va yechilishi graflar nazaryasining paydo bo`lishiga asos bo`ladi. Graflar nazariyasi bo`yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo`llaniladi. Ulardan bazilari quydagilardir: boshqotirmalarni hal qilish, qiziqarli o`yinlar, yo`llar, elektr zanjiri, integral szemalari va boshqarish sistemalarini loyixalashtirish, avtomatlar, blok sxemalar va kompyuter uchun programmalarni tadqiq qilish va hokazo.
Grafika - bu qirralar va tepaliklardan tashkil topgan matematik tuzilma. Grafika ba'zi bir havolalar orqali bog'langan (qirralar bilan ifodalangan) ob'ektlar to'plamini (tepaliklar bilan ifodalangan) ifodalaydi. Matematik belgilar yordamida grafik G bilan ifodalanishi mumkin, bu erda G = (V, E) va V - tepaliklar, E - qirralarning to'plami.

V1 V2 V1 V2 V3 V3

1-rasm 2-rasm

Yo`naltirilmagan grafika

Yo'naltirilmagan grafik - bu grafikning tepalarini bog'laydigan qirralarda yo'nalish bo'lmagan grafik. 1 -rasmda V = {V1, V2, V3} tepaliklar to'plami bilan yo'naltirilmagan grafik tasvirlangan. Yuqoridagi grafikdagi qirralarning to'plami V = {(V1, V2), (V2, V3), (V1, V3)} shaklida yozilishi mumkin. Shuni ham ta'kidlash mumkinki, qirralarning V = {(V2, V1), (V3, V2), (V3, V1)} deb yozilishiga hech narsa to'sqinlik qilmaydi, chunki qirralarning yo'nalishi yo'q. Shuning uchun yo'naltirilmagan grafikdagi qirralar tartibli juftliklar emas. Bu yo'naltirilmagan grafikning asosiy xarakteristikasi. Yo'naltirilmagan grafikalar tepaliklar bilan tasvirlangan ob'ektlar orasidagi nosimmetrik munosabatlarni ifodalash
uchun ishlatilishi mumkin. Masalan, shaharlar majmuasini bog'laydigan ikki tomonlama yo'l tarmog'ini yo'naltirilmagan grafik yordamida ko'rsatish mumkin. Shaharlar grafikdagi tepaliklar bilan ifodalanishi mumkin va qirralari shaharlarni bog'laydigan ikki tomonlama yo'llarni ifodalaydi.

Yo`naltirilgan grafika

Yo'naltirilgan grafika - bu grafikning tepaliklarni bog'laydigan qirralari yo'nalishga ega bo'lgan grafikdir. 2 -rasmda V = {V1, V2, V3} tepaliklar to'plami bilan yo'naltirilgan grafik tasvirlangan. Yuqoridagi grafikdagi qirralarning to'plami V = {(V1, V2), (V2, V3), (V1, V3)} shaklida yozilishi mumkin. Yo'naltirilmagan grafikdagi qirralar tartibli juftliklardir. Rasmiy ravishda, yo'naltirilgan grafikdagi e chekka e = (x, y) tartibli juftlik bilan ifodalanishi mumkin, bu erda x - chekkaning boshi, manbai yoki boshlang'ich nuqtasi deb nomlangan tepalik, y tepasi esa nuqta deyiladi , vertex yoki terminal nuqtasini tugatish. Masalan, shaharlar majmuasini bir tomonlama yo'llar yordamida bog'laydigan yo'l tarmog'i yo'naltirilmagan grafik yordamida ifodalanishi mumkin. Shaharlar grafikdagi tepaliklar bilan ifodalanishi mumkin va yo'naltirilgan qirralar shaharda transport harakati yo'nalishini hisobga olgan holda bog'laydigan yo'llarni ifodalaydi.
Yo'naltirilmagan grafikda tepaliklarni bog'laydigan qirralar bilan bog'liq yo'nalish yo'q. Yo'naltirilgan grafikda tepaliklarni bog'laydigan qirralar bilan bog'liq yo'nalish mavjud. Yo'naltirilgan grafikda chekka - bu tartibga solingan juftlik, bu erda tartiblangan juftlik ikki tepalikni bog'laydigan qirraning yo'nalishini ifodalaydi. Boshqa tomondan, yo'naltirilmagan grafikda chekka - bu tartibga solinmagan juftlik, chunki chekka bilan bog'liq yo'nalish yo'q. Yo'naltirilmagan grafikalar ob'ektlar orasidagi nosimmetrik munosabatlarni ifodalash uchun ishlatilishi mumkin.
Yo'naltirilmagan grafikdagi har bir tugunning darajasi va darajasi teng, lekin bu yo'naltirilgan grafik uchun to'g'ri emas. Yo'naltirilmagan grafikni ko'rsatish uchun matritsadan foydalanganda, matritsa har doim nosimmetrik grafikga aylanadi, lekin bu yo'naltirilgan grafikalar uchun to'g'ri emas. Yo'naltirilmagan grafikni har bir qirrani qarama -qarshi tomonga yo'naltirilgan ikkita qirraga almashtirish orqali yo'naltirilgan grafikka aylantirish mumkin. Biroq, yo'naltirilgan grafikn yo'naltirilmagan grafikaga aylantirish mumkin emas.

Xulosa:

Grafika - bu qirralar va tepaliklardan tashkil topgan matematik tuzilma. Yo'naltirilgan grafika - bu grafikning tepaliklarni bog'laydigan qirralari yo'nalishga ega bo'lgan grafikdir.

Yo'naltirilmagan grafik - bu grafikning tepalarini bog'laydigan qirralarda yo'nalish bo'lmagan grafik.
Yo'naltirilmagan grafikda tepaliklarni bog'laydigan qirralar bilan bog'liq yo'nalish yo'q. Yo'naltirilgan grafikda tepaliklarni bog'laydigan qirralar bilan bog'liq yo'nalish mavjud

Foydalanilgan adabiyotlar:

1.
AdamDrozdek.Data structure and algorithms in C++

2.
Fayl.org
3.
Googl.