Diskret matematika va matematik mantiq

21. Bir kishida 7 ta matematika kitobi, ikkinchisida 9 ta kitob bor. Ular birining
kitobini boshqasining kitobiga necha xil usulda almashtirishlari mumkin?
Birinchi shaxsning matematik kitoblar to‘plamini A to‘plami va ikkinchi shaxsning matematika kitoblari to‘plamini B to‘plami deb ataymiz.
Muammolar bayoniga ko‘ra, A da 7 ta kitob, B da 9 ta kitob mavjud. Ular ikkita kitobni necha usul bilan almashishlari mumkinligini bilish uchun biz kombinatsiyalar formulasidan foydalanishimiz kerak:
C(n,r) = n!/r!(n-r)!
Bu erda n - to'plamdagi kitoblarning umumiy soni va r - almashtiriladigan kitoblar soni (bu holda, 2).
A shaxsi uchun tanlash uchun 7 ta kitob bor, shuning uchun n = 7. B shaxsiga berish uchun biz A kitobidan 2 ta kitobni tanlamoqchimiz, shuning uchun r = 2. Bu raqamlarni formulaga ulab, biz quyidagilarni olamiz:
C(7,2) = 7!/2!(7-2)! = 21
Shunday qilib, A odam B shaxsiga 21 xil usulda ikkita kitob berishi mumkin.
Xuddi shunday, B shaxsida tanlash uchun 9 ta kitob bor, shuning uchun n = 9. A odamga berish uchun B dan 2 ta kitobni tanlamoqchimiz, shuning uchun r = 2. Bu raqamlarni formulaga ulab, biz quyidagilarni olamiz:
C(9,2) = 9!/2!(9-2)! = 36
Shunday qilib, B odam A odamga 36 xil usulda ikkita kitob berishi mumkin.
Shuning uchun, jami, ular ikkita kitobni 21 x 36 = 756 xil usulda almashishlari mumkin.
Graflar nazariyasi
Graflar nazariyasi haqida umumiy ma’lumotlar. 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 yeti ko‘prikning joylashuvi 1-shakldagi qadimiy xaritada tasvirlangan
Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida
qo‘llaniladi. Ulardan ba’zilari quyidagilardir. boshqotirmalami 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 hokazo.
Grafning abstract ta’rifi va unga bog'liq boshlang‘ich tushunchalar. Avvalo, grafning abstrakt matematik tushuncha sifatidagi ta’rifini va boshqa ba’zi sodda tushunchalarni keltiramiz. V qandaydir bo‘shmas to‘plam bo‘lsin. Uning v₁є V va v₂є V elementlaridan tuzilgan 1,v₂> ko‘rinishdagi barcha juftliklar (kortejlar) to‘plamini ( V to‘plamning o‘z-o‘ziga Dekart ko‘paytmasini) VxV bilan belgilaymiz.
Graf deb shunday < V, U> juftlikka aytiladiki, bu yerda V≠ø va U — 1 v₂> (v₁є V, v₂є V) ko‘rinishdagi juftliklar korteji bo‘lib, VxV to‘plamning elementlaridan tuzilgandir.
G=(V, U) graf berilgan bo‘lsin. V to‘plamning elementlariga G grafning uchlari, V to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi.
Graflar nazariyasida «uch» iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi ham qo‘llaniladi. Umuman olganda, hanuzgacha graflar nazariyasining ba’zi iboralari bo‘yicha umumiy kelishuv qaror topmagan. Shuning uchun, bundan keyingi ta’riflarda, imkoniyat boricha, muqobil (alternativ) iboralarni ham keltirishga
harakat qilamiz.
G = ( V, U) grafning ta ’riflga ko‘ra, U bo‘sh kortej bo‘lishi ham mumkin. Agar U bo‘sh bo‘lmasa, u holda bu kortej (a,b ) ( a є V, b є V) ko‘rinishdagi juftliklardan tashkil topadi, bunda a=b bo‘lishi hamda ixtiyoriy (a,b) juftlik U kortejda istalgancha marta qatnashishi mumkin.
1. Simmetriyali bo’lgan Q qo’shnilik matrisasi berilgan. Tekislikda G = (V, E) multigrafni chizing va uning insidentlik matrisasini tuzing.



2. Yo’naltirilmagan graf berilgan. Tugunlar raqamlansin. Grafning qo’shnilik va insidentlik matritsasi tuzilsin.