Yashiklar prinsipi

Dirixle prinsipi Dirixle prinsipi, "yashiklar prinsipi" — (ya+1) elementdan iborat boʻlgan toʻplam p ta sinfga ajratilganda sinflarning kamida bittasida elementlar soni 2 tadan kam boʻlmaydi, degan tasdiq. P. Dirixle nomi bilan ataladi. D. p., odatda, oʻnta yashikka oʻn bitta quyonni bittadan joylab boʻlmaydi, degan sodda misol bilan tushuntiriladi. Shuning uchun u "yashiklar prinsipi" deb ham ataladi. D. p. sodda ifodalansa ham, sonlar nazariyasi, kombinatorika va mat.ning boshqa boʻlimlarida muhim teoremalarni isbotlashga asos boʻladi. Garmonik funksiyalar nazariyasida ham D. p. deb ataluvchi teorema bor.

Graflar nazariyasining boshlang`ich ma`lumotlari

Reja:

1. 
   Graflar nazariyasi haqida umumiy va ma`lumotlar.
   
2. 
   Grafning abstrakt tarifi va u bilan bog`liqboshlang`ich tushunchalar
   
3. 
   Graflar nazariyasiga oid boshlang`ich misollar.
   

Kalit so`zlar: Graf, uch, qirra, yoy, yo`nalish, orgraf, qo`shni uchlar, yakkalangan uch, karrali qirralar, multigraf, psevdograf, nolgraf, to`la, belgilangan va izomorf garflar, garfning geometric ifodalanishi, uchlar, qirralar va yoylarinsidentligi.

1. Graflar nazariyasi haqida umumiy ma`lumotlar.
1736 yilda L. Eyler tomonidan o`sha davrda qiziqarli amaliy masalalardan birihisoblangan Kyonigsberg ko`priklari haqidagi masalaning qo`yilishiva yechilishi graflar nazariyasining paydo bo`lishiga asos bo`ldi.
Kyonigsberg shaxridagi Pregel daryosi ustida qurilganyettita ko`priklar joylashuvi 1- shakladagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqamlar bilan belgilangan. Pregel daryosi Kyonigsberg shaxrini o`sha davrda 4 ta , , va qismlarga bo`lgan. Shaharning ixtiyoriy qismida joylashgan uydan chiqib 7ta ko`priklardan faqat bir martadan o`tib, yana o`sha uyga qaytib kelish mumkinmi? Kyonigsbergko`priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut mavjudligi shartlari ham topildi. L. Eylerning bu maqolasi yuz yildan ko`p vaqt mobaynida graflar nazariyasi bo`yicha yagona ilmiy ish bo`lib keldi.
ХИХ asrning o`rtalarida graflar nazariyasi bilan bog`liq tatqiqotlar G. Kirxgof va A. Keli ishlarida paydo bo`ldi.
“Graf” iborasi D. Kyonig tomonidan 1936 yilda graflar nazariyasigabag`ishlangan dastlabki darslikda uchraydi.
Graflar nazariyasi bo`yicha tadqiqotlar natijalari insonназарияси бўйича тадқиқотлар натижалари инсон фаолиятининг турли соҳаларида қўлланилади. Улардан баъзилари қуйидагилардир: бошқотирмаларни ҳал қилиш; қизиқарли ўйинлар; йўллар, электр занжирлари, интеграл схемалари ва бошқариш системаларини лойиҳалаштириш; автоматлар, блок-схемалар ва компъютер учун программаларни тадқиқ қилиш ва ҳоказо.