Diskret matematika va matematik mantiq
Bir kishida 7 ta matematika kitobi, ikkinchisida 9 ta kitob bor. Ular birining
Download 284.11 Kb.
|
Dis mat Ilmira
- Bu sahifa navigatsiya:
- Graflar nazariyasi
- 1. Simmetriyali bo’lgan Q qo’shnilik matrisasi berilgan. Tekislikda G = (V, E) multigrafni chizing va uning insidentlik matrisasini tuzing.
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 v1є V va v2є V elementlaridan tuzilgan Graf deb shunday < V, U> juftlikka aytiladiki, bu yerda V≠ø va U — 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. Download 284.11 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling