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

quyidagicha aniqlangan (, ) -matritsa grafning qirralari qolib, uning qirralari qorinishga egadir.






Ravshanki, sirtmoqsiz va karrali qirralarsiz graf qirralari qolgan belgilangan graf berilgan borinishda aniqlangan (, ) matritsa grafning insidentlik matritsasi deb ataladi.






5- misol. 1- shaklda tasvirlangan grafning insidentlik matritsasi quyidagicha bolgan belgilangan sirtmoqsiz orgrafni qaraymiz. Elementlari








koladi:



.



Marshrutlar va zanjirlar haqida umumiy maplami va qirralar korteji bolsin. Bu grafdagi uchlar va qirralarning har ikki qorinishdagi chekli yoki cheksiz ketma-ketligi marshrut deb ataladi. Marshrutni uning uchlari ketma-ketligi yoki qirralari ketma-ketligi kolmasa, bu uchni marshrutning boshlanglmaganda esa, uni marshrutning oxirgi uchi deb ataydilar.



Agar marshrutning boshlanglsa, u holda uni uchdan uchga yolgan marshrut deb ataladi.




Marshrutdagi ikkita qoshni qirralarga tegishli uch ichki uch yoki oraliq uch deb ataladi.



Marshrutda qirralar va uchlar takrorlanishi mumkin bozida, uning boshlanglishi ham mumkin va teskarisi, marshrutning boshlanglishi ham mumkin.




Tabiiyki, marshrut:



ich uchga ham oxirgi uchga ham ega bo boshlangich uchga ega bolmasligi mumkin yoki, aksincha, oxirgi uchga ega bolmasligi mumkin (bir tomonlama cheksiz marshrut);