Graflar nazariyasining elementlari

Graflar nazariyasining elementlari Reja: Graflar xaqida tushuncha va uning ta'rifi. Graflar va ularning turlari. 1- m i sol . 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. 2- m i s o l . 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 boling1. 8, 5 va 3 birlik hajmli idishlardagi suyuqlik hajmini mos ravishda a , b va с bilan belgilab, muayyan bir vaqt uchun idishlardagi suyqlikning hajmlari asosida qaralayotgan sistemaning holatini ifodalovchi a , b , c uchliklami tuzamiz. Masalaning shartiga ko'ra a, b va с o'zgaruvchilar butun qiymatlar qabul qilgan holda 0 cr 8, 0 6 5 , 0 с 3 va a + b + c = 8 shartlarni qanoatlantirishlari kerak. Bu shartlami qanoatlantiruvchi barcha holatlar (uchliklar) quyidagilardir: 8,0,0 , 7,1,0 , 7,0,1 , 6,2,0 , 6,1,1 , 6,0,2 , 5,3,0 , 5,2,1 , 5,1,2 , 5,0,3 , 4,4,0 , 4,3,1 , 4,2,2 , 4,1,3 , 3,5,0 , 3,4,1 , 3,3,2 , 3,2,3 , 2,5,1 , 2,4,2 , 2,3,3 , 1,5,2 , 1,4,3 , 0,5,3 . Holatlar to'plamini V bilan belgilaymiz. Suyuqlikni (yoki uning bir qismini) idishlaming biridan boshqa birortasiga quyish natijasida sistema bir holatdan boshqa holatga o'tishi mumkin. Ta'kidlash kerakki, yuqoridagi holatlaming ixtiyoriysidan boshqa birortasiga bevosita yoki bilvosita o'tish imkoniyati mavjud bo'lmasligi ham mumkin. Sistemaning bir holatdan boshqa holatga bevosita o'tishlari to'plamini U bilan belgilaymiz. Natijada hosil bo'lgan (V,U) juftlikni graf deb qarash mumkin. Bu grafning uchlari sistema holatlariga, yoylari (qirralari) esa, bevosita o'tishlarga mos keladi. Berilgan masalani hal qilish uchun (V,U) grafning yoylaridan tashkil topgan shunday ketma-ketlik tuzish kerakki, bu ketma-ketlikning birinchi hadi 8,0,0 , oxirgi hadi esa ...