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 );
4.
– birorta ham qirraga ega bo‘lmasligi mumkin (
nol marshrut yoki
trivial marshrut ).
15
Grafda arzon marshrutni aniqlash Marshrutning uzunligi deb undagi qirralar soniga aytiladi. Turli qirralardan
tashkiltopgan marshrutga
zanjir deb ataladi. Agar zanjirning chetlaridan
tashqaribarcha uchlari turlicha bo‘lsa, u holda uni
oddiy zanjir deb ataydilar.
Berilgan zanjir yoki oddiy zanjir uchun 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.
6- misol. Yuqoridagi 1- shaklda tasvirlangan graf uchun 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. 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 zanjirning oxirgi bo‘g‘ini sifatida yoki 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.
16
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.
