2. Mantiqiy masalalarni yechishning asosiy usullari

1 - l e m m a (“ko‘rishishlar” haqida). Ixtiyoriy orientirlanmagan grafda barcha uchlar darajalari yig‘indisi qirralar sonining ikki baravariga teng.
Graflarga misollar.

• misol. O‘zbekiston Respublikasi hududidagi aeroportlar to‘plamini V bilan, bu shaharlar orasida belgilangan vaqt mobaynida amalga oshirilayotgan

samolyotlarning uchib qo‘nish hodisalari kortejini U bilan belgilaymiz. U holda (V,U) juftlikni graf deb qarash mumkin. Bu yerda grafning uchlariga
aeroportlar, yoylariga esa samolyotlarning uchib qo‘nish hodisalari mos keladi. Tabiiyki, (V,U) grafda karrali yoylar bo‘lishi mumkin, agar, qandaydir sababga
ko‘ra, samolyot uchgan aeroportga qaytib qo‘nsa, u holda bu hodisaga qaralayotgan grafdagi sirtmoq mos keladi.

• misol. Qadimgi boshqotirma masalalar qatoriga kiruvchi quyidagi masalani qaraymiz. Biror idishdagi hajmi 8 birlik suyuqlikni faqat o‘sha idish hamda 5 va 3 birlik hajmli idishlar vositasida teng ikki qismga bo‘ling. 8, 5 va 3 birlik hajmli idishlardagi suyuqlik hajmini mos ravishda a , b va c bilan belgilab, muayyan bir vaqt uchun idishlardagi suyqlikning hajmlari asosida qaralayotgan

sistemaning holatini ifodalovchi  a,b, c  uchliklarni tuzamiz. Masalaning shartiga ko‘ra a , b va c o‘zgaruvchilar butun qiymatlar qabul qilgan holda
0  a  8 , 0  b  5 va 0  c  3 shartlarni qanoatlantirishlari kerak. Bu shartlarni qanoatlantiruvchi holatlar quyidagilardir:
 8,0,0  ,  5,0,3  ,  5,3,0  ,  2,3,3  ,  2,5,1  ,

 7,0,1  ,  7,1,0  ,  4,1,3  ,  4,4,0  .
Mustaqil yechish uchun masalalar.

• Qishloqda 9 ta uy bor. Farmon - Ilyos va Omonning qo'shnisi, Mirshod - Ilyos va Sanjarning qo'shnisi, Vali - Dilshod va Naimning qo'shnisi, Elyor - Naimning qo'shnisi ekanligi aniq va boshqa qo'shnilar mavjud bo'lmasa, Farmon kechasi o'zining bog'i orqali o'tib, Naimlarnikidan olma olishi mumkinmi?
• A shahardan B shaharga 3 ta yo’l, B shahardan C shaharga esa 4 ta yo’l orqali

borsa bo’ladi. A shahardan B shahar orqali o’tib C shaharga boradigan nechta yo`l mavjud?
3) Bir kuni dam olish vaqtida Moskva, Sank-Peterburg, Novgorod, Perm va
Tomsk shaharlaridan beshta bola Yura, Tolya, Alyosha, Kolya va Vityalar aylana stol bo’ylab o’tirishdi. Moskvalik Tomsklik va Vitya o'rtasida, Sankt- Peterburglik Yura va Tolya o'rtasida, Permlik esa Alyoshaning qarshisida o'tirdi. Kolya hech qachon Sankt-Peterburgda bo'lmagan va Yura hech qachon Moskva yoki Tomskda bo'lmagan, ammo Tomskda yashovchi va Tolya muntazam ravishda xat yozishadi. Yigitlarning har biri qaysi shaharda yashashini aniqlang.
Javob: Tolya Moskvada, Vitya Sankt-Peterburgda, Yura Novgorodda, Kolya Permda, Alyosha Tomskda yashaydi.

• Regionda 5 ta shahar bor. Bu shaharlarni bir-biri bilan har biridan
• 4 tadan ; b) 3 tadan yo’l chiqadigan qilib bog’lash mumkinmi?
• Kompaniyada jami 16 ta odam ishlaydi. Kompaniyadagi har bir odam shu

kompaniyadagi 6 ta odam bilan do’st bo’lishi mumkinmi?

• Regionda 7 ta A,B,C,D,M,N,K shaharlar bor. A va D, B va K, M va C, N va B, D va M, C va D, K va N, M va A shaharlar orasida avtobus marshrutlari yo’lga qo’yilgan. Yuqoridagi marshrutlardan foydalanib M shahardan B shaharga borish mumkinmi?
• Mamlakatda 100 ta shahar bor. Har bir shahardan 10 ta yo’l chiqadi. Mamlakatda jami nechta yo’l bor?
• Mamlakatning har bir shahridan 6 ta yo’l chiqadi. Bu mamlakatda jami 50 ta shahar bo’lishi mumkinmi?
• Uchlarining darajalari 4,4,4,4,2 bo’lgan 5 ta uchli graf mavjudmi?
• Yetti uchli grafning oltita uchi darajasi 6 ga teng. Yettinchi uchining darajasini toping.

10)
11 ta kesmani har biri boshqa 5 tasi bilan kesishadigan qilib chizish
mumkinmi?
11) Jadvalda satr va ustun kesishgan katakda yuk tashish narxi yozilgan. Agar katak bo’sh bo’lsa demak ular qo’shni emas. A dan B ga boradigan eng arzon marshrutni toping.