Yo’naltirilgan atsiklik graphlarni masalalar yordamida yoritish

Andijon Mashinasozlik instituti TJB va KT fakulteti ATT yo’nalishi 1-bosqich k_20-20-guruh talabasi Bahodirova Madinaning Axborotlarga ishlov berish algoritmlash fanidan tayyorlagan slayd.

Mavzu: Yo’naltirilgan atsiklik graflarni masalalar yordamida yoritish.

Qabul qildi: Butayev E .

Yo’naltirilgan atsiklik graflarni masalalar yordamida yoritish
1
2

Graflar haqida qisqacha ma’lumot

• Dastlab graflar haqida qisqacha tarixiy ma’lumotlar. Grafning abstratik matematik tushunchasi sifatidagi ta’rifi va u bilan bog’liq boshlang’ich tushunchalar, graflarning geomet rik ravishda , maxsus turdagi ko’p had yordanida, qqo’shnilik va insidentlik matritsalari vositasida berilishi yoritiladi . So’ngra grafning elementlari ustida sodda amallar, graflarni birlashtirish, biriktirish, ko’paytirishamallari, mar – shurutlar va zanjirlar , grafning bog’lamliligi tushunchasi, Eyler va Gamilton graflari, graflarda masofa tushunchasi, minimal masofali yo’l haqidagi graflarda masala, daraxt va unga ekvivalent tushunchalari, grafning siklomatik soni bayon qilinadi. Tarmoq tushunchasi , tarmoqdagi oqimlar, maxsimal oqim haqidagi masalava bu masalalarni hal qilish uchun Ford algoritmi ham ushbu bobda keltiriladi.

Graflar nazariyasining boshlang’ich ma ‘ lumotlari

• Graf, uch, qirra, yoy, yo’nalish, orgraf, qo’shni uchlar, yakkalangan uch, karrali qirralar, multigraf, psevdograf nol graf, to’la, belgilangan va izomorf graflar, grafning geometrik ifodalanishi, uchlar, qirralar va yoylarni insidentligi.
• Graflar nazariyasi haqida umumiy ma’lumotlar.
• 1736-yilda L.Eyler tomonidan o’sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyongsberg ko’priklari haqdiagi masalaning qo’yilishi va yechilishi graflar nazariyasining paydo bo’lishiga asos bo’ladi.
• Kyongsberg shahridagi Ptegel daryosi ustidagi yetti ko’prikning joylashishi 1-shakldagi qadimiy xaritada tasvirlangan.

Grafning abstrakt ta’rifi va u bilan bog’liq boshlng’ich tushunchalar

• Graflar nazariyasi bo’yicha tadqiqotlar natijalari inson faoliyatining turli sohaalarida qo’llaniladi. Ulardan ba’zilari quyidagilardir: boshqotirmalarni hal qilish; qiziqarli o’yinlar; yo’llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish, avtomatlash, blok sxemalar va kompyuter uchun programmalarni tadqiq qilish va hokazo.
• Avvalo , grafning abstrakt matematik tushunchasi sifatidagi ta’rifini va boshqa bazi sodda tushunchalarni keltiramiz. F qandaydir bo’sh toplam bo’lsin. Uning V1eF va V2eK elementlaridan tuzilgan ko’rinishidagi barcha juftliklar to’plamini (^to’plamni o’z-o’ziga Dekart ko’paytmasini)VxV bilan belgilaymiz.
• Graf deb shunday juftlikka aytiladiki, VxV to’plamning elementlaridan tuzilgan.
• Bundan buyon grafni belgilashda yozuv o’rniga yozuvdan foydalanamiz.Grafning tashkil etuvchilarini ko’rsatishmuhim bo’lmasa, u holda uni lo tin alifbosining bitta harf I bilan belgilaymiz.