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



Yüklə 158,64 Kb.
səhifə5/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

Graflarning berilish usullari

1- misol. 1- shaklda tasvirlangan grafni deb belgilaymiz. Berilgan graf belgilangan graf bonalish kolgani uchun oriyentirlanmagan grafdir. Grafning qirralaridan biri, aniqrogshni, 1 va 4 uchlar esa qoshni qirralardir, chunki ular umumiy uchga (3 uch) ega, va qirralar esa qorinishda bon bitta element bor: 5ta uch va 6ta yoy, yaq. Bu grafning yoyi uchun 1 boshlangshnilik matritsalari.


Endi grafning boshqa bir berilish usuli negizida yotuvchi graf uchlari qo uchlari soni ga teng bolsin.


Elementlari








koshniligi matritsasi deb ataymiz.






Bu talmagan graf uchlari qolishi, satrlaridagi birlar soni esa mos uchlarning darajalariga tengligi kelib chiqadi.




1- misol. 1- shaklda tasvirlangan grafgning uchlari qorinishda bolgan belgilangan oriyentirlangan grafning uchlari qorinishda aniqlangan (, ) matritsaga aytiladi.






2- misol. 2- shaklda tasvirlangan orgrafning uchlari qoladi:




.


Endi uchlari bolsin. elementlari grafning va uchlarini tutashtiruvchi qirralar soniga teng boshniligi matritsasi
deb ataladi.




3- misol. 1- shaklda tasvirlangan oriyentirlanmagan multigraf uchlari qoladi:




.


Karrali yoylari boshniligi matritsasi
tushunchasini ham yuqoridagiga oriflash mumkin.




Shunday qilib, manfiymas butun sonlardan tashkil topgan va graf uchun uchlari qolgan kvadrat matritsa bilan graf orasida bir qiymatli moslik (izomorflik aniqligida) bor degan xulosa va, bundan, graflar nazariyasi bolmagan graf uchun elementlari


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