2. Mantiqiy masalalarni yechishning asosiy usullari

3-masala. O`n beshta o`rtoq uchrashib qolib, qo`l berib so`rasha boshlashdi. Ixtiyoriy vaqtda bir xil sonda qol berib ko `rishgan ikkita o`rtoq topilishini isbotlang.
Isboti: O`rtoqlarning ko`rishishlari soni to`plami (0,1,…,13) yoki (1,2,..,14)
bo`lishi mumkin. Ikkala holda ham 14 ta elementdan tuzilgan to`plam. Ko`rishishlar 14 ta, o`rtoqlar esa 15 ta. Ko’rishishlarni “quti”, o`rtoqlarni “predmetlar” desak, Dirixle prinsipiga ko’ra 2 ta bir xil sonda qol berib ko`rishgan o`rtoqlar topiladi.
Mustaqil yechish uchun masalalar.

• 10 ta odam aylana stol atrofida o`tirishibdi. Ularning yarmidan ko`pi erkak kishilardir. Kamida ikkita erkak qarama-qarshi o`tirganligini isbotlang.
• Matematiklar davlatida 15 ta shahar bor. Ulardan ba’zilari yo’llar bilan tutashtirilgan. Qandaydir ikkita shahardan bir xil sondagi yo’llar orqali chiqish mumkinligini isbotlang.
• Maktabda 30 ta sinf va 1000 ta o`quvchi bor. O`quvchilari
• 34 tadan kam bo’lmagan;
• 33 tadan ko’p bo’lmagan sinf topilishini isbotlang.
• Kafeda muzqaymoqning 4 xili sotiladi. 47 kishining har biri bittadan muzqaymoq sotib olidishdi.
• O`n ikkitadan kam bo`lmagan odam bir xil muzqaymoq tanlaganini isbotlang.
• Kafeda muzqaymoqning 4 turi sotiladi. 47 kishining har biri 2 tadan muzqaymoq sotib oldi (bir hil bo’lishi ham mumkin). Bir xildagi xaridni amalga oshirgan to’rt kishi topilishini isbotlang.

5) O’lchamlari 3x3 bo’lgan jadvalning har bir katagiga 1, 2 yoki 3 sonlari yozilgan. Hamma satrlar, hamma ustunlar va katta diagonallardagi sonlarning yig’indisi har xil bo’lishi mumkin-mi?
Graflar nazariyasining asosiy tushunchalari.
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.
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 hokazo.
Graf deb nuqtalar(graf uchlari) va bu nuqtalarni tutashtiruvchi chiziqlar(graf
qirralari)dan iborat geometrik figuraga aytiladi. Bunda uchlar yordamida

qandaydir to`plam elementlari ifodalansa, qirralar orqali elementlar orasidagi bog’liqlik ifoda etiladi.
Graflar yordamida mantiqiy masalalarni yechish mumkin. Buning uchun masala shartidan foydalanib nuqta(graf uchi) va chiziq(graf qirrasi)lardan iborat sxema tuzib olinadi.