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


Download 216.29 Kb.
bet4/8
Sana21.09.2023
Hajmi216.29 Kb.
#1683718
1   2   3   4   5   6   7   8
Bog'liq
Graflar nazariyasi. Graflar nazariyasiningasosiy tushunchalari. -fayllar.org




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 oling3. 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:




, , , , ,




, , , .





Download 216.29 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling