6-Mavzu: graflar nazariyasi mavzusiga oid matn Reja: 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? 
1.6.3-masala. L. Eylerning ko’rishishlar haqidagi lemmasining qo’llanilishiga 
doir amaliy misol keltiring? 
1.6.4-masala. Yo’lovchi daryodan bo’ri, qo’y va bir bog’ pichanni olib o’tishi 
kerak, lekin u qayiqdan o’zi bilan ularning faqat bittasini olib yurish imkoniyatiga 
ega. Yo’lovchi bu narsalarni sohilning bir qismidan ikkinchi qismiga ularni bus 
butun olib otishi grafini tuzing va elementlarini tahlil qiling? Tuzilgan graf 
yordamida masalani hal qiling? 

---

 1.6.5-masala. Quyidagi graflarda uchlari soni hamda har bir uchdagi qirralari 
sonini aniqlang? 
1-shakl 
1.6.6-masala U- bu sonlar orasidagi bo’luvchi bo’lishlik holatiga mos kortejlar 
deb belgilang. Ushbu G=(V,U) grafga mos kortejlarni tuzing? Bu graf orggraf 
bo’ladimi? Fikringizni asoslang? 
1.6.7-masala. Quyidagi chizmalarda Platon jismlaridan tetraedr, kub
2-shakl 
Grafga misol bo’ladi. Ularning uchlarining lokal darajasini aniqlang hamda 
qaysilari kubik graf bolishini ko’rsating.
 1.6. 8-masala. Uch uy va uch quduq haqida qadimiy boshqotirma masala. 
Tepalikda ketma-ket joylashgan uchta uy
hamda pastlikda
shunday uchta quduq
bor. Har bir uydan har bir quduqqa ixtiyoriy 
ikkitasi kesishmaydigan qilib uzluksiz yo’lakchalar o’tkazish mumkinmi? Masala 
shartini qanoatlantiradigan grafni chizishga harakat qiling va xulosa fikringizni 
bayon qiling? 
1.6.9-masala. Uchlari soni 5 ta, qirralari 7 ta bo’lgan oriyentirlanmagan graf 
chizing. Chizgan grafingizda qo’shni uchlarnini aniqlang hamda ularga insident 
qirralarni yozing.

---

1.6.10-masala. 12 birlik idishdagi suyuqlikni shu idish 
a
8 va 5 litrli idish 
yordamida teng ikki qismga ajrating? Bu masalani hal qilish maqsadida graf tuzib 
uning elementlarini tahlil qiling. Tuzilgan graf yordamida masalani hal qiling?