Iii bob. Graflar nazariyasi

2- 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 , va bilan belgilab, muayyan bir vaqt uchun idishlardagi suyqlikning hajmlari asosida qaralayotgan sistemaning holatini ifodalovchi uchliklarni tuzamiz. Masalaning shartiga ko‘ra , va o‘zgaruvchilar butun qiymatlar qabul qilgan holda , va shartlarni qanoatlantirishlari kerak. Bu shartlarni qanoatlantiruvchi holatlar quyidagilardir:
, , , , , , , , , , , , , , , , , , , , , , , .
Holatlar to‘plamini bilan belgilaymiz. Suyuqlikni (yoki uning bir qismini) idishlarning biridan boshqa birortasiga quyish natijasida sistema bir holatdan boshqa holatga o‘tishi mumkin. Ta’kidlash kerakki, yuqoridagi holatlarning ixtiyoriysidan boshqa birortasiga bevosita yoki bilvosita o‘tish imkoniyati mavjud bo‘lmasligi ham mumkin. Sistemaning bir holatdan boshqa holatga bevosita o‘tishlari to‘plamini bilan belgilaymiz. Natijada hosil bo‘lgan juftlikni graf deb qarash mumkin. Bu grafning uchlari sistema holatlariga, yoylari (qirralari) esa, bevosita o‘tishlarga mos keladi.
Berilgan masalani hal qilish uchun grafning yoylaridan tashkil topgan shunday ketma-ketlik tuzish kerakki, bu ketma-ketlikning birinchi hadi , oxirgi hadi esa bo‘lsin. Bunday ketma-ketliklardan biri quyida keltirilgan:
, , , , ,
, , , . ■


Muammoli topshiriq va masalalar

1. 
   Graf tushunchasini qo‘llash mumkin bo‘lgan amaliy misol keltiring va qaralayotgan grafni tahlil qiling.
   
2. 
   To‘la graf bilan bog‘liq biror misol keltiring.
   
3. 
   Biror idishdagi hajmi 8 birlik suyuqlikni faqat o‘sha idish hamda 5 va 3 birlik hajmga ega idishlar vositasida teng ikki qismga bo‘lish haqidagi boshqotirma masalani hal qilish uchun tuzilgan graf elementlarini tahlil qiling va bu masalaning mumkin qadar qisqa yechimini toping.
   
4. 
   Ko‘rishishlar haqidagi lemmaning qo‘llanilishiga doir amaliy misol keltiring.
   
5. 
   Kubik graf bilan bog‘liq amaliy misollar keltiring.
   
6. 
   Qadimgi boshqotirma masala: biror idishdagi hajmi 12 birlik suyuqlikni faqat o‘sha idish hamda 8 va 5 birlik hajmli idishlar yordamida teng ikki qismga ajrating⁹. Bu boshqotirma masalani hal qilish maqsadida graf tuzib uning elementlarini tahlil qiling. Tuzilgan graf yordamida masalani hal qiling.
   
7. 
   Qadimgi boshqotirma masala: yo‘lovchi daryodan bo‘ri, qo‘y va bir bog‘ pichanni olib o’tishi kerak, lekin u qayiqda o‘zi bilan faqat bitta narsani olib o‘tish imkoniyatiga ega. Agar sohilda bo‘ri va qo‘y birga qolsa bo‘ri qo‘yni, qo‘y va pichan birga qolganda esa, qo‘y pichanni yeb qo‘yadi. Yo‘lovchi narsalarni daryoning bir sohilidan ikkinchi sohiliga olib o’tishni ularning butunligini saqlagan holda amalga oshirishi kerak. Bu boshqotirma masalani hal qilish maqsadida graf tuzib uning elementlarini tahlil qiling. Tuzilgan graf yordamida masalani hal qiling.
   
8. 
   Barcha belgilangan -graflar sonini aniqlang.
   
9. 
   O‘zaro izomorf bo‘lmagan
   

a) uchta, b) to‘rtta, d) beshta
uchga ega barcha belgilangan graflar uchun to‘plam va kortejlarni aniqlang.

10. 
    Shaxmat o‘yinida shaxmat donalarining taxtada joylashuvi va o‘yin navbati birgalikda vaziyatni tashkil etadi. Barcha vaziyatlar to‘plamini graf uchlari to‘plami deb qarasak, vaziyatlarning biridan boshqasiga mumkin bo‘lgan o‘tishlar (yurishlar) grafning qirralari yoki yoylariga mos keladi deb hisoblash mumkin. Shaxmat o‘yinining qoidalariga rioya qilgan holda yuqorida bayon qilingan grafning shaxmat o‘yinidagi dastlabki vaziyatni ham o‘z ichiga oluvchi qandaydir oltita vaziyatlariga mos uchlari va bu uchlarni bog‘lovchi qirra va yoylarini aniqlang.