1. Graflar nazariyasining boshlang’ich ma’lumotlari Graflar ustida amallar

 Yozma mashq 

    1.6.1-masala.   

Biron  idishdagi  8  litr  suyuqlikni  shu  idish  va  5  litrli  hamda  3 

litrli idishdan foydalanib teng ikki qismga bo’ling? 

---

Yechish: 

Idishlarning hajmlarini a,b,c bilan belgilaymiz. Bunda a,b,c o’zgaruvchilar butun 

qiymatlar qabul qilgan holda 0



a



8,  0



b



5.  0



c



3  shartlarni qanoatlantirishlari 

kerak. Bu shartlarni qanoatlantiruvchi holatlar quyidagicha: 

(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,  sistemaning  bir  holatdan  boshqa  holatga  bevosita 

o’tishlar to’plamini U bilan belgilaymiz. Natijada hosil bo’lgan (V,U) juftlikni graf 

deb  atash  mumkin.  Bu  grafning  uchlari  sistema  holatlariga,  qirralari(yoylari)  esa, 

bevosita o’tishlarga mos keladi.  

       Berilgan  masalani  hal  qilish  uchun  (V,U)  grafning  qirralari(yoylari)dan 

tashkil  topgan  shunday  ketma-ketlik  tuzish  kerakki  bu  ketma-ketlikning  birinchi 

hadi (8,0,0),   oxirgi hadi (4,4,0) bo’lsin. Bunday ketma-ketliklardan biri quyi dagi 

cha: 

(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)  

  javob: 8 marta quyishdan keyin teng 2 ga bo’lishga erishildi. 

1.6.2-masala.

    G=(V,U)  grafda  V-Aeroportlar  to’plami,  U-  Samalyotlarning 

uchib  qo’nish  hodisalari  korteji  deb  belgilang  va  sirtmoqlari  bo’ladigan  grafga 

misol keltiring?