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 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 kompyuter uchun programmalarni tadqiq qilish va xokazo.