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

lishi mumkin (notrivial marshrut);




lmasligi mumkin (nol marshrut yoki trivial marshrut).



Marshrutning uzunligi deb undagi qirralar soniga aytiladi.



Turli qirralardan tashkil topgan marshrutga zanjir deb ataladi. Agar zanjirning chetlaridan tashqari barcha uchlari turlicha bolsa, u yopiq zanjir deb ataladi. Hech bonalgan marshrutdir, bunda 3 ich uch, 4 lib, u zanjir bosha graf uchun zanjirning oxirgi boini sifatida yoki qirralardan qaysisi olinishiga bognalishini (oriyentatsiyasini) inobatga olmasdan oriyentirlanmagan marshrut, zanjir va oddiy zanjir tushunchalarini kiritish mumkin. Lekin, oriyentirlangan graflar uchun oriyentirlangan marshrut tushunchasini kiritish tabiiydir.




Yoylarning oriyentatsiyalari hisobga olingan yoylar va uchlar ketma-ketligi oriyentirlangan marshrut deb ataladi.



Oriyentirlangan marshrut uchun zanjir tushunchasiga ol (yoki oriyentirlangan zanjir) tushunchasini ham kiritish mumkin. Boshlangla olmaydi. Bu ketma-ketlik oriyentirlangan marshrut ham bonalishiga teskari yoldir, lekin u kontur emas. Berilgan grafda faqat bitta kontur borinishda ifodalash mumkin. lmasa, u holda bu graf siklga ega.



Isboti. Agar grafda sirtmoqlar yoki karrali qirralar boi toriligi ravshandir. Shuning uchun teorema tasdiglmagan holda isbotlaymiz.



Faraz qilaylik, berilgan sirtmoqsiz va karrali qirralari bolsin. Qaralayotgan uchga qoshni uchni, uchga esa dan farqli boshqa qoshni uchni, va hakoza, tanlab,








qirralar ketma-ketligini tuzamiz. Teoremaning shartlariga kokidlaymiz.




Grafning uchlari toplam bong albatta oldin uchragan uchlardan birini tanlashga majbur bolsa, ketma-ketlikka qirralar qoxtatamiz, chunki tuzilgan qirralar ketma-ketligining uch ikki marta qatnashgan qismi biz izlayotgan sikldir. lamliligi tushunchasi. Agar oriyentirlanmagan grafda chetlari va uchlardan iborat marshrut topilsa, bu va uchlar bogzi esa va uchlarni boglovchi marshrut biror uchdan bir necha marta orniga marshrutda faqat uch qoldiriladi) yana olovchi oddiy zanjir kolangan uchlar doimo oddiy zanjir bilan ham boladi degan xulosaga kelamiz.