boshlang‘ich uchi, b esa oxirgi uchi deb ataladi. Bundan tashqari, yoy
(a,b)
ko‘rinishda yozilsa, u haqida a uchdan chiquvchi (boshlanuvchi) va b uchga kiruvchi (uchda tugovchi) yoy deb aytish ham odat tusiga kirgan.
Qirra uchun uning
(a,b)
yozuvidagi harflar joylashish tartibi muhim rol
o‘ynamaydi va a va b elementlar qirraning uchlari yoki chetlari deb ataladi.
Agar grafda yo
(a,b)
qirra, yo
(a,b)
yoy, yoki
(b, a)
yoy topillsa, u holda a
va b uchlar tutashtirilgan deyiladi. Agar grafning ikkita uchini tutashtiruvchi qirra yoki yoy bor bo‘lsa, u holda ular qo‘shni uchlar deb, aks holda esa, qo‘shni bo‘lmagan uchlar deb aytiladi.
Grafning ikkita uchi qo‘shni bo‘lsa, ular shu uchlarni tutashtiruvchi qirraga
(yoyga) insident, o‘z navbatida, qirra yoki yoy bu uchlarga insident deyiladi.
Grafda ikkita qirra (yoy) umumiy chetga ega bo‘lsa, ular qo‘shni qirralar
(yoylar) deyiladi.
Shuni ta’kidlash kerakki, qo‘shnilik tushunchasi grafning bir jinsli, insidentlik tushunchasi esa uning turli jinsli elementlari orasidagi munosabatni ifodalaydi.
Ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni m va
qirralar (yoylar) soni n ga qarab belgilanadi va bu holda grafni ataydilar.
(m, n) -graf deb
Agar
G (V ,U )
grafda U kortej faqat qirralardan iborat bo‘lsa, u holda
yo‘naltirilmagan (oriyentirlanmagan) va faqat yo‘naltirilgan (oriyentirlangan) qirralardan (ya’ni, yoylardan) tashkil topgan bo‘lsa, u holda u yo‘naltirilgan (oriyentirlangan) graf deb ataladi. Oriyentirlangan graf, qisqacha, orgraf deb ham ataladi.
Ko‘p hollarda oriyentirlanmagan qirralari ham, oriyentirlangan qirralari ham bo‘lgan graflar bilan ish ko‘rishga to‘g‘ri keladi. Bunday graflar aralash graflar deb ataladi.
Agar
G (V ,U )
grafning (orgrafning) U korteji tarkibida
V V
to‘plamdan
olingan takrorlanuvchi elementlar bo‘lsa, u holda ular karrali yoki parallel qirralar (yoylar) deb ataladi. Karrali qirralari yoki yoylari bo‘lgan graf multigraf deyiladi.
Ikkala chetki (boshlang‘ich va oxirgi) uchlari ustma-ust tushgan qirra (yoy),
ya’ni grafning
(a, a) U
elementi sirtmoq deb ataladi. Sirtmoq, odatda,
yo‘naltirilmagan deb hisoblanadi. Qirralari (yoylari) orasida sirtmoqlari bo‘lgan graf psevdograf deyiladi.
Umumiy holda uchlar to‘plami V va (yoki) qirralar (yoylar, qirra va yoylar) korteji U cheksiz ko‘p elementli bo‘lishi mumkin. Bundan keyin V to‘plam va U
kortej faqat chekli bo‘lgan
|
