Tadqiqot usuli: BMIda qo’yilgan maqsadni amalga oshirish uchun hosilaning sonli approksimasi yordamida Laplas operatorining sonli approksimasiyasi topildi, matematik analiz va funksional analizdagi tushunchalardan foydalanib Laplas operatorining xos qiymatlari va mos xos funksiyalari o’rganildi.
BMIning hajmi va tuzilishi: Ushbu bitiruv malakaviy ishi kirish, 2 bob, 7 ta paragraf, har bir bobning xulosalari, xotima, foydalanilgan adabiyotlardan iborat.
Olingan asosiy natijalar: BMI referativ xarakterga ega bo’lsada, unda keltirilgan ma’lumotlar bakalavriyat o’quv dasturiga kiritilmagan.
1-bob
Mavzu : Graflar nazariyasi elementlari.
1.1 Graflar nazariyasi haqida umumiy ma’lumotlar.
1736-yilda Eyler tomonidan o’sha davrda qiziqarli bo’lgan amaliy masalalardan biri hisoblanganKuonidsberd ko’priklari haqidagi masalaning qo’yilishi va yechimlari graflar nazariyasining paydo bo’lishiga asosbo’lgan. XIXasrning o’rtalarida graflar nazariyasi bilan bog’liq tadqiqotlar G. Kichxdof va A. Kaliishlarida paydo bo’lgan.
“ Graf ” iborasi D.Kuopid tomonidan 1936- yilda graflar nazariyasiga bag’ishlangan dastlabki darslikda uchraydi. Graflar nazariyasibo’yicha tadqiqotlar natijalari inson faoliyatining turli soxalarida qo’llaniladi. Ulardan ba’zilari quyidagilar: boshqotirmalarni hal qilish, qiziqarli o’yinlar, yo’llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyixalashtirish, avtomatlar, blok – sxemalar kompyuter uchun programmalar tadqiq qilish va xokazo.
Avval grafning abstrakt ta’rifi va u bilan bog’liq boshlang’ich tushunchalarni keltiramiz . Grafning abstraktmatematik tushuncha sifatidagi ta’rifini va boshqa sodda tushunchalarni bayon qilamiz. qandaydir bo’shbo’lmagan to’plam bo’lsin . Uning vaelementlaridan tuzilganko’rinishdagi barcha juftliklar to’plamini bilan belgilaymiz.
Graf deb shundayjuftlikka aytiladiki, bu yerda va ko’rinishdagi juftliklar korteji bo’lib to’plamning elementlaridan tuzilgandir.
Bundan keyin belgilash o’rniga dan foydalanamiz. Grafning tashkil etuvchilarini ko’rsatish mumkin bo’lmasa, uholda uni lotin alifbosining bitta harfi bilanbelgilaymiz.Graf berilgan bo’lsin. to’plamning o’zigaesa graf uchlari to’plami uchlari deyiladi.
Graflar nazariyasida“uch” o’rniga ba’zida tugun yoki nuqta iborasi ham ishlatiladi.
grafning ta’rifiga ko’ra, bo’shkortej bo’lishi ham mumkin. Agar bo’sh bo’lmasa u holda bu kortej ko’rinishdagi juftliklardan tashkil topadi, bunda bo’lishi hamda ixtiyoriy juftlik kortejda istalgancha marta qatnashishi mumkin.
Agar juftlik uchun uni tashkil etuvchilarning joylashuv o’rni ahamiyatsiz bo’lsa, ya’ni bo’lsa juftlikka yo’naltirilmagan qirra yoki qisqacha qirra deyiladi. Agar butartib muhim bo’lsa , ya’ni bo’lsa juftlikga yoy yoki yo’naltirilgan qirra deyiladi.
kortejning tarkibiga qarab, uni yo grafning qirralari korteji yo yoylari korteji , yoki qirralari va yoyalari korteji deb ataymiz.
Grafning uchlari va qirralari uningelementlari deyiladi. graf yechimlarining soni ga tengdir, bu yerda grafning uchlari soni va bilan uning qirralari soni belgilangan.
Grafning qirrasi, odatda uni tashkil etuvchi uchlar yordamida yoki yoki ko’rinishda belgilanadi. Boshqa belgilashlar ham ishlatiladi : masalan, yoy uchun yoki, qirra uchun , yoy yoki qirra uchun u ko’rinishda.
va yozuvlar bir biridan farq qiluvchi yoylarni ifodalaydi. Agar yoy ko’rinishda ifodalangan bo’lsa, u holdauning boshlang’ich uchi esa uning oxirga uchi deyiladi. Bundan tashqari, yoy ko’rinishda yozilsa, u holda uchidan chiquvchi va uchga kiruvchi yoy deb aytiladi.
Qirra uchun uning yozuvdagi harflar joylashish tartibi muhim rol o’ynamaydi va va elementlar qirraning uchlari deyiladi.
Agar grafda yo qirra, yo yoy yoki yoy topilsa, u holda
va uchlar tutashtirilgan deyiladi. Agar grafning ikki uchini tutashtiruvchi qirra yoki yoy bor bo’lsa, u holda ular qo’shni uchlar, aks holda qo’shni bo’lmagan uchlar deyiladi.
Grafning ikki uchi qo’shni bo’lsa, ular shu uchlarni tutashtiruvchiqirraga intsident, o’z navbatida, qirra yoki yoy bu uchlarga intsident deyiladi. Grafda qirraumumiy chetga ega bo’lsa, ular qo’shni qirralar deyiladi.
Ba’zan graf undagielementlar soniga qarab, ya’ni uchlar soni va qirralar soni ga qarab belgilanadi va bu holda grafni ni graf deb ataladi.
Agar grafga kartej faqat qirralardan iborat bo’lsa, u holda yo’naltirilmagan va faqat yo’naltirilgan qirralardan tashkil topgan bo’lsa, u holda u yo’naltirilgan qirra deyiladi.Agar grafda orientirlanmagan qirralar ham, orientirlangan qirralari ham bo’lsa, bunga aralash graf deyiladi.
Agar grafgakartej tarkibida to’plamdan olingan takrorlanuvchi elementlarbo’lsa, u holda karrali yoki parallel qirralar deyiladi. Karrali qirralari yoki yoylari bo’lgan grafga multigraf deyiladi.
Umumiy holda uchlar to’plamiva qirralar korteji cheksiz ko’p elementli bo’lishi mumkin. Bundan keyin to’plam va korteji faqat chekli bo’lgan graflarni qaraymiz. Bunday graflar chekli graflar deyiladi.
Hech qanday qirrabilan bog’lamagan uchga yakkalangan uch deyiladi.Faqat yakkalangan uchlardan iborat grafga nol graf yoki bo’sh graf deyiladi.Uchlar soni ga teng bo’sh graf yoki kabi belgilanadi.
Istalgan ikki uchi sirtmoqsiz va karrali qirralarsiz orientirlanmagan grafga to’la graf deyiladi.Uchlar son ga teng bo’lgan to’la graf grafning qirralar soni ga tengbo’ladi.
Agar grafning uchlariga qandaydir belgilar , masalan,sonlari mos qo’yilgan bo’lsa, unga belgilangan graf deyiladi.
Agar vagraflarning uchlari to’plamlari, ya’ni va to’plamlar asosida uchlarning qo’shnilik munosabatini saqlaydigan o’zaro bir qiymatli moslik o’rnatish mumkin bo’lsa, u holda va graflar izomorf graflar deyiladi. Bu ta’rifni quyidagicha ifodalash mumkin: agar ixtiyoriy uchun bo’lsa u holda
vagraflarizomorfdir. Agar ixomorf graflardan biri orientirlangan bo’lsa, u holda ikkinchisi ham albatta orientirlangan bo’lishi va ulardagi mos yoylarning yo’nalishlari ham bir biriga mos bo’lishi shart.
Graf uchiga intsident qirralar soni shu uchning lokal darajasi yoki qisqacha darajasi deyiladi. Grafdagi uchning darajaini bilan belgilaymiz.
Agar grafning barcha uchlari bir xil darajaga ega bo’lsa, u holda bunday grafdarajali regulyar graf deyiladi. Uch darajali regulyar grafga kubik grafdeyiladi.graf nolinchi darajali regulyar graf deyiladi.
esadarajali regulyar graf bo’ladi.
|
