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

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