Nukus innovatsion instituti

O’ZBEKISTON RESPUBLIKASI OLIY TA’LIM, FAN VA INNOVATSIYALAR VAZIRLIGI NUKUS INNOVATSION INSTITUTI IT DASTURIY INJINERING fakulteti sirtqi bo’limi ___________________________________________fanidan MUSTAQIL ISH MAVZU: _______________________________________ _______________________________________ Bajargan:_____________________________________________ Qabul qilgan:__________________________________________ Gurux raqami «___»

R E J A:

1. 
   Graf nazariyasi.
   
2. 
   Graf nazariyasining paydo bo’lishi.
   
3. 
   Deduksiya teoremasi natijalari.
   
4. 
   Grafning abstrakt ta’rifi va u bilan bog‘liq boshlang‘ich tushunchalar.
   

Graflar nazariyasining asosiy masalasi berilgan nuqtalar va ularni tutashtiruvchi chiziqlarning xossalaridan tashkil topadi. Bunday talqinda chiziqlarnig to’g’ri chiziq yoki kesma, yoylardan yoki egri chiziqlardan iborat bo’lishi hamda bu chiziqlar qaerda joylashishi, uzun yoki qisqa bo’lishi muhim emas. Shunisi muhimki bu chiziqlar berilgan ikki nuqtani tutashtiradi.

1736 – yilda L.Eyler tomonidan o’sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonisberg ko’priklari haqidagi masalaning qo’yilishi va echilishi graflar nazariyasining paydo bo’lishiga asos bo’ldi.
Kyonisberg shaxridagi Pregel daryosi ustiga qurilgan ettita ko’prik o’sha vaqtda shaxarni to’rtta qismga ajratgan. Shaxarning ixtiyoriy qismida joylashgan uydan chiqib ettita ko’rikdan faqat bir martadan o’tib, yana o’sha uyga qaytib kelish mumkinmi? Kyonisberg ko’priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut Eyler tsikli nomi bilan yuritiladi) mavjudligi shartlari ham topildi. L.Eyler tomonidan e’lon qilingan tarixiy ilmiy ish yuz yildan kshproq vaqt mobaynida graflar nazariyasi bo’yicha yagona ilmiy ish bo’lib keldi.
XIX asrning o’rtalarida graflar nazariyasi bilan bog’liq tadqiqotlar G.Kirxgof (1924–1887, olmon fizigi) va A.Keli (1821–1895, ingliz matematigi) ishlaarida paydo bo’ldi.
“Graf” iborasi D.Kyonig (1884–1944, venger matematigi) tomonidan 1936– yilda graflar nazariyasiga bag’ishlangan dastlabki darsliklarda uchraydi.
Graflar nazariyasi bo’yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo’llaniladi. Ulardan ba’zilari quyidagilar: boshqotirmalarni hal qilish; qiziqarli o’yinlar; yo’llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirishva hakazo.
Avvalo grafning abstrakt matematik tushuncha sifatidagi ta’rifini keltiramiz. Ixtiyoriy nuqtalarning qandaydir usulda bog’lanishidan tashkil topgan to’plamni qaraymiz. Ushbu to’plamni uchlar to’plami va uning elementlarini esa uchlar deb ataymiz. to’plamning va elementlaridan tuzilgan ko’rinishidagi barcha juftliklar to’plamini (to’plamning o’z-o’ziga Dekrat ko’paytmasini) deb belgilaymiz.
Graf deb shunday juftlikga aytiladiki, bu erda va ko’rinishidagi juftliklar bo’lib, to’plamning elementlaridan tuzilgandir.
Grafni lotin alifbosining harfi bilan belgilaymiz.
Grafga ta’rif berishda boshqacha yondoshuvdan ham foydalanish mumkin. Graf deb bir qancha uchlar to’plamining birlashmasiga yoki qaysi uchlar bog’langanligini ko’rsatuvchi juftliklarga aytiladi. Mos ravishda grafning geometrik tasvirida aniq har bir juftlik grafning qirrasi deyiladi, va uchlar esa qirraning oxirlari deyiladi. Qirraning ta’rifida uning oxirgi ikki uchining joylashish tartibi e’toborga olinishi ham, olinmasligi ham mumkin. Agar bunday tartib mavjud bo’lmasa, ya’ni deyish mumkin bo’lsa, u holda ni yo’naltirilmagan qirra deb ataladi. Agar bunday tartib mavjud bo’lsa, u holda qirra yo’naltirilgan qirra deyiladi. Yo’naltirilgan qirrada boshlang’ich uch, oxirgi uch deb hisoblanadi. Shuningdek qirrani uchdan chiquvchi va uchga boruvchi qirra deyiladi. Qirra yo’naltirilgan bo’lgan holda ham, yo’naltirilmagan holda ham qirra va uchlarga intsidient deb ataladi.
Ham yo’naltirilgan, ham yo’naltirilmagan qirralarga ega bo’lgan graf aralash graf deyiladi. Misol sifatida, shaxarning xaritasini graf sifatida olsak, unda ko’chalarni qirra deb, chorrahalarni esa uchlar sifatida olish mumkin. Bunda faqat bir tomonlama harakat mavjud ko’chalarni yo’nalishga ega qirra deb olsak, u holda ikki tomonlama harakat mavjud ko’chalarni hech qanday yo’nalish orqali belgilab bo’lmaydi.
Hech bir qirraga intsidient bo’lmagan uch yakkalangan uch deyiladi. Agar grafning ikkita uchini tutashtiruvchi qirra bor bo’lsa, u holda bunday uchlar qo’shni uchlar deyiladi, aks holda esa qo’shni bo’lmagan uchlar deyiladi.
Faqat yakkalangan uchlardan tashkil topgan grafni nol graf deyiladi va orqali belgilanadi.
Ikkita chetki ya’ni boshlang’ich va oxirgi qirralari ustma-ust tushga qirra sirtmoq deyiladi va uni kabi yoziladi.
Agar grafning ikiita uchi o’zaro bir necha qirralar orqali tutashgan bo’lsa bunday qirralarni parallel yoki karrali qirralar deyiladi.
Bunda agar graf yo’naltirilgan bo’lsa, hr bir qirra uchun yo’nalish aniqlanadi. Misol sifatida, jamoaviy musobaqani olish mumkin. Bunda jamoalar mos ravishda grafning uchlari hisoblanadi. Ikkita va jamoalar har safar bir-biri bilan o’ynaganda ular qirra orqali tutashtiriladi. Agar jamoa ni yutsa u holda yo’nalish dan tomon yoki, aksincha yo’naltiriladi. Durang natija esa yo’naltirilmagan qirrani ifodalaydi.
1736 yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi.
Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko‘priklar joylashuvi 1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqamlar bilan belgilangan. Pregel daryosi Kyonigsberg shahrini o‘sha davrda to‘rtta , , va qismlarga bo‘lgan. Shaharning ixtiyoriy qismida joylashgan uydan chiqib yettita ko‘priklardan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish mumkinmi? Kyonigsberg ko‘priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut Eyler sikli nomi bilan yuritiladi, mavjudligi shartlari ham topildi. Bu natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan. L. Eylerning bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo‘yicha yagona ilmiy ish bo‘lib keldi.
XIX asrning o‘rtalarida graflar nazariyasi bilan bog‘liq tadqiqotlar G. Kirxgof va A. Keli ishlarida paydo bo‘ldi.
“Graf” iborasi D. Kyonig tomonidan 1936 yilda graflar nazariyasiga bag‘ishlangan dastlabki darslikda uchraydi.
Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo‘llaniladi. Ulardan ba’zilari quyidagilardir: boshqotirmalarni hal qilish;
qiziqarli o‘yinlar; yo‘llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, blok-sxemalar va komp’yuter uchun programmalarni tadqiq qilish va hokazo.