Graflar ustida amallar. Marshrutlar va zanjirlar

uchga yo‘nalgan marshrut yoki chetlari v_{p va vq} bo‘lgan marshrut deb ataladi.

Marshrutdagi ikkita qo’shni qirralarga tegishli uch ichki uch yoki

oraliq uch deb ataladi.

Marshrutda qirralar va uchlar takrorlanishi mumkin bo‘lgani uchun marshrutning ichki uchi, bir vaqtning o‘zida, uning boshlang‘ich va (yoki) oxirgi uchi bo‘lishi ham mumkin va teskarisi, marshrutning boshlang‘ich va (yoki) oxirgi uchi uning ichki uchi bo‘lishi ham mumkin.

Tabiiyki, marshrut:

• 
  boshlang‘ich uchga ham oxirgi uchga ham ega bo‘lmasligi mumkin (bunday marshrut ikki tomonlama cheksiz marshrut deb ataladi);
  
• 
  boshlangich uchga ega bo‘lib, oxirgi uchga ega bo‘lmasligi mumkin yoki, aksincha, oxirgi uchga ega bo‘lib, boshlangich uchga ega bo‘lmasligi mumkin (bir tomonlama cheksiz marshrut);
  
• 
  yagona qirradan iborat bo‘lishi mumkin (notrivial marshrut);
  
• 
  birorta ham qirraga ega bo‘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 bo‘lsa, u holda uni oddiy zanjir deb ataydilar.
Berilgan (v_{1,v2 ,...,vs )} zanjir yoki oddiy zanjir uchun v_{1  vs} bo‘lsa, u yopiq zanjir deb ataladi. Hech bo‘lmaganda bitta qirraga ega yopiq oddiy zanjir sikl deb ataladi. Sirtmoq yoki bir juft karrali qirralar sikl tashkil etishi ravshandir. Tushunarliki, grafdagi zanjir grafning qism grafi deb qaralishi mumkin.

• 
  misol. 1- shaklda tasvirlangan graf uchun
  

_(3,u_{4 , 2,u1,1,u1, 2,u6 , 2,u4 ,3,u5 , 4)}

3

ketma-ketlik 3 belgili uchdan 4 belgili uchga yo‘nalgan marshrutdir, bunda 3 – boshlang‘ich uch, 4 – oxirgi uchdir. Bu marshrutda 1, 2 va 3 belgili uchlar oraliq uchlar hisoblanadi.

_{1- shakl Qaralayotgan marshrutning uzunligi 6a teng}

bo‘lib, u zanjir bo‘la olmaydi, chunki unda 1

belgili uch 2 marta (bir marta oraliq uch sifatida, ikkinchi marta esa oxirgi uch sifatida) qatnashmoqda.

Yana o‘sha graf uchun (3, 2,1,3) zanjirning oxirgi bo‘g‘ini sifatida
_{u2 yoki u3}




qirralardan qaysisi olinishiga bog‘liqsiz ravishda, u yopiq
zanjir va sikldir. ■
Oriyentirlangan graflar uchun ham undagi yoylarning yo‘nalishini (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 o‘xshash yo‘l (yoki oriyentirlangan zanjir) tushunchasini ham kiritish mumkin. Boshlang‘ich va oxirgi uchlari ustma- ust tushadigan oriyentirlangan zanjir kontur deb ataladi.

• 
  misol. 2- shaklda tasvirlangan grafni qaraymiz. Uning uch va qirralaridan tuzilgan
  

_(3,u<sub>3 ,1,u4 , 4,u5 ,5,u2 , 2,u1,1)

ketma-ketlik</sub> oriyentirlanmagan marshrut va zanjirdir, lekin u oddiy zanjir bo‘la olmaydi. Bu ketma-ketlik oriyentirlangan marshrut ham bo‘la olmaydi, chunki unda marshrut yo‘nalishiga teskari yo‘nalishga ega yoylar bor (u_{3 ,u4 ,u1).}
Qaralayotgan graf uchun




₍u_{6 ,u5 ,u2 )}




ketma-ketlik oriyentirlangan
marshrutni tashkil etadi. Bu marshrut yo‘ldir, lekin u kontur emas.
Berilgan grafda faqat bitta kontur bo‘lib, bu konturni




(4,u₅,5,u₆, 4)




yoki
(5,u₆ , 4,u₅,5) ko‘rinishda ifodalash mumkin. ■

• 
  teorema. Agar grafdagi har bir uchning lokal darajasi ikkidan kichik bo‘lmasa, u holda bu graf siklga ega.
  

Isboti. Agar grafda sirtmoqlar yoki karrali qirralar bo‘lsa, teoremaning tasdig‘i to‘g‘riligi ravshandir. Shuning uchun teorema tasdig‘ini graf sirtmoqsiz va karrali qirralari bo‘lmagan holda isbotlaymiz.

Faraz qilaylik, v V berilgan sirtmoqsiz va karrali qirralari
bo‘lmagan




G  (V ,U )




grafning ixtiyoriy uchi bo‘lsin. Qaralayotgan v
uchga qo‘shni v₁ uchni va bu uchga v dan farqli boshqa qo‘shni v₂
uchni, v₂




uchga esa




<sub>v1 dan farqli boshqa qo‘shni v3




uchni,</sub> va hakoza, v_i
uchga




_{vi1dan farqli boshqa qo‘shni}




^vi1




uchni, va hakoza, tanlab,
₍₍v,v_{1 ),(v1,v2 ),(v2 ,v3 ),...,(vi1,vi ),(vi ,vi1),...)}

qirralar ketma-ketligini tuzamiz. Teoremaning shartlariga ko‘ra
yuqoridagi jarayonni amalga oshirish va talab etilgan xossaga ega uchni topish mumkinligini ta’kidlaymiz.




^vi1
Grafning uchlari to‘plami V chekli to‘plam bo‘lganligidan, yuqorida bayon etilgan uchlar ketma-ketligini qurish jarayonida chekli qadamdan so‘ng albatta oldin uchragan uchlardan birini tanlashga
_majbur bo‘lamiz. Agar v_k




uch ketma-ketlikda ikki marta uchragan
dastlabki uch bo‘lsa, ketma-ketlikka qirralar qo‘shish jarayonini
_{to‘xtatamiz,} chunki tuzilgan qirralar ketma-ketligining v_k

marta qatnashgan qismi biz izlayotgan sikldir. ■




uch ikki