Graflar nazariyasi haqida umumiy masha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg koyilishi va yechilishi graflar nazariyasining

Agar ikki bolaklariga tegishli istalgan ikkita uchi qolsa, u holda bu graf tolakli graf deb ataladi. Tolakli grafni bilan belgilaymiz, bu yerda va bilan grafning bolishi ravshan, bu yerda uning qirralari soni.

Grafning ikki bolishi haqidagi bashimcha malakli graf tushunchasini ham kiritish mumkin.



1- misol. Oplamini bilan, bu shaharlar orasida belgilangan vaqt mobaynida amalga oshirilayotgan samolyotlarning uchib qonish hodisalari mos keladi. Tabiiyki, grafda karrali yoylar bora, samolyot uchgan aeroportga qaytib qo



2- misol. Qadimgi boshqotirma masalalar qatoriga kiruvchi quyidagi masalani qaraymiz. Biror idishdagi hajmi 8 birlik suyuqlikni faqat oling³. 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 kozgaruvchilar butun qiymatlar qabul qilgan holda , va shartlarni qanoatlantirishlari kerak. Bu shartlarni qanoatlantiruvchi holatlar quyidagilardir:



, , , , , , , , , , , , , , , , , , , , , , , .

Holatlar totishi mumkin. Tatish imkoniyati mavjud botishlari tolgan juftlikni graf deb qarash mumkin. Bu grafning uchlari sistema holatlariga, yoylari (qirralari) esa, bevosita olsin. Bunday ketma-ketliklardan biri quyida keltirilgan:



, , , , ,



, , , .