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



Yüklə 158,64 Kb.
səhifə4/8
tarix07.01.2024
ölçüsü158,64 Kb.
#209843
1   2   3   4   5   6   7   8
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:




, , , , ,




, , , .





Yüklə 158,64 Kb.

Dostları ilə paylaş:
1   2   3   4   5   6   7   8




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin